数据结构环形队列
环形队列的定义环形队列是一种队列数据结构，它与普通队列相似，但在内部实现上有一个特殊之处：队列的尾部指针连接到队列的头部，形成一个循环。
环形队列的特点
环形队列是一种具有固定容量的队列，其特点在于尾指针与头指针相连，形成循环，从而实现元素的循环利用。这使得环形队列在高效的入队和出队操作方面表现出色，同时最大程度地利用存储空间。
环形队列的运算
入队：向队列尾部插入元素，尾指针向后移动。如果队列已满，入队操作将失败。
出队：从队列头部移除元素，头指针向后移动。如果队列为空，出队操作将失败。
查看队头元素：获取队列头部元素的值，但不移除元素。
判空：检查队列是否为空。
判满：检查队列是否已满。
队列大小：返回队列中元素的数量。
清空队列：将队列清空，使其变为空队列。
销毁队列：释放队列的内存和资源，回收队列所占用的空间。
环形队列的实现
初始化
/*循环队列初始化*/
int init(CirclesQueue *Q)
{
Q->front =0;
Q->rear = 0;
return 0;
}
入队
/*入队*/
int enqueue(CirclesQueue *Q, DataType x)
{
if(isfull(Q))
{
printf("队列已满！100001\n");
return 100001;
}
Q->rear = (Q->rear+1) % MAXSIZE;
Q->data =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("队列为空！100002\n");
return 100002;
}
Q->front = (Q->front+1) % MAXSIZE;
*x = Q->data;
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("队列为空！100002\n");
return 100002;
}
else
{
return Q->data;
}
return 0;
}
输出队列
/*输出队列*/
void querylist(CirclesQueue *Q)
{
int i;
if (isempty(Q))
{
/* code */
printf("队列为空\n");
return;
}
i = (Q->front) % MAXSIZE;
printf("队列：");
do
{
printf("%d", Q->data);
i = (i + 1) % MAXSIZE;
} while (i != Q->rear);
printf("\n");
}
运行结果截图
完整Demo
main.c
#include <stdio.h>
#include "CirclesQueue.c"
#include "welcome.h"
int main(int argc, char *argv[])
{
CirclesQueue Q;
DataType x, a, len;
int cmd,i, m, n;
char yn;
for (i = 0; i < strlen(welcome); i++)
{
printf("%c", welcome);
for (m = 0; m < 2000; m++)
for (n = 0; n < 2000; 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~8）：");
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;
}
CirclesQueue.c
/*
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("队列已满！100001\n");
return 100001;
}
Q->rear = (Q->rear + 1) % MAXSIZE;
Q->data = 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("队列为空！100002\n");
return 100002;
}
Q->front = (Q->front + 1) % MAXSIZE;
*x = Q->data;
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("队列为空！100002\n");
return 100002;
}
else
{
return Q->data;
}
return 0;
}
/*输出队列*/
void querylist(CirclesQueue *Q)
{
int i;
if (isempty(Q))
{
/* code */
printf("队列为空\n");
return;
}
i = (Q->front) % MAXSIZE;
printf("队列：");
do
{
printf("%d", Q->data);
i = (i + 1) % MAXSIZE;
} while (i != Q->rear);
printf("\n");
}
CirclesQueue.h
/*
CirclesQueue.h
循环队列
*/
#include <stdio.h>
#define MAXSIZE 100
typedef int DataType;
typedef struct
{
DataType data;
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);
小结
环形队列是一种有限容量的队列，它能高效地处理入队和出队操作，同时充分利用存储空间，适合循环使用有限资源的应用。需要特别注意队列已满和队列为空的情况，以避免数据溢出或损失。
页:
[1]