详解循环队列

目录

循环队列的概念

 循环队列的结构和基本运算

 循环队列的操作

循环队列的结构代码

初始化

入队

出队

队空

队满

队内元素的个数

获取对内头元素

输出队列

完整代码

效果截图​编辑

小结

参考文献

---

 

循环队列的概念

循环队列是一种特殊类型的队列数据结构，也被称为”唤醒缓冲器“。它在数组的基础上实现了循环利用空间的功能。在循环队列中，队尾和队头之间形成了一个循环，当队尾指针“追上”队头指针时，队列不再继续增长，而是继续利用之前出队的空间。

 循环队列的结构和基本运算

1. 队头指针(front)：指向队头元素的位置。
2. 队尾指针(rear)：指向队尾元素的下一个位置，也就是即将插入新元素的位置。

3. 入队操作会将元素插入到队尾指针所指向的位置，并将队尾指针后移。当队列满时，入队操作会失败。

4. 出队操作会删除队头元素，并将队头指针后移。当队列为空时，出队操作会失败。

5. 当队列为空时，front指针和rear指针同时指向下标为0的位置，因此循环队列为空的条件为front == rear
6. 由于循环队列需要预留一个空间来区分队列为空和队列满的状态，队列满的条件为rear + 1 == head

 循环队列的操作

循环队列的结构代码

#define MAXSIZE 100
 
typedef int DataType;
 
typedef struct
{
	DataType data[MAXSIZE];
	int front;
	int rear;
}CirclesQueue;

初始化

int init(CirclesQueue *Q)
{
	return 0;
    Q->front = Q->rear = 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 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;
}

队空

当队列为空时，front指针和rear指针同时指向下标为0的位置，因此循环队列为空的条件为front == rear

/*判断队是否空*/
int isempty(CirclesQueue *Q)
{
	return (Q->front == Q->rear) ? 1 : 0;
}

队满

队列满的条件为rear + 1 == head,尾指针像后移动一位，遇到头指针了。

/*判断队是否满？*/
int isfull(CirclesQueue *Q)
{
	return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0;
}

队内元素的个数

按照正常逻辑，计算队列长度只需要队尾减去队头即可，但是由于是循环队列，可能存在front大，rear小运算得出负数的情况，所以必须通过加上MAXSIZE再取余保证队列的大小为正数。

/* 获取队列长度：循环队列：若rear在前方，则长度为rear-front+MAXSIZE，否则为rear-front */    
int getLength(CirclesQueue *Q) {  
    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; /
} 

获取对内头元素

/* 获取对内头元素 */ 
DataType getFront(CirclesQueue* Q) {  
    int i;
    i = (Q -> front) %MAXSIZE;
    return Q -> data[(i + 1 % MAXSIZE)];
}

输出队列

/* 输出队列内容 */ 
void printQueue(CirclesQueue *Q) {
    int i;
    if (isempty(Q)) {  
        printf("Queue is empty.\n");  
        return;  
    }  
    i = (Q -> front) %MAXSIZE;
    do{
        printf(" %d",Q -> data[(i + 1 % MAXSIZE)]);
        i = (i+1) %MAXSIZE;
    }while(i != Q -> rear);
}

完整代码

/*
   main.c
*/
#include <stdio.h>
#include "CirclesQueue.h"
#include <string.h>
#include <stdlib.h>
 
int main(int argc, char* argv[])
{
	CirclesQueue Q;
	DataType x;
	int cmd;
	char yn;
int result;
    char welcome[] = "\n\
    ★╭－－－－－－╮☆☆☆☆☆☆╭－－－－－－╮\n\
    ★╰╮八方来财╭╯◢ █ ◣◢ █ ◣╰╮期末高分╭╯\n\
    ★╭╯╰－－－╯╰╮██自  由██╭╯╰－－－╯╰╮\n\
    ★║◢ █ ◣◢ █ ◣║◥ █快乐█ ◤║◢ █ ◣◢ █ ◣║\n\
    ★║██████████║　◥ ██ ◤　║██████████║ \n\
    ★║◥ █真心█ ◤║　        ║◥ █祝福█ ◤║\n\
    ★║　◥ ██ ◤　║☆ ☆ ☆ ☆ ☆║　◥ ██ ◤　║\n\
    ★║　 ◥ ◤　 ║☆ 事事如意☆ ║ ◥ ◤　║\n\
         \\   ☆ 祝我 . 也祝你！☆\n\n";
	int i = 0; 
	int m = 0; 
	int n = 0;
    for(i=0;i<strlen(welcome);i++)
	{
		printf("%c",welcome[i]);
		for(m=0;m<10000;m++)
			for(n=0;n<1000;n++)
			{
				;
			}
	}
	printf("\n\n\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）？");
			getchar();
			scanf("%c", &yn);
 
			if(yn == 'y' || yn == 'Y')
			{
				if(!dequeue(&Q,&x))
				{
					printf("队首元素【%d】已出队！\n", x);
				}
			}
			break;
	    case 4:
			if(isempty(&Q)) printf("队列为空！\n");
			else printf("队列不为空！\n");
			break;
		case 5:
			if(isfull(&Q)) printf("队列已满！\n");
			else printf("队列还没有满！\n");
			break;
		case 6:
			printf("队列的长度：%d\n",getLength(&Q));
			break;
		case 7:
		    printf("获取对内头元素: %d\n", getFront(&Q));  
            break;
		case 8:
			printf("输出队列：");
			printQueue(&Q);
			printf("\n");
			break;
		case 9:
		    printf("本程序为循环队列的演示程序，由王路平设计开发！\n");
		    break;
		}
 
	}while(cmd!=0);
 
 
	return 0;
}
/*
	CirclesQueue.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);
 
/* 输出队列内容 */ 
void printQueue(CirclesQueue *Q);
 
/* 获取队列长度 */ 
int getLength(CirclesQueue *Q);
 
/* 获取对内头元素 */
DataType getFront(CirclesQueue* Q);
/*
	CirclesQueue.c
*/
#include "CirclesQueue.h"
 
/*循环队列初始化*/
int init(CirclesQueue *Q)
{
	Q->front = 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 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 isfull(CirclesQueue *Q)
{
	return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0;
}
 
 
/* 获取队列长度:循环队列：若rear在前方，则长度为rear-front+MAXSIZE，否则为rear-front   */ 
int getLength(CirclesQueue *Q) {  
    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; 
} 
 
/* 获取对内头元素 */ 
DataType getFront(CirclesQueue* Q) {  
    int i;
    i = (Q -> front) %MAXSIZE;
    return Q -> data[(i + 1 % MAXSIZE)];
}
/* 输出队列内容 */ 
void printQueue(CirclesQueue *Q) {
    int i;
    if (isempty(Q)) {  
        printf("Queue is empty.\n");  
        return;  
    }  
    i = (Q -> front) %MAXSIZE;
    do{
        printf(" %d",Q -> data[(i + 1 % MAXSIZE)]);
        i = (i+1) %MAXSIZE;
    }while(i != Q -> rear);
}
 

效果截图

小结

本次学习了循环队列，了解了循环队列的入队，出队，队空，队满等基本操作，明白了循环队列的优点在于其高效的插入和删除操作，但需要注意的是在实现时需要处理满队列和空队列的情况。此外，循环队列也需要一些技巧来扩展其容量，例如使用多级循环队列等。

参考文献

循环队列详解_Forward♞的博客-CSDN博客

队列之循环队列详解（C语言版）-CSDN博客