数据结构（循环队列）循环队列|数据结构

本文概述

复杂
插入循环队列
在循环队列中插入元素的算法
C功能
从循环队列中删除元素的算法
算法
C功能
菜单驱动程序在循环队列上实现所有操作

就线性队列而言, 删除和插入只能分别在前端和后端进行。
考虑下图所示的队列。

文章图片
上图所示的队列已完全填满, 由于后方== max-1变为true的条件, 因此无法再插入任何元素。
但是, 如果我们删除队列前端的2个元素, 由于条件after = max -1仍然成立, 我们仍然不能插入任何元素。
【数据结构（循环队列）】这是线性队列的主要问题, 尽管数组中有可用空间, 但是不能在队列中插入更多元素。这仅仅是内存浪费, 我们需要克服这个问题。

文章图片
解决此问题的方法之一是循环队列。在循环队列中, 第一个索引紧接在最后一个索引之后。你可以想到一个循环队列, 如下图所示。

文章图片
当front = -1和back = max-1时, 循环队列将已满。循环队列的实现类似于线性队列的实现。只有在插入和删除的情况下实现的逻辑部分才与线性队列中的逻辑部分不同。
复杂时间复杂度

Front	O(1)
Rear	O(1)
enQueue()	O(1)
deQueue()	O(1)

插入循环队列在队列中插入元素的情况有三种。

如果（rear + 1）％maxsize = front, 则队列已满。在这种情况下, 会发生溢出, 因此无法在队列中执行插入。
如果Rear！= max-1, 则将Rear增加到mod（maxsize）, 并将新值插入队列的后端。
如果front！= 0且Rear = max-1, 则意味着队列未满, 因此, 将Rear的值设置为0并在其中插入新元素。

在循环队列中插入元素的算法

步骤1：IF（REAR + 1）％MAX = FRONT写“ OVERFLOW”转到步骤4 [IF结束]
步骤2：如果FRONT = -1且REAR = -1, 则SET FRONT = REAR = 0 ELSE如果REAR = MAX-1且FRONT！ = 0 SET REAR = 0 ELSE SET REAR =（REAR +1）％MAX [IF结束]
步骤3：SET QUEUE [REAR] = VAL
步骤4：退出

C功能

void insert(int item, int queue[]){ if((rear+1)%maxsize == front) {printf("\nOVERFLOW"); return; } else if(front == -1 & & rear == -1) {front = 0; rear = 0; } else if(rear == maxsize -1 & & front != 0) {rear = 0; } else {rear = (rear+1)%maxsize; } queue[rear] = item; }

从循环队列中删除元素的算法要从循环队列中删除元素, 我们必须检查以下三个条件。

如果front = -1, 则队列中没有元素, 因此将发生下溢情况。
如果队列中只有一个元素, 在这种情况下, 条件Rear = front成立, 因此, 两个条件都设置为-1, 并且队列被完全删除。
如果front = max -1, 则从前端删除该值, 并且front的值设置为0。
否则, 将front的值增加1, 然后删除前端的元素。

算法

第1步：如果FRONT = -1, 则输入“ UnderFLOW”转到第4步[IF的结尾]
步骤2：SET VAL = QUEUE [FRONT]
步骤3：如果前=后置=前= -1其他如果中=最大-1前= 0其他前=前+ 1 [IF的末尾] [IF的末尾]
步骤4：退出

C功能

void delete(){ if(front == -1 & rear == -1) {printf("\nUNDERFLOW\n"); return; } else if(front == rear) {front = -1; rear = -1; } else if(front == maxsize -1){front = 0; } else front = front + 1; }

菜单驱动程序在循环队列上实现所有操作

#include< stdio.h> #include< stdlib.h> #define maxsize 5void insert(); void delete(); void display(); int front = -1, rear = -1; int queue[maxsize]; void main (){ int choice; while(choice != 4) { printf("\n*************************Main Menu*****************************\n"); printf("\n=================================================================\n"); printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n"); printf("\nEnter your choice ?"); scanf("%d", & choice); switch(choice){case 1:insert(); break; case 2:delete(); break; case 3:display(); break; case 4:exit(0); break; default: printf("\nEnter valid choice??\n"); } }}void insert(){ int item; printf("\nEnter the element\n"); scanf("%d", & item); if((rear+1)%maxsize == front) {printf("\nOVERFLOW"); return; } else if(front == -1 & & rear == -1) {front = 0; rear = 0; } else if(rear == maxsize -1 & & front != 0) {rear = 0; } else {rear = (rear+1)%maxsize; } queue[rear] = item; printf("\nValue inserted "); }void delete(){ int item; if(front == -1 & rear == -1) {printf("\nUNDERFLOW\n"); return; } else if(front == rear) {front = -1; rear = -1; } else if(front == maxsize -1){front = 0; } else front = front + 1; } void display(){int i; if(front == -1)printf("\nCircular Queue is Empty!!!\n"); else{i = front; printf("\nCircular Queue Elements are : \n"); if(front < = rear){while(i < = rear)printf("%d %d %d\n", queue[i++], front, rear); }else{while(i < = maxsize - 1)printf("%d %d %d\n", queue[i++], front, rear); i = 0; while(i < = rear)printf("%d %d %d\n", queue[i++], front, rear); }}}

输出：

**********Main Menu**********=============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?1Enter the element1Value inserted **********Main Menu**********=============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?1Enter the element2Value inserted **********Main Menu**********=============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?1Enter the element3Value inserted **********Main Menu**********=============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?3Circular Queue Elements are : 123**********Main Menu**********=============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?2**********Main Menu**********=============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?1Enter the element4Value inserted **********Main Menu**********=============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?3Circular Queue Elements are : 234**********Main Menu**********=============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?1Enter the element1OVERFLOW**********Main Menu**********=============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?4