一种可以实现 "先进先出" 的存储结构
分类:
链式队列: 用链表实现
静态队列: 用数组实现, 静态队列通常都必须是循环队列
循环队列的讲解:
静态队列为什么是循环队列
减少对内存的浪费
循环队列需要几个参数来确定
两个参数, frant ,rear 但这 2 个参数不同场合有不同的含义, 建议初学者先记住
循环队列各个参数的含义
队列初始化: front 和 rear 的值都是零
队列非空: front 代表队列的第一个元素, rear 代表队列的最后一个有效元素的下一个元素
队列空: front 和 rear 的值相等, 但不一定是零
循环队列入队伪算法
将值存入 rear 所代表的位置
错误的写法: r = r + 1
正确的应该是 r = (r+1)% 数组长度
循环队列出队伪算法
front = (front+1)% 数组长度
如何判断循环队列是否为空
如果 front 和 rear 的值相等, 则队列为空
如何判断循环队列已满
多增加一个表标识的参数
少用一个元素, 通常都是这样:(rear+1) % 数组长度 == front
具体的实现
- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.h>
- typedef struct Queue
- {
- int * pBase;
- int front;
- int rear;
- }QUEUE;
- void init(QUEUE *);
- bool full_queue(QUEUE *);
- bool empty(QUEUE *);
- bool en_queue(QUEUE * , int val); // 入队
- void traverse(QUEUE *);
- bool out(QUEUE *, int * pVal);
- int main(void)
- {
- QUEUE Q;
- int val;
- init(&Q);
- en_queue(&Q , 1);
- en_queue(&Q , 2);
- en_queue(&Q , 3);
- en_queue(&Q , 4);
- en_queue(&Q , 5);
- en_queue(&Q , 6);
- en_queue(&Q , 7);
- traverse(&Q);
- if (out(&Q , &val))
- {
- printf("出队成功, 出队的元素:%d\n", val);
- en_queue(&Q , 9);
- traverse(&Q);
- }
- else
- {
- printf("出队失败 \ n");
- }
- return 0;
- }
- void init(QUEUE * pQ)
- {
- pQ->pBase = (int *)malloc(sizeof(int) * 6); // 初始化默认是长度是 6
- if (NULL == pQ->pBase)
- {
- printf("初始化失败 \ n");
- exit(-1);
- }
- pQ->front = 0;
- pQ->rear = 0;
- }
- bool full_queue(QUEUE *pQ)
- {
- if ((pQ->rear+1)%6 == pQ->front)
- {
- return true;
- }
- else
- {
- return false;
- }
- }
- bool en_queue(QUEUE *pQ , int val)
- {
- if (full_queue(pQ))
- {
- return false;
- }
- else
- {
- pQ->pBase[pQ->rear] = val;
- pQ->rear = (pQ->rear+1)%6;
- return true;
- }
- }
- void traverse(QUEUE * pQ)
- {
- int i = pQ->front;
- while(i != pQ->rear)
- {
- printf("%d\n",pQ->pBase[i] );
- i = (i+1) % 6;
- }
- return;
- }
- bool empty(QUEUE * pQ)
- {
- if (pQ->front == pQ->rear)
- {
- return true;
- }
- else
- {
- return false;
- }
- }
- bool out(QUEUE * pQ, int * pVal)
- {
- if (empty(pQ))
- {
- return false;
- }
- else
- {
- *pVal = pQ->pBase[pQ->front];
- pQ->front = (pQ->front+1) % 6;
- return true;
- }
- }
队列的应用
所有和时间有关的操作都有队列的影子
来源: https://www.cnblogs.com/mengd/p/12045809.html