《详解循环队栈》
目录：
循环队列的定义及其特点
循环队列的实现
完整Demo
运行截图
小结
参考文献
一、循环队列的定义及其特点
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。而循环队列是队列的一种特殊形式，循环队列（也被称为环形队列）是一种线性数据结构，其操作表现基于先进先出原则（FIFO），并且队尾被连接在队首之后形成一个循环。在循环队列固定大小，空间能够重复利用。
二、循环队列的实现
队列实现一般有两种数组队列和链式队列，数组队列在一般应用中都会将其头尾相连形成循环队列，因为普通的数组存在“假溢出的问题”。本文所讲述并实现的队列为没有头结点的循环队列。
1.结构体定义
本次顺序栈的代码中定义了队列最大容量，用于存储数据元素的指针，队头下标，队尾下标。
typedef int DataType;
typedef struct {
int maxSize;//队列最大容量
DataType* data;//数据指针
int front;//队头下标
int rear;//队尾下标
}CirclesQueue;
2.初始化
初始化时使用MaxSzie（最大容量）+ 1 * 单个DataType长度申请内存空间，同时将队头队尾下标指向0；此处加一是为了留出最后一个结点空间，用于避免队头队尾重合，头尾重合在循环队列里一般视为空队列，当然也可以另外定义一个flag标记来判断是否为满或空，这样就可以不用多申请一个结点，优化了内存占用。但本文的代码实现为什么不用呢？因为我懒得写。
/**
* @brief 循环队列初始化
*
* @param Q 循环队列指针
* @param MaxSize 队列最大长度
*
* @return 状态码：0为成功
**/
int initCirclesQueue(CirclesQueue* Q, int MaxSize) {
Q->data = (DataType*)malloc(sizeof(DataType) * (MaxSize + 1));
if (!Q->data) {
printf("%s", errorHint[0]);
return errorCode[0];
}
Q->maxSize = (MaxSize + 1);
Q->front = 0;
Q->rear = 0;
return 0;
}
3.入队
入队、出队操作比较简单，入队时先进行队列判满，如满即返回错误码，反之则将数据元素插入队尾，而后将队尾下标后移一位。此处需要注意的是要将队尾下标+1后对maxSize（队列最大容量）取余，避免下标溢出。
/**
* @brief 循环队列入队
*
* @param Q 循环队列指针
* @param x 入队数据元素
*
* @return 状态码：0为成功
**/
int enqueue(CirclesQueue* Q, DataType* x) {
int flag = isFullQueue(Q);
if (!flag) {
Q->data[Q->rear] = *x;
Q->rear = ((Q->rear + 1) % Q->maxSize);
return 0;
}
return flag;
}
4.出队
出队同入队一般，先进行队列判空，如空即返回错误码，反之则将传入的DataType指针指向队头所指的数据元素，而后将队头下标后移一位。此处需要注意的是要将队头下标+1后对maxSize（队列最大容量）取余，避免下标溢出。
/**
* @brief 循环队列出队
*
* @param Q 循环队列指针
* @param x 入队数据元素
*
* @return 状态码：0为成功
**/
int dequeue(CirclesQueue* Q, DataType* x) {
int flag = isEmptyQueue(Q);
if (!flag) {
*x = Q->data[Q->front];
Q->front = ((Q->front + 1) % Q->maxSize);
return 0;
}
return flag;
}
5.打印
打印时需先进行判空，为空即打印错误信息并返回错误码，反之则从队头下标开始遍历队列，直至队头下标+1 = 队尾下标。此处和出队一样需要注意循环中要将队头下标+1后对maxSize（队列最大容量）取余，避免下标溢出。
/**
* @brief 循环队列打印
*
* @param Q 循环队列指针
*
* @return 状态码：0为成功
**/
int printQueue(CirclesQueue* Q) {
int flag = isEmptyQueue(Q);
if (!flag) {
int coordinates = Q->front;
printf("循环队列：");
while (coordinates != Q->rear) {
printf(" %d", Q->data[coordinates]);
coordinates = ((coordinates + 1) % Q->maxSize);
}
printf("\n");
return 0;
}
return flag;
}
三、完整Demo
welcome.h（欢迎字符图案）：
char *welcome[] = {
" \n",
" 4&(\n",
" ` ~&&\\yM#1\n",
" ,_'Q!!NMW&\n",
" WCb 7N@4D Q%,,\n",
" PM'*MDk#M0p,\n",
" ]@J0&e~~4r' ,+bQEQ\n",
" F8I&#' _&B$$bW#&$\n",
" &0A1 L#DE&E~!Q&Q,\n",
" _=, ,#0RN1 _T@0$' ZN$Q. grNq5\n",
" ^ 'd ,0K0pK^ g*Q0g' #Q4p&,/g9X*&#,_/ (q\n",
" TA1 ,sDQWh4^ x&NM0` _ #FQ#K#fA# `*K#XWP~-\n",
" ^&p,wNMM0qD: /HE#EN' ..#g)~ '@NG0Qx, `=X*\n",
" ' '43$'hEk##m0D04f_g ~^ ~ `-00**0\n",
" =0#ONq2W0BF^#, _ p,,\n",
" ` ^''~ ~b'' **R3`\n",
" ow,F +#F~'\n",
" /-9! `\\ \n",
" R\n"
};
View Code
circlesQueue.h（结构体与函数声明）：
/*
CirclesQueue
*/
typedef int DataType;
typedef struct {
int maxSize;//队列最大容量
DataType* data;//数据指针
int front;//队头下标
int rear;//队尾下标
}CirclesQueue;
int initCirclesQueue(CirclesQueue* Q, int MaxSize);
int enqueue(CirclesQueue* Q, DataType* x);
int dequeue(CirclesQueue* Q, DataType* x);
int isFullQueue(CirclesQueue* Q);
int isEmptyQueue(CirclesQueue* Q);
int printQueue(CirclesQueue* Q);
View Code
circlesQueue.c（函数实现）：
#include
#include "circlesQueue.h"
#include
#include "error.h"
/**
* @brief 循环队列初始化
*
* @param Q 循环队列指针
* @param MaxSize 队列最大长度
*
* @return 状态码：0为成功
**/
int initCirclesQueue(CirclesQueue* Q, int MaxSize) {
Q->data = (DataType*)malloc(sizeof(DataType) * (MaxSize + 1));
if (!Q->data) {
printf("%s", errorHint[0]);
return errorCode[0];
}
Q->maxSize = (MaxSize + 1);
Q->front = 0;
Q->rear = 0;
return 0;
}
/**
* @brief 循环队列入队
*
* @param Q 循环队列指针
* @param x 入队数据元素
*
* @return 状态码：0为成功
**/
int enqueue(CirclesQueue* Q, DataType* x) {
int flag = isFullQueue(Q);
if (!flag) {
Q->data[Q->rear] = *x;
Q->rear = ((Q->rear + 1) % Q->maxSize);
return 0;
}
return flag;
}
/**
* @brief 循环队列出队
*
* @param Q 循环队列指针
* @param x 入队数据元素
*
* @return 状态码：0为成功
**/
int dequeue(CirclesQueue* Q, DataType* x) {
int flag = isEmptyQueue(Q);
if (!flag) {
*x = Q->data[Q->front];
Q->front = ((Q->front + 1) % Q->maxSize);
return 0;
}
return flag;
}
/**
* @brief 循环队列判满
*
* @param Q 循环队列指针
*
* @return 状态码：0为不为满
**/
int isFullQueue(CirclesQueue* Q) {
if (((Q->rear + 1) % Q->maxSize) == Q->front) {
printf("%s", errorHint[1]);
return errorCode[1];
}
return 0;
}
/**
* @brief 循环队列判空
*
* @param Q 循环队列指针
*
* @return 状态码：0为不为空
**/
int isEmptyQueue(CirclesQueue* Q) {
if (Q->rear == Q->front) {
printf("%s", errorHint[2]);
return errorCode[2];
}
return 0;
}
/**
* @brief 循环队列打印
*
* @param Q 循环队列指针
*
* @return 状态码：0为成功
**/
int printQueue(CirclesQueue* Q) {
int flag = isEmptyQueue(Q);
if (!flag) {
int coordinates = Q->front;
printf("循环队列：");
while (coordinates != Q->rear) {
printf(" %d", Q->data[coordinates]);
coordinates = ((coordinates + 1) % Q->maxSize);
}
printf("\n");
return 0;
}
return flag;
}
View Code
main.c（主函数）：
#include
#include
#include
#include "welcome.h"
#include "circlesQueue.h"
int main(int argc, char *argv[]) {
for (int i = 0; i < 19; i++) {
printf("%s", welcome[i]);
for (int j = 0; j <= 100000000; j++) {
for (int m; m <= 100000000; m++) {
;
}
}
}
int operate;
int maxSize;
char verify;
DataType data;
CirclesQueue Q;
printf("\n\n本应用程序为数据结构-循环队列演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n");
do {
printf("<---------------------------------------------------循环队列演示程序-------------------------------------------------->\n");
printf("0. 退出程序\n");
printf("1. 初始化循环队列\n");
printf("2. 打印循环队列\n");
printf("3. 入队\n");
printf("4. 出队\n");
printf("5. 帮助\n");
printf("请输入操作选项(0~5,0为退出)：");
scanf("%d", &operate);
// getchar();
switch (operate) {
case 1:
printf("请输入循环队列最大容量：");
scanf("%d", &maxSize);
// getchar();
if (!initCirclesQueue(&Q, maxSize)) {
printf("初始化完成\n\n");
}
break;
case 2:
printQueue(&Q);
break;
case 3:
printf("请输入入队数据：");
scanf("%d", &data);
if (!enqueue(&Q, &data)) {
printf("元素%d入队成功！\n\n", data);
}
break;
case 4:
while (1) {
printf("出队操作无法完全恢复是否要出栈？(y/n)：");
getchar();
scanf("%c", &verify);
if (verify == 89 || verify == 121) {
if (!dequeue(&Q, &data)) {
printf("元素%d出队成功！\n\n", data);
}
break;
} else if (verify == 78 || verify == 110) {
printf("出队操作已取消\n\n");
break;
}
}
break;
case 5:
printf("本应用程序为数据结构-循环队列演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n");
break;
case 0:
return 0;
break;
}
} while (operate != 0);
return 0;
}
View Code
error.h（错误信息）：
int errorCode[] = {100001, 100002, 100003, 100004, 100005};
char* errorHint[] = {
"ERROR[100001]：申请内存错误，初始化失败！\n\n",
"ERROR[100002]：循环队列已满！\n\n",
"ERROR[100003]：循环队列为空！\n\n",
"ERROR[100004]：无可撤销操作！\n\n",
"ERROR[100005]：申请内存错误，结点创建失败！\n\n",
};
View Code
四、运行截图
程序运行效果图
五、小结
队列的内容也是比较简单，只需注意在操作下标的时候要将下标对最大容量取余避免数组越界。
每周闲篇：本来是准备在这周将手上的这个APP结工的，又双叒叕因为计划外的N个状况打断了！莫名其妙还被劈头盖脸训了一顿，上次通话中压根没提材料细则吧？怎么又变成我的问题了？怎么老是有人喜欢把问题搞复杂？还推卸责任？
六、参考文献
王海艳等.《数据结构（C语言）》第二版[M].北京:人民邮电出版社,2020:10~14.