环形队列详解

大家好，欢迎来到IT知识分享网。

一、环形队列的定义

1.1 队列及环形队列定义

        队列是一种线性数据结构，它遵循先进先出或后近后出的原则。队列允许在一端插入元素，另一端删除元素。队列有时也被称为待办事项列表，尤其是在计算机程序中，它被广泛用于任务排队、缓存和异步处理方案中。

        环形队列，它可以在固定大小的数组中循环使用。它类似于普通队列，但与普通队列不同的是，在环形队列中，队列的队尾可以接到数组的开头，使数组像一个圆环一样循环。因此，环形队列往往比普通队列的效率更高，尤其是在实现循环缓冲区等应用时。环形队列主要的操作有入队和出队。

1.2 环形队列的特点

环形队列是一种特殊的队列数据结构，它的特点如下：

1. 队列的存储结构是一个环形结构，即队列的头尾相连，形成一个环形。
2. 队列有固定的大小，通常用数组来实现。
3. 队列的插入和删除操作只能在队头和队尾进行，而不能在中间进行。
4. 当队列的头指针或尾指针达到队列的末尾时，它们将指向队列的起始位置，形成环形。
5. 环形队列的操作效率较高，只需要通过指针的移动来完成插入和删除操作。

二、环形队列的实现与使用

2.1 环形队列的接口定义

#include <stdio.h> #define MAXSIZE 100 typedef int DataType; typedef struct { DataType data[MAXSIZE]; int front; int rear; }CirclesQueue; /*循环队列初始化*/ int init(CirclesQueue *Q); /*入队*/ int enqueue(CirclesQueue *Q, DataType x); /*队满？*/ int isfull(CirclesQueue *Q); /*出队*/ int dequeue(CirclesQueue *Q, DataType *); /*队空*/ int isempty(CirclesQueue *Q); /*队长*/ int querylen(CirclesQueue *Q); /*打印队首元素*/ int printfront(CirclesQueue *Q); /*输出队列*/ void querylist(CirclesQueue *Q);

2.2 环形队列的实现

2.2.1 环形队列初始化

int init(CirclesQueue *Q) { Q->front =0; Q->rear = 0; return 0; }

2.2.2 入队

int enqueue(CirclesQueue *Q, DataType x) { if(isfull(Q)) { printf("队列已满！\n"); return ; } Q->rear = (Q->rear+1) % MAXSIZE; Q->data[Q->rear] =x; return 0; }

2.2.3 出队

int dequeue(CirclesQueue *Q, DataType *x) { if(isempty(Q)) { printf("队列为空！\n"); return ; } Q->front = (Q->front+1) % MAXSIZE; *x = Q->data[Q->front]; return 0; }

2.2.4 判断是否队空

int isempty(CirclesQueue *Q) { return (Q->front == Q->rear) ? 1 : 0; }

2.2.5 判断是否队满

int isfull(CirclesQueue *Q) { return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0; }

2.2.6 输出队列长度

int querylen(CirclesQueue *Q){ return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; } 

2.2.7 取队首元素

int printfront(CirclesQueue *Q){ DataType a; if(isempty(Q)) { printf("队列为空！\n"); return ; }else { return Q->data[Q->front +1 %MAXSIZE]; } return 0; }

2.2.8 输出队列

void querylist(CirclesQueue *Q) { int i; if (isempty(Q)) { printf("队列为空\n"); return; } i = (Q->front)%MAXSIZE; printf("队列："); do { printf("%d ",Q->data[i + 1 % MAXSIZE]); i = (i + 1) % MAXSIZE; } while (i != Q->rear); printf("\n"); }

2.3环形队列的使用

#include <stdio.h> #include "CirclesQueue.h" #include "welcome.h" int main(int argc, char* argv[]) { CirclesQueue Q; DataType x,a,len; int i,m,n,cmd; char yn; for(i=0;i<strlen(welcome);i++) { printf("%c",welcome[i]); for(m=0;m<1000;m++) for(n=0;n<1000;n++) { ; } } do { printf("-----------循环队列演示-----------\n"); printf(" 1. 初始化\n"); printf(" 2. 入队\n"); printf(" 3. 出队\n"); printf(" 4. 队空？\n"); printf(" 5. 队满\n"); printf(" 6. 队列长度\n"); printf(" 7. 打印队首元素\n"); printf(" 8. 打印队列\n"); printf(" 9. 帮助\n"); printf(" 0. 退出\n"); printf(" 请选择（0~9）："); scanf("%d",&cmd); switch(cmd) { case 1: init(&Q); printf("队列已初始化！\n"); break; case 2: printf("请输入要入队的元素x="); scanf("%d", &x); if(!enqueue(&Q,x)) { printf("元素x=%d已入队\n", x); } break; case 3: printf("确定要出队（出队会将删除对首元素, y or n, n）？"); fflush(stdin); scanf("%c", &yn); if(yn == 'y' || yn == 'Y') { if(!dequeue(&Q,&x)) { printf("队首元素【%d】已出队！\n", x); } } break; case 4: if (isempty(&Q) == 1) { printf("队列为空！\n"); }else{ printf("队列不是空的！\n"); } break; case 5: if (isfull(&Q) == 1) { printf("队列已满！\n"); }else{ printf("队列未满！\n"); } break; case 6 : len = querylen(&Q); printf("队列长度为【%d】\n",len); break; case 7: a = printfront(&Q); printf("队首元素为【%d】\n",a); break; case 8: querylist(&Q); break; case 9: printf("本程序为环形队列的演示程序，由黄彬森设计开发，本程序演示了环形队列功能！\n"); break; } }while(cmd!=0); return 0; }

三、完整代码

3.1  main.c文件代码

#include <stdio.h> #include "CirclesQueue.h" #include "welcome.h" int main(int argc, char* argv[]) { CirclesQueue Q; DataType x,a,len; int i,m,n,cmd; char yn; for(i=0;i<strlen(welcome);i++) { printf("%c",welcome[i]); for(m=0;m<1000;m++) for(n=0;n<1000;n++) { ; } } do { printf("-----------循环队列演示-----------\n"); printf(" 1. 初始化\n"); printf(" 2. 入队\n"); printf(" 3. 出队\n"); printf(" 4. 队空？\n"); printf(" 5. 队满\n"); printf(" 6. 队列长度\n"); printf(" 7. 打印队首元素\n"); printf(" 8. 打印队列\n"); printf(" 9. 帮助\n"); printf(" 0. 退出\n"); printf(" 请选择（0~9）："); scanf("%d",&cmd); switch(cmd) { case 1: init(&Q); printf("队列已初始化！\n"); break; case 2: printf("请输入要入队的元素x="); scanf("%d", &x); if(!enqueue(&Q,x)) { printf("元素x=%d已入队\n", x); } break; case 3: printf("确定要出队（出队会将删除对首元素, y or n, n）？"); fflush(stdin); scanf("%c", &yn); if(yn == 'y' || yn == 'Y') { if(!dequeue(&Q,&x)) { printf("队首元素【%d】已出队！\n", x); } } break; case 4: if (isempty(&Q) == 1) { printf("队列为空！\n"); }else{ printf("队列不是空的！\n"); } break; case 5: if (isfull(&Q) == 1) { printf("队列已满！\n"); }else{ printf("队列未满！\n"); } break; case 6 : len = querylen(&Q); printf("队列长度为【%d】\n",len); break; case 7: a = printfront(&Q); printf("队首元素为【%d】\n",a); break; case 8: querylist(&Q); break; case 9: printf("本程序为环形队列的演示程序，由黄彬森设计开发，本程序演示了环形队列功能！\n"); break; } }while(cmd!=0); return 0; }

3.2  CirclesQueue.h文件代码

#include <stdio.h> #define MAXSIZE 100 typedef int DataType; typedef struct { DataType data[MAXSIZE]; int front; int rear; }CirclesQueue; /*循环队列初始化*/ int init(CirclesQueue *Q); /*入队*/ int enqueue(CirclesQueue *Q, DataType x); /*队满？*/ int isfull(CirclesQueue *Q); /*出队*/ int dequeue(CirclesQueue *Q, DataType *); /*队空*/ int isempty(CirclesQueue *Q); /*队长*/ int querylen(CirclesQueue *Q); /*打印队首元素*/ int printfront(CirclesQueue *Q); /*输出队列*/ void querylist(CirclesQueue *Q);

3.3  CirclesQueue.c文件代码

#include <stdio.h> #include "CirclesQueue.h" /*循环队列初始化*/ int init(CirclesQueue *Q) { Q->front =0; Q->rear = 0; return 0; } /*入队*/ int enqueue(CirclesQueue *Q, DataType x) { if(isfull(Q)) { printf("队列已满！\n"); return ; } Q->rear = (Q->rear+1) % MAXSIZE; Q->data[Q->rear] =x; return 0; } /*队满？*/ int isfull(CirclesQueue *Q) { return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0; } /*出队*/ int dequeue(CirclesQueue *Q, DataType *x) { if(isempty(Q)) { printf("队列为空！\n"); return ; } Q->front = (Q->front+1) % MAXSIZE; *x = Q->data[Q->front]; return 0; } /*队空*/ int isempty(CirclesQueue *Q) { return (Q->front == Q->rear) ? 1 : 0; } /*队列长度*/ int querylen(CirclesQueue *Q){ return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; } /*打印队首元素*/ int printfront(CirclesQueue *Q){ DataType a; if(isempty(Q)) { printf("队列为空！\n"); return ; }else { return Q->data[Q->front +1 %MAXSIZE]; } return 0; } /*输出队列*/ void querylist(CirclesQueue *Q) { int i; if (isempty(Q)) { printf("队列为空\n"); return; } i = (Q->front)%MAXSIZE; printf("队列："); do { printf("%d ",Q->data[i + 1 % MAXSIZE]); i = (i + 1) % MAXSIZE; } while (i != Q->rear); printf("\n"); } 

3.4  welcome.h文件代码

char welcome[] = "\n\ | .-.\n\ | / 、 .-.\n\ | / 、 / 、 .-. .-.\n\ +--/-------、-----/-----、-----/---、---/---、---/-、-/-、/、/---\n\ | / 、 / 、 / '-' '-' \n\ |/ '-' '-' \n\ ";

四、代码运行结果

 | .-. | / 、 .-. | / 、 / 、 .-. .-. +--/-------、-----/-----、-----/---、---/---、---/-、-/-、/、/--- | / 、 / 、 / '-' '-' |/ '-' '-' -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：1 队列已初始化！ -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：2 请输入要入队的元素x=10 元素x=10已入队 -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：2 请输入要入队的元素x=20 元素x=20已入队 -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：2 请输入要入队的元素x=30 元素x=30已入队 -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：6 队列长度为【3】 -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：7 队首元素为【10】 -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：8 队列：10 20 30 -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：5 队列未满！ -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：3 确定要出队（出队会将删除对首元素, y or n, n）？y 队首元素【10】已出队！ -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：3 确定要出队（出队会将删除对首元素, y or n, n）？y 队首元素【20】已出队！ -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：3 确定要出队（出队会将删除对首元素, y or n, n）？y 队首元素【30】已出队！ -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：4 队列为空！ -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：9 本程序为环形队列的演示程序，由黄彬森设计开发，本程序演示了环形队列功能！ -----------循环队列演示----------- 1. 初始化 2. 入队 3. 出队 4. 队空？ 5. 队满 6. 队列长度 7. 打印队首元素 8. 打印队列 9. 帮助 0. 退出 请选择（0~9）：0 -------------------------------- Process exited after 56.99 seconds with return value 0 请按任意键继续. . .

五、小结

        环形队列解决了队列存在资源浪费的问题，即当队列的尾指针指向存储空间的末尾时，如果队列的头指针还没有指向存储空间的起始位置，那么新加入队列的元素将被存储在存储空间的起始位置，这样就可以循环利用存储空间，避免了队列满的情况。

六、参考文献

【1】CSDN

【2】数据结构(C语言)