柚子快報(bào)邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)——循環(huán)隊(duì)列詳解
柚子快報(bào)邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)——循環(huán)隊(duì)列詳解
目錄
一、循環(huán)隊(duì)列的定義
二、 循環(huán)隊(duì)列的基本操作
三、循環(huán)隊(duì)列的實(shí)現(xiàn)?
1、循環(huán)隊(duì)列的定義
2、循環(huán)隊(duì)列的初始化?
3、循環(huán)隊(duì)列出隊(duì)?
4、循環(huán)隊(duì)列入隊(duì)?
5、隊(duì)列判空
6、 隊(duì)列判滿
7、取隊(duì)頭元素
8、輸出隊(duì)列?
9、求隊(duì)列長度?
四、完整代碼?
五、小結(jié)?
六、參考文獻(xiàn)
一、循環(huán)隊(duì)列的定義
定義：隊(duì)列主要有順序隊(duì)列，循環(huán)隊(duì)列，雙端隊(duì)列，優(yōu)先隊(duì)列。而當(dāng)中循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)。它也被稱為“環(huán)形緩沖器”。它只允許在一端進(jìn)行插入操作，即隊(duì)尾（rear），而在另一端進(jìn)行刪除操作，即隊(duì)頭 (front)，其操作表現(xiàn)基于FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。向隊(duì)列中插入新的數(shù)據(jù)元素稱為入隊(duì)，新入隊(duì)的元素就成為了隊(duì)列的隊(duì)尾元素。
特點(diǎn)：
循環(huán)隊(duì)列允許元素在隊(duì)尾插入，在隊(duì)頭刪除，同時(shí)遵循先進(jìn)先出原則。由于循環(huán)隊(duì)列是基于數(shù)組實(shí)現(xiàn)的，所以它的訪問速度很快，特別是在移動(dòng)元素時(shí)。如果需要大量添加和刪除元素，循環(huán)隊(duì)列比鏈表更有效率，因?yàn)樗恍枰l繁地移動(dòng)指針來訪問元素。不支持隨機(jī)訪問元素，因此不能像數(shù)組那樣直接訪問特定位置的元素。
二、 循環(huán)隊(duì)列的基本操作
1、初始化：這是創(chuàng)建一個(gè)空的順序隊(duì)列，需要設(shè)定隊(duì)首指針front和隊(duì)尾指針rear都指向同一個(gè)位置，一般初始都設(shè)置為0，即隊(duì)列為空。
2、元素入隊(duì)：也被稱為插入操作，是將一個(gè)新元素添加到隊(duì)列尾部的操作。
3、元素出隊(duì)：也被稱為刪除操作，是將隊(duì)列頭部的元素移除的操作。
4、求隊(duì)列長度：可以通過計(jì)算隊(duì)尾指針和隊(duì)首指針之差的值再加1來獲取當(dāng)前隊(duì)列的長度。
5、判斷是否為空：通過檢查隊(duì)首指針front和隊(duì)尾指針rear是否相等來判斷隊(duì)列是否為空。
6、判斷是否為滿：當(dāng)隊(duì)尾指針指向數(shù)組的最后一個(gè)位置時(shí)，下一個(gè)要插入的位置就是隊(duì)頭指針。
7、取隊(duì)頭：頭元素就是隊(duì)列中的第一個(gè)元素，可以通過返回隊(duì)首指針front的值來獲取。
8、輸出隊(duì)列：將隊(duì)列中元素通過while語句循環(huán)語句打印出來
三、循環(huán)隊(duì)列的實(shí)現(xiàn)?
1、循環(huán)隊(duì)列的定義
用一個(gè)數(shù)組來存儲隊(duì)列中的元素，用front作為隊(duì)頭指針，指向隊(duì)列的第一個(gè)元素，用rear作為隊(duì)尾指針，即指向隊(duì)列最后一個(gè)元素的下一個(gè)位置.
#define MAXSIZE 4
typedef int DataType;
typedef struct
{
DataType data[MAXSIZE];
int front;
int rear;
}CirclesQueue;
2、循環(huán)隊(duì)列的初始化?
循環(huán)隊(duì)列的初始化只需要將隊(duì)頭指針（front）和隊(duì)尾指針（rear）都初始化為0.
/*循環(huán)隊(duì)列初始化*/
int init(CirclesQueue *Q)
{
Q->front = Q->rear = 0;
return 0;
}
3、循環(huán)隊(duì)列出隊(duì)?
出隊(duì)前判斷隊(duì)列是否為空，如果為空，返回100002錯(cuò)誤信息，如果隊(duì)列不為空，將隊(duì)列的隊(duì)頭指針向前移動(dòng)一位，即將隊(duì)頭指針加1并對MAXSIZE取模，確保指針在數(shù)組范圍內(nèi)循環(huán)移動(dòng)，當(dāng)?shù)竭_(dá)數(shù)組末尾時(shí)，會回到數(shù)組的開頭。
/*出隊(duì)*/
int dequeue(CirclesQueue *Q, DataType *x)
{
if(isempty(Q))
{
printf("隊(duì)列為空！100002\n");
return 100002;
}
Q->front = (Q->front+1) % MAXSIZE;
*x = Q->data[Q->front];
return 0;
}
4、循環(huán)隊(duì)列入隊(duì)?
入隊(duì)前需要判斷隊(duì)列是否已經(jīng)滿了，如果隊(duì)列為滿，則不能入隊(duì)。反之，則將隊(duì)列的隊(duì)頭向前移動(dòng)一位，確保指針在數(shù)組范圍內(nèi)能夠循環(huán)移動(dòng)。具體來說，就是將當(dāng)前隊(duì)頭指針的值加1，然后對隊(duì)列的最大容量（MAXSIZE）取模來實(shí)現(xiàn)。
/*入隊(duì)*/
int enqueue(CirclesQueue *Q, DataType x)
{
if(isfull(Q))
{
printf("隊(duì)列已滿！100001\n");
return 100001;
}
Q->rear = (Q->rear+1) % MAXSIZE;
Q->data[Q->rear] = x;
return 0;
}
5、隊(duì)列判空
判斷循環(huán)隊(duì)列是否為空通過比較隊(duì)頭指針和隊(duì)尾指針是否相等來判斷，如果它們相等，說明隊(duì)列中沒有元素，反之則存在元素。?
/*隊(duì)空*/
int isempty(CirclesQueue *Q)
{
return (Q->front == Q->rear) ? 1 : 0;
}
6、 隊(duì)列判滿
判斷循環(huán)隊(duì)列是否為滿可以讓隊(duì)列的rear指針加1之后對MAXSIZE取模結(jié)果等于front指針，這時(shí)表明隊(duì)列已滿，反之則未滿。
/*隊(duì)滿？*/
int isfull(CirclesQueue *Q)
{
return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0;
}
7、取隊(duì)頭元素
想要獲取隊(duì)頭元素，首先需要判斷隊(duì)列是否為空，如果為空，返回錯(cuò)誤信息。不為空時(shí)，可以通過計(jì)算front加1后對MAXSIZE取模獲取隊(duì)首元素的位置。
/*取隊(duì)頭元素*/
int QueueFront(CirclesQueue *Q,DataType *x)
{
if(isempty(Q))
{
printf("隊(duì)列為空！100002\n");
return 100002;
}
*x = Q->data[(Q->front + 1) % MAXSIZE];
return 0;
8、輸出隊(duì)列?
輸出隊(duì)列前需要先判斷隊(duì)列是否為空，如果為空則輸出隊(duì)列為空，不為空時(shí)，將隊(duì)頭指針的值賦給i，并對最大容量MAXSIZE取模，再通過do-while循環(huán)來遍歷隊(duì)列中的元素，循環(huán)的內(nèi)部通過計(jì)算(i + 1 % MAXSIZE)來獲取下一個(gè)元素的索引，并輸出打印當(dāng)前元素，同時(shí)更新i的值，使其加1并對MAXSIZE取模，以便繼續(xù)遍歷隊(duì)列。
/*輸出隊(duì)列*/
void PrintQueue(CirclesQueue *Q){
int i;
if (isempty(Q))
{
printf("隊(duì)列為空！\n");
return;
}
i=(Q->front)%MAXSIZE; //確保i的值在0到MAXSIZE-1之間，以便在后續(xù)操作中作為數(shù)組索引使用
do
{
printf("%d、",Q->data[(i + 1 % MAXSIZE)]);
i=(i+1)%MAXSIZE;
}while(i!=Q->rear);
}
9、求隊(duì)列長度?
求循環(huán)隊(duì)列的長度可以通過計(jì)算隊(duì)列的尾指針（rear）和頭指針（front）之間的差值，加上最大容量(MAXSIZE)，然后對最大容量取模，得到隊(duì)列的實(shí)際長度。最后，將計(jì)算結(jié)果存儲在指針x所指向的位置，并返回0表示成功。
*獲取隊(duì)列長度*/
int getLength(CirclesQueue *Q,DataType *x) {
*x= (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
return 0;
}
四、完整代碼?
1、main.c
#include
#include "CirclesQueue.h"
int main(int argc, char* argv[])
{
CirclesQueue Q;
DataType x;
int cmd;
char yn;
do
{
printf("-----------循環(huán)隊(duì)列演示-----------\n");
printf(" 1. 初始化\n");
printf(" 2. 入隊(duì)\n");
printf(" 3. 出隊(duì)\n");
printf(" 4. 隊(duì)空？\n");
printf(" 5. 隊(duì)滿\n");
printf(" 6.取隊(duì)頭\n");
printf(" 7.輸出隊(duì)列\(zhòng)n");
printf(" 8.取長度\n");
printf(" 9.幫助\n");
printf(" 0. 退出\n");
printf(" 請選擇（0~6）：");
scanf("%d",&cmd);
switch(cmd)
{
case 1:
init(&Q);
printf("隊(duì)列已初始化！\n");
break;
case 2:
printf("請輸入要入隊(duì)的元素x=");
scanf("%d", &x);
if(!enqueue(&Q,x))
{
printf("元素x=%d已入隊(duì)\n", x);
}
break;
case 3:
printf("確定要出隊(duì)（出隊(duì)會將刪除對首元素, y or n, n）？");
flushall();
scanf("%c", &yn);
if(yn == 'y' || yn == 'Y')
{
if(!dequeue(&Q,&x))
{
printf("隊(duì)首元素【%d】已出隊(duì)！\n", x);
}
}
break;
case 4:
if(isempty(&Q))
{
printf("隊(duì)列為空！\n");
}
else{
printf("隊(duì)列不為空!\n");
}
break;
case 5:
if(isfull(&Q))
{
printf("隊(duì)列為滿！\n");
}
else{
printf("隊(duì)列未滿!\n");
}
break;
case 6:
if(!QueueFront(&Q,&x))
{
printf("隊(duì)首元素為【%d】！\n", x);
}
break;
case 7:
PrintQueue(&Q);
printf("\n");
break;
case 8:
if(!getLength(&Q,&x))
{
printf("隊(duì)列長度為【%d】！\n", x);
}
break;
case 9:
printf("本程序由zzb設(shè)計(jì)開發(fā),實(shí)現(xiàn)了循環(huán)隊(duì)列的入隊(duì)、出隊(duì)、取隊(duì)頭等操作\n");
}
}while(cmd!=0);
return 0;
}
2、?CirclesQueue.c
/*
CirclesQueue.c
*/
#include "CirclesQueue.h"
/*循環(huán)隊(duì)列初始化*/
int init(CirclesQueue *Q)
{
Q->front = Q->rear = 0;
return 0;
}
/*入隊(duì)*/
int enqueue(CirclesQueue *Q, DataType x)
{
if(isfull(Q))
{
printf("隊(duì)列已滿！100001\n");
return 100001;
}
Q->rear = (Q->rear+1) % MAXSIZE;
Q->data[Q->rear] = x;
return 0;
}
/*隊(duì)滿？*/
int isfull(CirclesQueue *Q)
{
return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0;
}
/*出隊(duì)*/
int dequeue(CirclesQueue *Q, DataType *x)
{
if(isempty(Q))
{
printf("隊(duì)列為空！100002\n");
return 100002;
}
Q->front = (Q->front+1) % MAXSIZE;
*x = Q->data[Q->front];
return 0;
}
/*隊(duì)空*/
int isempty(CirclesQueue *Q)
{
return (Q->front == Q->rear) ? 1 : 0;
}
/*取隊(duì)頭元素*/
int QueueFront(CirclesQueue *Q,DataType *x)
{
if(isempty(Q))
{
printf("隊(duì)列為空！100002\n");
return 100002;
}
*x = Q->data[(Q->front + 1) % MAXSIZE];
return 0;
}
/*輸出隊(duì)列*/
void PrintQueue(CirclesQueue *Q){
int i;
if (isempty(Q))
{
printf("隊(duì)列為空！\n");
return;
}
i=(Q->front)%MAXSIZE;
do
{
printf("%d、",Q->data[(i + 1 % MAXSIZE)]);
i=(i+1)%MAXSIZE;
}while(i!=Q->rear);
}
/*獲取隊(duì)列長度*/
int getLength(CirclesQueue *Q,DataType *x) {
*x= (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
return 0;
}
3、?CirclesQueue.h
/*
CirclesQueue.h
循環(huán)隊(duì)列
*/
#define MAXSIZE 4
typedef int DataType;
typedef struct
{
DataType data[MAXSIZE];
int front;
int rear;
}CirclesQueue;
/*循環(huán)隊(duì)列初始化*/
int init(CirclesQueue *Q);
/*入隊(duì)*/
int enqueue(CirclesQueue *Q, DataType x);
/*隊(duì)滿？*/
int isfull(CirclesQueue *Q);
/*出隊(duì)*/
int dequeue(CirclesQueue *Q, DataType *x);
/*隊(duì)空*/
int isempty(CirclesQueue *Q);
/*取隊(duì)頭元素*/
int QueueFront(CirclesQueue *Q,DataType *x);
/*輸出隊(duì)列*/
void PrintQueue(CirclesQueue *Q);
/*隊(duì)列長度*/
int getLength(CirclesQueue *Q,DataType *x);
4、運(yùn)行截圖?
五、小結(jié)?
1、循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)。它也被稱為“環(huán)形緩沖器”。它只允許在一端進(jìn)行插入操作，即隊(duì)尾（rear），而在另一端進(jìn)行刪除操作，即隊(duì)頭 (front)，其操作表現(xiàn)基于FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。
2、循環(huán)隊(duì)列的應(yīng)用范圍非常廣泛，比如線程池任務(wù)調(diào)度、消息隊(duì)列系統(tǒng)、緩沖區(qū)管理、廣度優(yōu)先搜索算法等應(yīng)用場景。
3、隊(duì)列滿時(shí)，無法再進(jìn)行插入操作；當(dāng)隊(duì)列空時(shí)，無法再進(jìn)行刪除操作。隊(duì)列的大小是固定的，一旦創(chuàng)建后不能改變。
?六、參考文獻(xiàn)
?
《數(shù)據(jù)結(jié)構(gòu)》(C語言版）李剛，劉萬輝.北京：高等教育出版社?，2017.? ?
《C語言程序設(shè)計(jì)》(第四版）譚浩強(qiáng). 北京：清華大學(xué)出版社，2014.
? CSDN 數(shù)據(jù)結(jié)構(gòu)-----循環(huán)隊(duì)列
?
?
?
?
?
柚子快報(bào)邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)——循環(huán)隊(duì)列詳解
參考鏈接
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Etsy手工藝品外貿(mào)
