如果你快乐起来了，就没法继续悲伤。
3.4、队列
? ????定义：
? ????????????一种可以实现“先进先出”的存储结构
? ????分类：
? ????????????链式队列 – 用链表实现
? ????????????静态队列 – 用数组实现
? ????????????????静态队列通常都必须是循环队列
? ????循环队列【思考】：
? ????????????1、 静态队列为什么必须是循环队列？
? ????????????2、 循环队列需要几个参数来确定？
? ????????????3、 循环队列各个参数的含义
typedef struct Queue
{
int * pBase; // 使用数组实现则 pBase相当于数组名
int front; //队头
int rear; //队尾
}QUEUE;
? ????????????4、循环队列入队伪算法
? ????????????5、循环队列出队伪算法
? ????????????6、 如何判断循环队列是否为空
? ????????????????pQ->front == pQ->rear
? ????????????7、 如何判断循环队列是否已满
????????????????????????两种方式：
????????????????????????????????????1.多增加一个表标识参数
????????????????????????????????????2.少用一个元素【通常使用】
???????????????????????????????????????????????? 如果r和f的值紧挨着，则队列已满
???????????????????????????????????????????????? if( (r+1)%数组长度 == f )
???????????????????????????????????????????????? ??????已满
???????????????????????????????????????????????? else
?????????????????????????????????????????????????????? 不满
? ????队列算法：
? ????????????入队
? ????????????出队
? ????队列的具体应用：
? ????????????所有和时间有关的操作都有队列的影子
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Queue
{
int * pBase;
int front;
int rear;
}QUEUE;
void init(QUEUE *); // 初始化
bool en_queue(QUEUE *, int val); // 入队
bool traverse_queue(QUEUE *); // 遍历
bool full_queue(QUEUE *); // 判断队列是否已满
bool out_queue(QUEUE *, int *); //出队
bool empty_queue(QUEUE *); // 判断队列是否为空
int main(void) {
QUEUE q;
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); // 此处初始化队列长度为6，但循环队列 一般只存放 队列长度-1 个元素，所以6不会入队
traverse_queue(&q); // 1 2 3 4 5
int val;
if(out_queue(&q, &val))
{
printf("出队成功！出队元素为：%d\n",val);
}
else
{
printf("出队失败\n");
}
traverse_queue(&q); // 2 3 4 5
return 0;
}
void init(QUEUE * pQ)
{
pQ->pBase = (int *)malloc(sizeof(int) * 6); // 假定队列长度为6
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;
}
}
bool traverse_queue(QUEUE * pQ)
{
int i = pQ->front;
while (i != pQ->rear)
{
printf("%d\t", pQ->pBase[i]);
i = (i + 1) % 6;
}
printf("\n");
}
bool empty_queue(QUEUE * pQ)
{
if(pQ->front == pQ->rear)
return true;
else
return false;
}
bool out_queue(QUEUE * pQ, int * pVal)
{
if (empty_queue(pQ))
{
return false;
}
else
{
*pVal = pQ->pBase[pQ->front];
pQ->front = (pQ->front+1) % 6;
return true;
}
}
运行结果如下：
