目录

一、普通的顺序存储队列

二、循环队列

（1）少用一个元素空间

i、初始化队列操作：

iii、入队操作：

iv、出队操作：

（2）设置flag标志

i、初始化队列操作：

ii、判断队空操作：

iii、入队操作：

iv、出队操作：

（3）设置length存储队列元素的个数

i、初始化队列操作：

ii、判断队空操作：

iii、入队操作：

iv、出队操作：

（4）总结

三、循环队列测试程序

（1）少用一个元素空间

（2）设置flag标志

（3）设置length存储队列元素的个数

四、拓展

（1）思路

（2）修改代码

队空和队满条件没有改变。

i、初始化操作：

ii、判断队列为空操作：

iii、入队操作：

iv、出队操作：

（3）测试程序

一、普通的顺序存储队列

在介绍循环队列三种判断队空、队满操作之前，先解释下为啥会用循环队列。

队列：一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一段称为队尾，允许删除的一段称为队头。

咱们看一下普通的顺序存储队列：

普通的顺序储存队列的存储结构为：

#define MAXSIZE 5typedef int DataType;typedef struct Queue{DataType data[MAXSIZE];// 存储队列的数据空间int front; // 队头指针int rear;// 队尾指针 }SeqQueue;

如图所示：

front、rear分别指向队头，也就是数组索引为0的地方，此时队列为空（即rear == front），

现在将0、1、2、3、4依次入队（队尾指针rear一直向后移，队头指针front不动）。

如图所示：

0、1、2、3、4入队后，rear指向数组的后面，此时队满（即rear == MAXSIZE），然后再将0、1、2、3、4出队，出队后变为 队尾指针和队头指针都指向数组后面（即 rear == front），但如果现在 5 想入队却又入不了，应为 rear的值已经超过数组的最大索引，像这种数组有位置但却无法插入的这种现象叫做“假溢出”。

如图所示：

但如果咱们想rear在数组索引为0处就好。有这个想法的同学很不错，这就引出了循环队列。

二、循环队列

像上面想的那样，咱们只要把队尾和队头连，那个rear不就指向数组索引为0的地方，这就是循环队列。而怎样实现呢？只需将 入队后的rear和 出队后的front同 MAXSIZE取余即可。例如上面的队满时，rear = 5，对MAXSIZE取余后，即 rear = rear % MAXSIZE = 0；符合我们的想法。

rear = (rear + 1) % MAXSIZE; // 入队后取余front = (front + 1) % MAXSIZE; // 出队后取余

循环队列：队列头尾相接的顺序存储结构就是循环队列。

如图所示：

此时循环队列为空（rear == front）。然后将0、1、2、3、4入队，此时的rear会指向数组索引为0的地方，不会像上面普通队列那样指到数组外。

然后将0、1出队，rear指针不动，front指向2处。

此时 5 入队，如果是普通队列的话，此时入队便失败（由于rear指向了数组外），但循环队列不会，此时rear指向 0 处，而之前 0 处的项已经出队，故可入队。

此时衍生一个问题，就是咱们之前队满时，有rear == front，但之前队空时 ，也有rear == front。那当 rear == front 时，是队空还是队满呢？这是不是很有歧义，所以咱们就要来解决这个问题。（即使判断队空和队满的条件不同，消除歧义）。

解决这个问题的三种方法：

1. 少用一个元素的空间；
2. 设置一个flag，来区别队列的 “空” 和 “满” ；
3. 设置一个变量。统计队列中的元素数量。

（1）少用一个元素空间

当队满时，rear 和 front相差一个元素，此时的 rear 不等于 front，也就区分了队空和队满的条件（即 rear == front 为队空，而非队满）。

此时 (rear + 1) % MAXSIZE == front 为队队满，rear == front 为队空。

队空的判断条件：

q->rear == q->front

队满的判断条件：

(q->rear + 1) % MAXSIZE == q->front;

队列的存储结构：

#define MAXSIZE 5typedef int DataType;typedef struct Queue{DataType data[MAXSIZE];// 存储队列的数据空间int front; // 队头指针int rear;// 队尾指针 }SeqQueue;

i、初始化队列操作：

利用malloc()函数分配队列的存储结构，再将 front = rear = 0；此时队列为空。

SeqQueue* InitQueue(){SeqQueue* q;q = (SeqQueue*)malloc(sizeof(SeqQueue)); // 队列的存储结构q->front = q->rear = 0; // 初始化rear和front，队列为空printf("循环队列已经创建完毕\n");return q;}

ii、判断队空操作：

利用队空判断条件 rear == front；成立队列为空，不成立队列不为空。

bool QueueEmpty(SeqQueue* q){if (q->rear == q->front)// 判断队空return true;return false;}

iii、入队操作：

首先利用队满条件判断队列是否为满，队满则退出入队函数，不为满着进行入队操作，并将 rear 利用 rear =（rear+1） % MAXSIZE 进行更新。

bool EnQueue(SeqQueue* q, DataType x){if ((q->rear+1) % MAXSIZE == q->front) // 判断队满{printf("循环队列已满！\n");return false;}q->data[q->rear] = x; // 入队q->rear = (q->rear + 1) % MAXSIZE; // 更新rearreturn true;}

iv、出队操作：

利用队空条件判断队列是否为空，队列为空不能进行出队操作。队不为空时，进行出队操作，并将front = (front + 1) % MAXSIZE 进行更新。

DataType DeQueue(SeqQueue* q){DataType x; // 出队元素的值if (q->rear == q->front)// 判断队空{printf("队列为空！不能进行删除操作\n");return -1;}x = q->data[q->front]; // 出队q->front = (q->front + 1) % MAXSIZE; // 更新frontreturn x;}

（2）设置flag标志

当设置flag标志时，就不需要空出一个元素的位置。队满时，flag对应一个值，队空时，flag对应一个与队满时flag的值不同的值（即队空和队满的flag值不一样），所以当 front == rear 时，依靠 flag值就可以区分队空队满。

注：flag标志可以自选，符合上面的flag条件即可。（队满和队空的flag值不同）。

队列的存储结构：

#define MAXSIZE 5typedef int DataType;typedef struct Queue{DataType data[MAXSIZE];int front;int rear;bool flag;}SeqQueue;

当 rear = front 且 flag = flase 时队空.

当 rear = front 且 flag = true时，队列为满。

队空判断条件：

(q->front == q->rear) && !(q->flag)

队满判断条件：

(q->front == q->rear) && q->flag

i、初始化队列操作：

利用malloc()函数创建队列，初始化 rear = front = 0，并将 flag 设置为队空标志（flag = false）。

SeqQueue* InitQueue(){SeqQueue* q;q = (SeqQueue*)malloc(sizeof(SeqQueue)); // 分配队列的内存q->flag = false; // 设置队空标志q->front = q->rear = 0; // 初始化 rear和 frontprintf("循环队列已经创建完毕\n");return q;}

ii、判断队空操作：

利用队空判断条件进行判断，成立则队空，不成立则队不为空。

bool QueueEmpty(SeqQueue* q){if ((q->front == q->rear) && !(q->flag))// 判断队空return true;return false;}

iii、入队操作：

首先判断利用队满条件判断是否可以入队，可以入队，然后再进行入队操作，并更新rear，入队后，需要判断 rear 是否等于 front，（即入队后要判断队是否为满）队满设置flag为队满的的flag值。（这就是和最开始的循环队列的区别，因为最开始的循环队列，当入队后rear = front，没设置区分队空和队满的标志，在退出入队函数后，就区分不了队空、队满，此时 rear = front）。

bool EnQueue(SeqQueue* q, DataType x){if ((q->front == q->rear) && q->flag) // 判断队满{printf("循环队列已满！\n");return false;}q->data[q->rear++] = x; // 入队q->rear %= MAXSIZE; // 更新rearif (q->rear == q->front) // 判断入队后，队是否为满，满则设置队满标志flagq->flag = true; // 队满return true;}

iv、出队操作：

首先利用队空判断条件判断队列是否为空，可以出队，再执行出队操作，并更新front，出队后，需要判断 rear 是否等于 front，（即出队后要判断队是否为空）队空设置flag为队空的的flag值。（这就是和最开始的循环队列的区别，因为最开始的循环队列，当出队后rear = front，没设置区分队空和队满的标志，在退出出队函数后，就区分不了队空、队满，此时 rear = front）。

DataType DeQueue(SeqQueue* q){DataType x; // 出队的元素的值if ((q->front == q->rear) && !(q->flag))// 判断队空{printf("队列为空！不能进行删除操作\n");return -1;}x = q->data[q->front++]; // 出队q->front %= MAXSIZE; // 更新frontif (q->front == q->rear) // 判断出队后队列是否为空，设置flag标志q->flag = false; // 队空return x;}

（3）设置length存储队列元素的个数

利用length来存储队列的元素个数（即队列的长度），不需要为了判断队满、队空牺牲一个元素的空间，同时利用 length 这个变量，判断队空、队满很简单，（即length = 0，队空；length = MAXSIZE，队满），不需要利用到 rear 和 front 来判断队空、队满。

队列的存储结构：

#define MAXSIZE 5typedef int DataType;typedef struct Queue {DataType data[MAXSIZE];int front;int rear;int length;}SeqQueue;

当 length = 0时，队空。

当 length = MAXSIZE时，队满。

队空判断条件：

q->length == 0

队满判断条件：

q->length == MAXSIZE

i、初始化队列操作：

利用malloc()函数分配队列的空间，并初始化 rear 和 front，初始化 length = 0，为队空的标志。

SeqQueue* InitQueue(){SeqQueue* q;q = (SeqQueue*)malloc(sizeof(SeqQueue)); // 分配队列空间q->length = 0; // 初始化length，队列为空q->rear = q->front = 0; // 初始化rear 和 frontprintf("循环队列已经创建完毕\n");return q;}

ii、判断队空操作：

直接利用 length = 0 来判断队列是否为空。

bool QueueEmpty(SeqQueue* q){if (q->length == 0)// 判断队空return true;return false;}

iii、入队操作：

首先利用队满条件判断队列是否已满，未满则进行入队操作，并更新rear，队列长度加一（length++）。

bool EnQueue(SeqQueue* q, DataType x){if (q->length == MAXSIZE) // 判断队满{printf("循环队列已满！\n");return false;}q->data[q->rear++] = x; // 入队q->rear %= MAXSIZE; // 更新rearq->length++; // 队列长度加一return true;}

iv、出队操作：

利用队列为空条件判断队列是否为空，空就不进行出队操作。不为空时，出队，更新front，队列长度减一(length–）。

DataType DeQueue(SeqQueue* q){DataType x; // 出队元素的值if (q->length == 0)// 判断队空{printf("队列为空！不能进行删除操作\n");return -1;}q->data[q->front++] = x; // 出队q->front %= MAXSIZE; // 更新frontq->length--; // 队列的长度减一return x;}

（4）总结

总体来说，使用 length 来保存队列的元素个数（队列长度）的方法，是最简单的。而带有flag标志区分队满、对空的方法，则较难点。牺牲一个元素的方法在二者之间，可以根据自身的情况来选用这三种方法的一种。

三、循环队列测试程序

在所有队列使用之前，均要初始化队列。

（1）少用一个元素空间

#include #include #include #define MAXSIZE 5typedef int DataType;typedef struct Queue{DataType data[MAXSIZE];int front;int rear;}SeqQueue;SeqQueue* InitQueue();bool QueueEmpty(SeqQueue* q);bool EnQueue(SeqQueue* q, DataType x);DataType DeQueue(SeqQueue* q);void ShowQueue(SeqQueue* q);int ShowMeanu();int main(void){int choice;SeqQueue* queue;while (true){int choice;choice = ShowMeanu();switch (choice){case 0:exit(0);break;case 1: queue = InitQueue();break;case 2: {int x;printf("请输入要入队的值：");scanf("%d", &x);EnQueue(queue, x);}break;case 3: DeQueue(queue);break;case 4: {bool statue = QueueEmpty(queue);if (statue)printf("队列为空\n");elseprintf("队列不为空\n");}break;case 5: ShowQueue(queue);break;default: printf("请输入恰当的测试功能！！！\n");}}return 0;}int ShowMeanu(){int choice;printf("\n欢迎来到循环队列测试程序！！！！！\n");printf("有以下功能可提供测试\n");printf("1.创建循环队列2.入队\n");printf("3.出队 4.判断队空\n");printf("5.队列显示\n");printf("0.退出程序\n");printf("你需要测试的功能是：");scanf("%d", &choice);return choice;}SeqQueue* InitQueue(){SeqQueue* q;q = (SeqQueue*)malloc(sizeof(SeqQueue));q->front = q->rear = 0;printf("循环队列已经创建完毕\n");return q;}bool QueueEmpty(SeqQueue* q){if (q->rear == q->front)// 判断队空return true;return false;}bool EnQueue(SeqQueue* q, DataType x){if ((q->rear+1) % MAXSIZE == q->front){printf("循环队列已满！\n");return false;}q->data[q->rear] = x;q->rear = (q->rear + 1) % MAXSIZE;return true;}DataType DeQueue(SeqQueue* q){DataType x;if (q->rear == q->front)// 判断队空{printf("队列为空！不能进行删除操作\n");return -1;}x = q->data[q->front];q->front = (q->front + 1) % MAXSIZE;return x;}void ShowQueue(SeqQueue* q){int front, rear;front = q->front;rear = q->rear;if (rear == front){printf("队列为空！！！\n");return;}while (rear != front)printf("%d\n", q->data[front++]);return;}

（2）设置flag标志

#include #include #include #define MAXSIZE 5typedef int DataType;typedef struct Queue{DataType data[MAXSIZE];int front;int rear;bool flag;}SeqQueue;SeqQueue* InitQueue();bool QueueEmpty(SeqQueue* q);bool EnQueue(SeqQueue* q, DataType x);DataType DeQueue(SeqQueue* q);void ShowQueue(SeqQueue* q);int ShowMeanu();int main(void){int choice;SeqQueue* queue;while (true){int choice;choice = ShowMeanu();switch (choice){case 0:exit(0);break;case 1: queue = InitQueue();break;case 2: {int x;printf("请输入要入队的值：");scanf("%d", &x);EnQueue(queue, x);}break;case 3: DeQueue(queue);break;case 4: {bool statue = QueueEmpty(queue);if (statue)printf("队列为空\n");elseprintf("队列不为空\n");}break;case 5: ShowQueue(queue);break;default: printf("请输入恰当的测试功能！！！\n");}}return 0;}int ShowMeanu(){int choice;printf("\n欢迎来到循环队列测试程序！！！！！\n");printf("有以下功能可提供测试\n");printf("1.创建循环队列2.入队\n");printf("3.出队 4.判断队空\n");printf("5.队列显示\n");printf("0.退出程序\n");printf("你需要测试的功能是：");scanf("%d", &choice);return choice;}SeqQueue* InitQueue(){SeqQueue* q;q = (SeqQueue*)malloc(sizeof(SeqQueue));q->flag = false;q->front = q->rear = 0;printf("循环队列已经创建完毕\n");return q;}bool QueueEmpty(SeqQueue* q){if ((q->front == q->rear) && !(q->flag))// 判断队空return true;return false;}bool EnQueue(SeqQueue* q, DataType x){if ((q->front == q->rear) && q->flag){printf("循环队列已满！\n");return false;}q->data[q->rear] = x;++(q->rear);q->rear %= MAXSIZE;if (q->rear == q->front) // 设置队列已满q->flag = true;return true;}DataType DeQueue(SeqQueue* q){DataType x;if ((q->front == q->rear) && !(q->flag))// 判断队空{printf("队列为空！不能进行删除操作\n");return -1;}x = q->data[q->front++];q->front %= MAXSIZE;if (q->front == q->rear) // 设置队列为空q->flag = false;return x;}void ShowQueue(SeqQueue* q){int front, rear;front = q->front;rear = q->rear;if ((front == rear) && !(q->flag)){printf("队列为空\n");return;}/*while (front != rear) // 循环输出队列元素{printf("%d\n", q->data[front++]);front %= MAXSIZE;}// 忽略了队满 rear == front*/// 先输出一个元素，便可解决上面此种情况printf("%d\n", q->data[front++]);while (front != rear) // 循环输出队列元素{printf("%d\n", q->data[front++]);front %= MAXSIZE;}return;}

（3）设置length存储队列元素的个数

#include #include #include #define MAXSIZE 5typedef int DataType;typedef struct Queue {DataType data[MAXSIZE];int front;int rear;int length;}SeqQueue;SeqQueue* InitQueue();bool QueueEmpty(SeqQueue* q);bool EnQueue(SeqQueue* q, DataType x);DataType DeQueue(SeqQueue* q);void ShowQueue(SeqQueue* q);int ShowMeanu();int main(void){int choice;SeqQueue* queue;while (true){int choice;choice = ShowMeanu();switch (choice){case 0:exit(0);break;case 1: queue = InitQueue();break;case 2: {int x;printf("请输入要入队的值：");scanf("%d", &x);EnQueue(queue, x);}break;case 3: DeQueue(queue);break;case 4: {bool statue = QueueEmpty(queue);if (statue)printf("队列为空\n");elseprintf("队列不为空\n");}break;case 5: ShowQueue(queue);break;default: printf("请输入恰当的测试功能！！！\n");}}return 0;}int ShowMeanu(){int choice;printf("\n欢迎来到循环队列测试程序！！！！！\n");printf("有以下功能可提供测试\n");printf("1.创建循环队列2.入队\n");printf("3.出队 4.判断队空\n");printf("5.队列显示\n");printf("0.退出程序\n");printf("你需要测试的功能是：");scanf("%d", &choice);return choice;}SeqQueue* InitQueue(){SeqQueue* q;q = (SeqQueue*)malloc(sizeof(SeqQueue));q->length = 0;q->rear = q->front = 0;printf("循环队列已经创建完毕\n");return q;}bool QueueEmpty(SeqQueue* q){if (q->length == 0)// 判断队空return true;return false;}bool EnQueue(SeqQueue* q, DataType x){if (q->length == MAXSIZE){printf("循环队列已满！\n");return false;}q->data[q->rear++] = x;q->rear %= MAXSIZE;q->length++;return true;}DataType DeQueue(SeqQueue* q){DataType x;if (q->length == 0)// 判断队空{printf("队列为空！不能进行删除操作\n");return -1;}q->data[q->front++] = x;q->front %= MAXSIZE;q->length--;return x;}void ShowQueue(SeqQueue* q){int front = q->front;int length = q->length; // 存储队列长度if (length == 0){printf("队列为空！！！\n");return;}while (length != 0){printf("%d\n", q->data[front++]);front %= MAXSIZE;length--;}return;}

四、拓展

当上面的方法三（即利用length来保存队列的元素个数），少了一个指针，你是否还能进行入队、出队的操作。这里我用少了一个队头指针（front）来做演示。

（1）思路

少了一个front队头指针，我们的出队就变的好像不知所措，我们一般想如果它能用length 和 rear 表示该多好，而这也正是解决此题的方法，我们需要找出 rear、front 和 length 这三者之间的关系。

length 表示列表长度，那 首先猜想length = rear – front 是不是可以推出 front = rear – length 呢？看下图：

此时length = 2， rear = 4,。front = rear – length = 2好像可以，但再看下图：

此时 length = 3，rear = 0。front = rear – length = -3那就不行了，故 frontrear – length。

咱们想对上面第二个图（即front = -3），rear 加上空的位置个数是不是就是front，对的，它就是front，那空的位置个数等于数组的最大元素的个数减去队列的长度（MAXSIZE – length），即 front = (rear + MAXSIZE – length).但又看第一个图：

此时 front 好像不需要MAXSIZE就可得出（front = rear – length）；那现在要解决的问题就是，要在需要MAXSIZE就要有，不需要则无，因为 MAXSIZE 对其本身求模为 0，故在把上公式对MAXSIZE求模，就相当于MAXSIZE没有，故公式改进为front = (rear + MAXSIZE – length) % MASIZE.符合两个图，那就推出了length 、rear、front三者之间的关系（即 front = (rear + MAXSIZE – length) % MASIZE）。然后利用这个关系就可以修改之前那个源码了。

（2）修改代码

队列的存储结构：

#define MAXSIZE 5typedef int DataType;typedef struct Queue{DataType data[MAXSIZE];int rear;int length; // 少了front指针}SeqQueue;

队空和队满条件没有改变。

队空条件：

q->length == 0

队满条件：

q->length == MAXSIZE

i、初始化操作：

利用malloc()函数分配队列的空间，初始化length和rear。

SeqQueue* InitQueue(){SeqQueue* q;q = (SeqQueue*)malloc(sizeof(SeqQueue));q->length = 0; // 初始化lengthq->rear = 0; // 初始化printf("循环队列已经创建完毕\n");return q;}

ii、判断队列为空操作：

利用length == 0.

bool QueueEmpty(SeqQueue* q){if (q->length == 0)// 判断队空return true;return false;}

iii、入队操作：

入队操作和上面的没变——利用队满条件判断队列是否已满，未满则进行入队操作，并更新rear，队列长度加一（length++）。

bool EnQueue(SeqQueue* q, DataType x){if (q->length == MAXSIZE) // 判断队满{printf("循环队列已满！\n");return false;}q->data[q->rear++] = x; // 入队q->rear %= MAXSIZE;// 更新rearq->length++;// 队列长度加一return true;}

iv、出队操作：

出队操作改变了，这里要声明一个局部变量，充当 front 队头指针，利用关系front = (rear + MAXSIZE – length) % MASIZE求出队头的位置，再进行出队操作并更新length。

DataType DeQueue(SeqQueue* q){DataType x;int front; // 局部变量，相当于队头指针if (q->length == 0)// 判断队空{printf("队列为空！不能进行删除操作\n");return -1;}front = (MAXSIZE - q->length + q->rear) % MAXSIZE; // 求出队头指针位置x = q->data[front]; // 出队q->length--;// 队列长度减一return x;}

如果是去掉队尾指针rear，则利用等式 rear = (front + length) % MAXSIZE 求出rear，其等式过程是怎样形成的，与上面类似（去掉front队头指针），请自行思考。

（3）测试程序

在使用队列之前，请对队列初始化。

#include #include #include #define MAXSIZE 5typedef int DataType;typedef struct Queue{DataType data[MAXSIZE];int rear;int length;}SeqQueue;SeqQueue* InitQueue();bool QueueEmpty(SeqQueue* q);bool EnQueue(SeqQueue* q, DataType x);DataType DeQueue(SeqQueue* q);void ShowQueue(SeqQueue* q);int ShowMeanu();int main(void){int choice;SeqQueue* queue;while (true){int choice;choice = ShowMeanu();switch (choice){case 0:exit(0);break;case 1: queue = InitQueue();break;case 2: {int x;printf("请输入要入队的值：");scanf("%d", &x);EnQueue(queue, x);}break;case 3: DeQueue(queue);break;case 4: {bool statue = QueueEmpty(queue);if (statue)printf("队列为空\n");elseprintf("队列不为空\n");}break;case 5: ShowQueue(queue);break;default: printf("请输入恰当的测试功能！！！\n");}}return 0;}int ShowMeanu(){int choice;printf("\n欢迎来到循环队列测试程序！！！！！\n");printf("有以下功能可提供测试\n");printf("1.创建循环队列2.入队\n");printf("3.出队 4.判断队空\n");printf("5.队列显示\n");printf("0.退出程序\n");printf("你需要测试的功能是：");scanf("%d", &choice);return choice;}SeqQueue* InitQueue(){SeqQueue* q;q = (SeqQueue*)malloc(sizeof(SeqQueue));q->length = 0;q->rear = 0;printf("循环队列已经创建完毕\n");return q;}bool QueueEmpty(SeqQueue* q){if (q->length == 0)// 判断队空return true;return false;}bool EnQueue(SeqQueue* q, DataType x){if (q->length == MAXSIZE){printf("循环队列已满！\n");return false;}q->data[q->rear++] = x;q->rear %= MAXSIZE;q->length++;return true;}DataType DeQueue(SeqQueue* q){DataType x;int front;if (q->length == 0)// 判断队空{printf("队列为空！不能进行删除操作\n");return -1;}front = (MAXSIZE - q->length + q->rear) % MAXSIZE;x = q->data[front];q->length--;return x;}void ShowQueue(SeqQueue* q){int front;int length = q->length; // 存储队列长度if (length == 0){printf("队列为空！！！\n");return;}while (length != 0){front = (MAXSIZE - length + q->rear) % MAXSIZE;printf("%d", q->data[front]);length--;}return;}