隊(duì)列（queue）

隊(duì)列（queue）：只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。
隊(duì)列是一種先進(jìn)先出（First In First Out）的線性表，簡稱FIFO。
允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭

1、抽象數(shù)據(jù)類型

ADT 隊(duì)列(Queue) Data同線性表。元素具有相同的類型，相鄰元素具有前驅(qū)和后繼關(guān)系。 OperationInitQueue(*Q)： 初始化操作，建立一個空隊(duì)列Q。DestroyQueue(*Q)： 若隊(duì)列Q存在，則銷毀它。ClearQueue(*Q)： 將隊(duì)列 Q 清空。QueueEmpty(Q)： 若隊(duì)列Q為空，送回true,否則退回false。GetHead(Q, *e)： 若隊(duì)列Q存在且非空，用e返因隊(duì)列Q的隊(duì)頭元素。EnQueue(*Q,e)： 若隊(duì)列Q存在，插入新元素e到隊(duì)列Q中并成為隊(duì)尾元素。DeQueue(*Q, *e)： 刪除隊(duì)列Q中隊(duì)頭元素，并用e返回其值。QueueLength(Q)： 送回隊(duì)列Q的元素個教。 endADT

2、循環(huán)隊(duì)列（順序隊(duì)列）

下圖為隊(duì)列的假溢出示意圖，即下標(biāo) 0 和 1 的位置還是空閑的，然而指向隊(duì)尾的指針rear已經(jīng)出現(xiàn)了數(shù)組越界的錯誤。為了避免這種情況，一般順序隊(duì)列也指循環(huán)隊(duì)列。

循環(huán)隊(duì)列：采用環(huán)狀順序表來存放隊(duì)列元素，并用兩個指針，其中 front 指針指向隊(duì)列的隊(duì)頭元素，rear指針指向隊(duì)尾元素的下一個位置，往隊(duì)列中加進(jìn)或取出元素時分別改變這兩個變量的計(jì)數(shù)。當(dāng)頭尾指針（front / rear）指向隊(duì)列尾的元素（下標(biāo)：QueueSize-1）時，其加1操作的結(jié)果是指向向量的下界0。

2.1 特殊情況的判定——空\滿隊(duì)列

??當(dāng)隊(duì)列為空或者滿的時候都會出現(xiàn) front == rear 的情況，即無法通過條件 front == rear 來判別隊(duì)列是”空”還是”滿”。

解決這個問題的方法至少有三種：
　　① 另設(shè)一布爾變量或標(biāo)志變量以區(qū)別隊(duì)列的空和滿；
　　② 保留一個元素空間。約定入隊(duì)前，測試對尾指針 rear 在循環(huán)意義下加1后是否等于 front，若相等則認(rèn)為隊(duì)滿（注意：rear所指的單元始終為空），此時判空條件仍是 front == rear，判滿條件改變；
　　③使用一個計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)（即隊(duì)列長度）。
　　
　　下文針對②進(jìn)行討論。

2.2 實(shí)現(xiàn)

隊(duì)列空的條件：
???? ? ? ???? ? ? front == rear
隊(duì)列滿的條件：
???? ? ? （rear + 1）% QueueSize == front
??其中，rear為指向隊(duì)尾元素的下一位置的指針，front 為指向隊(duì)頭元素的指針。QueueSize為隊(duì)列的最大長度。

通用計(jì)算隊(duì)列長度公式：
???? （rear - front + QueueSize） % QueueSize

代碼實(shí)現(xiàn)

注意：傳參的形式傳址還是傳實(shí)體對象，實(shí)體對象需要用實(shí)心點(diǎn)來指向成員，所以判斷條件寫成 Q.front==Q.rear；傳址則為Q->front == Q->rear

#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存儲空間初始分配量 */typedef int Status; typedef int QElemType; /* QElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int *//* 循環(huán)隊(duì)列的順序存儲結(jié)構(gòu) */ typedef struct {QElemType data[MAXSIZE];int front; /* 頭指針 */int rear; /* 尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個位置 */ }SqQueue;Status visit(QElemType c) {printf("%d ",c);return OK; }/* 初始化一個空隊(duì)列Q */ Status InitQueue(SqQueue *Q) {Q->front=0;Q->rear=0;return OK; }/* 將Q清為空隊(duì)列 */ Status ClearQueue(SqQueue *Q) {Q->front=Q->rear=0;return OK; }/* 若隊(duì)列Q為空隊(duì)列,則返回TRUE,否則返回FALSE */ Status QueueEmpty(SqQueue Q) { if(Q.front==Q.rear) /* 隊(duì)列空的標(biāo)志 */return TRUE;elsereturn FALSE; }/* 返回Q的元素個數(shù)，也就是隊(duì)列的當(dāng)前長度 */ int QueueLength(SqQueue Q) {return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; }/* 若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR */ Status GetHead(SqQueue Q,QElemType *e) {if(Q.front==Q.rear) /* 隊(duì)列空 */return ERROR;*e=Q.data[Q.front];return OK; }/* 若隊(duì)列未滿，則插入元素e為Q新的隊(duì)尾元素 */ Status EnQueue(SqQueue *Q,QElemType e) {if ((Q->rear+1)%MAXSIZE == Q->front) /* 隊(duì)列滿的判斷 */return ERROR;Q->data[Q->rear]=e; /* 將元素e賦值給隊(duì)尾 */Q->rear=(Q->rear+1)%MAXSIZE;/* rear指針向后移一位置， *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK; }/* 若隊(duì)列不空，則刪除Q中隊(duì)頭元素，用e返回其值 */ Status DeQueue(SqQueue *Q,QElemType *e) {if (Q->front == Q->rear) /* 隊(duì)列空的判斷 */return ERROR;*e=Q->data[Q->front]; /* 將隊(duì)頭元素賦值給e */Q->front=(Q->front+1)%MAXSIZE; /* front指針向后移一位置， *//* 若到最后則轉(zhuǎn)到數(shù)組頭部 */return OK; }/* 從隊(duì)頭到隊(duì)尾依次對隊(duì)列Q中每個元素輸出 */ Status QueueTraverse(SqQueue Q) { int i;i=Q.front;while((i+Q.front)!=Q.rear){visit(Q.data[i]);i=(i+1)%MAXSIZE;}printf("\n");return OK; }int main() {Status j;int i=0,l;QElemType d;SqQueue Q;InitQueue(&Q);printf("初始化隊(duì)列后，隊(duì)列空否？%u(1:空 0:否)\n",QueueEmpty(Q));printf("請輸入整型隊(duì)列元素(不超過%d個),-1為提前結(jié)束符: ",MAXSIZE-1);do{/* scanf("%d",&d); */d=i+100;if(d==-1)break;i++;EnQueue(&Q,d);}while(i<MAXSIZE-1);printf("隊(duì)列長度為: %d\n",QueueLength(Q));printf("現(xiàn)在隊(duì)列空否？%u(1:空 0:否)\n",QueueEmpty(Q));printf("連續(xù)%d次由隊(duì)頭刪除元素,隊(duì)尾插入元素:\n",MAXSIZE);for(l=1;l<=MAXSIZE;l++){DeQueue(&Q,&d);printf("刪除的元素是%d,插入的元素:%d \n",d,l+1000);/* scanf("%d",&d); */d=l+1000;EnQueue(&Q,d);}l=QueueLength(Q);printf("現(xiàn)在隊(duì)列中的元素為: \n");QueueTraverse(Q);printf("共向隊(duì)尾插入了%d個元素\n",i+MAXSIZE);if(l-2>0)printf("現(xiàn)在由隊(duì)頭刪除%d個元素:\n",l-2);while(QueueLength(Q)>2){DeQueue(&Q,&d);printf("刪除的元素值為%d\n",d);}j=GetHead(Q,&d);if(j)printf("現(xiàn)在隊(duì)頭元素為: %d\n",d);ClearQueue(&Q);printf("清空隊(duì)列后, 隊(duì)列空否？%u(1:空 0:否)\n",QueueEmpty(Q));return 0; }

3、隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈隊(duì)列）及實(shí)現(xiàn)

3.1 鏈隊(duì)列定義

隊(duì)頭指針( front )指向鏈隊(duì)列的頭結(jié)點(diǎn)，而隊(duì)尾指針( rear )指向終端結(jié)點(diǎn)。非空鏈隊(duì)列如下所示。

當(dāng)隊(duì)列為空時，front和rear都指向頭結(jié)點(diǎn)。

結(jié)構(gòu)如下：

#include "stdio.h"/* QElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */ typedef int QElemType;typedef struct QNode /* 結(jié)點(diǎn)結(jié)構(gòu) */ {QElemType data;struct QNode *next; } QNode,*QueuePtr;typedef struct /* 隊(duì)列的鏈表結(jié)構(gòu) */ {QueuePtr front,rear; /* 隊(duì)頭、隊(duì)尾指針 */ } LinkQueue;int main() {return 0; }

3.2 入隊(duì)操作

步驟：
1、根據(jù)圖，我們先創(chuàng)建一個結(jié)點(diǎn)s，QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
2、然后給s的data域賦值e，指針域next賦值null。s->data=e;s->next=NULL; 目的就是讓它成為新任隊(duì)尾元素。
3、前任隊(duì)尾元素呢？直接讓它的指針域指向s就行了。Q->rear->next=s;
4、別忘了把隊(duì)尾指針重新指向新任隊(duì)尾s。Q->rear=s;

3.3 出隊(duì)操作

一般情況：

如果鏈隊(duì)列只剩下一個元素的時候，出隊(duì)則如下圖：

3.4 實(shí)現(xiàn)

#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 20 /* 存儲空間初始分配量 */typedef int Status; typedef int QElemType; /* QElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */typedef struct QNode /* 結(jié)點(diǎn)結(jié)構(gòu) */ {QElemType data;struct QNode *next; }QNode,*QueuePtr;typedef struct /* 隊(duì)列的鏈表結(jié)構(gòu) */ {QueuePtr front,rear; /* 隊(duì)頭、隊(duì)尾指針 */ }LinkQueue;Status visit(QElemType c) {printf("%d ",c);return OK; }/* 構(gòu)造一個空隊(duì)列Q */ Status InitQueue(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));if(!Q->front)exit(OVERFLOW);Q->front->next=NULL;return OK; }/* 銷毀隊(duì)列Q */ Status DestroyQueue(LinkQueue *Q) {while(Q->front){Q->rear=Q->front->next;free(Q->front);Q->front=Q->rear;}return OK; }/* 將Q清為空隊(duì)列 */ Status ClearQueue(LinkQueue *Q) {QueuePtr p,q;Q->rear=Q->front;p=Q->front->next;Q->front->next=NULL;while(p){q=p;p=p->next;free(q);}return OK; }/* 若Q為空隊(duì)列,則返回TRUE,否則返回FALSE */ Status QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear)return TRUE;elsereturn FALSE; }/* 求隊(duì)列的長度 */ int QueueLength(LinkQueue Q) { int i=0;QueuePtr p;p=Q.front;while(Q.rear!=p){i++;p=p->next;}return i; }/* 若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR */ Status GetHead(LinkQueue Q,QElemType *e) { QueuePtr p;if(Q.front==Q.rear)return ERROR;p=Q.front->next;*e=p->data;return OK; }/* 插入元素e為Q的新的隊(duì)尾元素 */ Status EnQueue(LinkQueue *Q,QElemType e) { QueuePtr s=(QueuePtr)malloc(sizeof(QNode));if(!s) /* 存儲分配失敗 */exit(OVERFLOW);s->data=e;s->next=NULL;Q->rear->next=s; /* 把擁有元素e的新結(jié)點(diǎn)s賦值給原隊(duì)尾結(jié)點(diǎn)的后繼，見圖中① */Q->rear=s; /* 把當(dāng)前的s設(shè)置為隊(duì)尾結(jié)點(diǎn)，rear指向s，見圖中② */return OK; }/* 若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR */ Status DeQueue(LinkQueue *Q,QElemType *e) {QueuePtr p;if(Q->front==Q->rear)return ERROR;p=Q->front->next; /* 將欲刪除的隊(duì)頭結(jié)點(diǎn)暫存給p，見圖中① */*e=p->data; /* 將欲刪除的隊(duì)頭結(jié)點(diǎn)的值賦值給e */Q->front->next=p->next;/* 將原隊(duì)頭結(jié)點(diǎn)的后繼p->next賦值給頭結(jié)點(diǎn)后繼，見圖中② */if(Q->rear==p) /* 若隊(duì)頭就是隊(duì)尾，則刪除后將rear指向頭結(jié)點(diǎn)，見圖中③ */Q->rear=Q->front;free(p);return OK; }/* 從隊(duì)頭到隊(duì)尾依次對隊(duì)列Q中每個元素輸出 */ Status QueueTraverse(LinkQueue Q) {QueuePtr p;p=Q.front->next;while(p){visit(p->data);p=p->next;}printf("\n");return OK; }int main() {int i;QElemType d;LinkQueue q;i=InitQueue(&q);if(i)printf("成功地構(gòu)造了一個空隊(duì)列!\n");printf("是否空隊(duì)列？%d(1:空 0:否) ",QueueEmpty(q));printf("隊(duì)列的長度為%d\n",QueueLength(q));EnQueue(&q,-5);EnQueue(&q,5);EnQueue(&q,10);printf("插入3個元素(-5,5,10)后,隊(duì)列的長度為%d\n",QueueLength(q));printf("是否空隊(duì)列？%d(1:空 0:否) ",QueueEmpty(q));printf("隊(duì)列的元素依次為：");QueueTraverse(q);i=GetHead(q,&d);if(i==OK)printf("隊(duì)頭元素是：%d\n",d);DeQueue(&q,&d);printf("刪除了隊(duì)頭元素%d\n",d);i=GetHead(q,&d);if(i==OK)printf("新的隊(duì)頭元素是：%d\n",d);ClearQueue(&q);printf("清空隊(duì)列后,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);DestroyQueue(&q);printf("銷毀隊(duì)列后,q.front=%u q.rear=%u\n",q.front, q.rear);return 0; }

總結(jié)

以上是生活随笔為你收集整理的数据结构——队列（queue）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。