上接前文，我们学习了栈的相关知识内容，接下来，来认识一个与栈类似的，另一种特殊的线性表，队列，本文目的是了解并认识队列这一概念，并实现循环队列
一、认识队列
1.队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊的线性表，队列具有先进先出的特性，在队尾插入数据，称为入队，在队头删除数据，称为出队。
如图所示：
2.队列的实现
队列可以由两种方式来实现，分别可以由顺序表，和链表来实现，队列又分为循环队列，非循环队列。
区分：
1.非循环队列时，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会低一点。
2.循环队列的时候，使用数组更加方便简洁，唯一缺点就是循环队列用数组的时候，只能是静态的数组，动态不能构成循环队列，当然可以使用循环链表
二、实现循环队列
我们使用数组的结构来实现循环队列
1.结构体格式以及初始化
代码如下：
#define MAXSIZE 11//表示的是数组的元素个数，多一个1，是为了留给rear空间的 typedef struct SqQueue { int data[MAXSIZE]; int front;//队头 int rear;//队尾 front 和 rear 就是指针（类似） }SqQueue; //初始化队列 void InitQueue(SqQueue* ps) { //初始化队列只需要队头队尾都为0 表示下标起始位置 ps->front = ps->rear = 0; }
实际上，我们使用的是静态数组，也只有这样我们才能实现循环队列，如果是动态数组，就无法实现循环效果，而且定义的MAXSIZE大小为11，有一个空间是不被存放数值的，作为一个标志。
2.队尾插入元素（入队）
最重要的一点是理解
(rear+1)%MAXSIZE==front 这是判断队列是否为满队列的标志
如图所示：
代码如下：
//队尾插入元素 void EnQueue(SqQueue* ps,int data) { //插入的时候先进行判满 if ((ps->rear + 1) % MAXSIZE == ps->front) {//最多存储MAXSIZE-1个元素 //表示已经满了 perror("队列已经满了，无法加入新元素\n"); exit(-1);//stdlib.h 头文件里面的 } ps->data[ps->rear] = data; ps->rear = (ps->rear + 1) % MAXSIZE; }
3.队头删除数据（出队）
如图所示：
代码如下：
//队头出队 //只需要移动指针位置即可 void OutQueue(SqQueue* ps, int* data) { //出队先判别是否为空 if (ps->rear == ps->front) { perror("为空队列，无法出队\n"); exit(-1); } *data = ps->data[ps->front]; ps->front = (ps->front + 1) % MAXSIZE; //不需要整体移动只要将队头指针后移就可以 }
4.打印
如图所示：
代码如下：
//遍历打印元素 void PrintQueue(SqQueue* ps) { int i = 0; printf("Queue->"); while ((i + ps->front)%MAXSIZE != ps->rear) { //从front的队头位置开始，i从0开始 ++一直到等于rear结束 printf("%d->", ps->data[i + ps->front]); i = (i + 1) % MAXSIZE; } printf("NULL\n"); }
5.清空队列、返回队头元素、返回队列元素个数
代码如下：
//将队列清空 void ClearQueue(SqQueue* ps) { ps->front = ps->rear = 0; } //返回队头元素 void GetHead(SqQueue* ps, int* data) { if (ps->front == ps->rear) { perror("为空队列\n"); exit(-1); } *data = ps->data[ps->front]; } //返回队列中的元素个数 int CountSqQueue(SqQueue* ps) { return (ps->rear - ps->front + MAXSIZE) % MAXSIZE; }
三、完整代码实现
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<malloc.h> #include<assert.h> #include<stdlib.h> //构建的是循环队列，是使用数组的形式，完成的循环队列 #define MAXSIZE 11//表示的是数组的元素个数，多一个1，是为了留给rear空间的 typedef struct SqQueue { int data[MAXSIZE]; int front;//队头 int rear;//队尾 front 和 rear 就是指针（类似） }SqQueue; //初始化队列 void InitQueue(SqQueue* ps) { //初始化队列只需要队头队尾都为0 表示下标起始位置 ps->front = ps->rear = 0; } //将队列清空 void ClearQueue(SqQueue* ps) { ps->front = ps->rear = 0; } //队尾插入元素 void EnQueue(SqQueue* ps,int data) { //插入的时候先进行判满 if ((ps->rear + 1) % MAXSIZE == ps->front) {//最多存储MAXSIZE-1个元素 //表示已经满了 perror("队列已经满了，无法加入新元素\n"); exit(-1);//stdlib.h 头文件里面的 } ps->data[ps->rear] = data; ps->rear = (ps->rear + 1) % MAXSIZE; } //队头出队 //只需要移动指针位置即可 void OutQueue(SqQueue* ps, int* data) { //出队先判别是否为空 if (ps->rear == ps->front) { perror("为空队列，无法出队\n"); exit(-1); } *data = ps->data[ps->front]; ps->front = (ps->front + 1) % MAXSIZE; //不需要整体移动只要将队头指针后移就可以 } //遍历打印元素 void PrintQueue(SqQueue* ps) { int i = 0; printf("Queue->"); while ((i + ps->front)%MAXSIZE != ps->rear) { //从front的队头位置开始，i从0开始 ++一直到等于rear结束 printf("%d->", ps->data[i + ps->front]); i = (i + 1) % MAXSIZE; } printf("NULL\n"); } //返回队头元素 void GetHead(SqQueue* ps, int* data) { if (ps->front == ps->rear) { perror("为空队列\n"); exit(-1); } *data = ps->data[ps->front]; } //返回队列中的元素个数 int CountSqQueue(SqQueue* ps) { return (ps->rear - ps->front + MAXSIZE) % MAXSIZE; } int main() { SqQueue Q; InitQueue(&Q); EnQueue(&Q, 1); EnQueue(&Q, 2); EnQueue(&Q, 3); EnQueue(&Q, 4); EnQueue(&Q, 5); PrintQueue(&Q); int a = 0; OutQueue(&Q, &a); PrintQueue(&Q); EnQueue(&Q, 1); EnQueue(&Q, 2); //EnQueue(&Q, 3); EnQueue(&Q, 4); EnQueue(&Q, 4); EnQueue(&Q, 5); EnQueue(&Q, 5); PrintQueue(&Q); }
总结
本文了解认识队列这一新的概念，我们也通过数组的结构实现循环队列，这一种方式实现循环队列是比较简单好理解的，主要的是理解MAXSIZE为什么要多一个空间，例如设置为11，还有判空，判满，操作。这是最为重要的。
判空：rear==front
判满：(rear+1)%MAXSIZE==front
得到队列元素个数：(rear-front+MAXSIZE)%MAXSIZE
front、rear、i得到下一个位置的方法：
例如：rear=(rear+1)%MAXSIZE
