数据结构环形队列

只看该作者 · 2025-2-19 20:00

环形队列的定义
      环形队列是一种队列数据结构，它与普通队列相似，但在内部实现上有一个特殊之处：队列的尾部指针连接到队列的头部，形成一个循环。

环形队列的特点
      环形队列是一种具有固定容量的队列，其特点在于尾指针与头指针相连，形成循环，从而实现元素的循环利用。这使得环形队列在高效的入队和出队操作方面表现出色，同时最大程度地利用存储空间。

环形队列的运算
入队：向队列尾部插入元素，尾指针向后移动。如果队列已满，入队操作将失败。

出队：从队列头部移除元素，头指针向后移动。如果队列为空，出队操作将失败。

查看队头元素：获取队列头部元素的值，但不移除元素。

判空：检查队列是否为空。

判满：检查队列是否已满。

队列大小：返回队列中元素的数量。

清空队列：将队列清空，使其变为空队列。

销毁队列：释放队列的内存和资源，回收队列所占用的空间。

环形队列的实现
初始化

/*循环队列初始化*/
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[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("队列为空！100002\n");
return 100002;
}
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("队列为空！100002\n");
return 100002;
}
else
{
return Q->data[Q->front + 1 % MAXSIZE];
}

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 + 1 % MAXSIZE]);
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[i]);
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[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("队列为空！100002\n");
return 100002;
}
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("队列为空！100002\n");
return 100002;
}
else
{
return Q->data[Q->front + 1 % MAXSIZE];
}

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 + 1 % MAXSIZE]);
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[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);
小结
      环形队列是一种有限容量的队列，它能高效地处理入队和出队操作，同时充分利用存储空间，适合循环使用有限资源的应用。需要特别注意队列已满和队列为空的情况，以避免数据溢出或损失。

只看该作者 · 2025-3-4 19:38

在多任务或中断环境下，对环形队列的操作需要考虑线程安全，避免数据竞争

只看该作者 · 2025-3-4 20:34

预先分配数组空间，避免动态内存分配。

2万 · 2025-3-9 19:25

环形队列使用两个指针，一个用于指示队列的头部（下一个元素将被移除的位置），另一个用于指示队列的尾部（下一个元素将被添加的位置）。

只看该作者 · 2025-3-9 20:46

环形队列特别适用于需要高效、连续数据处理的场合

只看该作者 · 2025-3-9 22:30

#include <stdbool.h>
#include <stdint.h>

typedef struct {
uint8_t *buffer;
uint16_t head;
uint16_t tail;
uint16_t size;
} CircularQueue;

void CircularQueue_Init(CircularQueue *q, uint8_t *buf, uint16_t buf_size) {
q->buffer = buf;
q->head = 0;
q->tail = 0;
q->size = buf_size;
}

bool CircularQueue_Enqueue(CircularQueue *q, uint8_t data) {
if ((q->tail + 1) % q->size == q->head) {
      return false;
}
q->buffer[q->tail++] = data;
if (q->tail >= q->size) {
      q->tail = 0;
}
return true;
}

bool CircularQueue_Dequeue(CircularQueue *q, uint8_t *data) {
if (q->head == q->tail) {
      return false;
}
*data = q->buffer[q->head++];
if (q->head >= q->size) {
      q->head = 0;
}
return true;
}

uint16_t CircularQueue_GetLength(CircularQueue *q) {
if (q->tail >= q->head) {
      return q->tail - q->head + 1;
} else {
      return q->size - (q->head - q->tail);
}
}