關于隊列的基本定義已經在[第2章棧和隊列以及串](http://blog.csdn.net/u013595419/article/details/50516508#t3)中說到了，與[棧](http://blog.csdn.net/u013595419/article/details/50518427)類似，同樣有使用順序結構存儲的隊列（這里簡稱順序隊列）和鏈式結構存儲的隊列（ 這里簡稱鏈隊列）。 ## 一. 順序隊列 ### 1.1定義 隊列的順序實現是指分配一塊連續的存儲單元用于存放隊列中的元素，并附設兩個指針front和rear分別指示頭元素和隊尾元素。設隊頭指針指向隊頭元素的位置，隊尾指針指向隊尾元素的下一個位置。 隊列的順序存儲類型則可以描述為： ~~~ #define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int front,rear; }SqQueue; ~~~ 這里對順序隊列的判斷條件進行說明。 > - 隊空條件：Q.front==Q.rear==0 > - 隊滿條件：> ~~Q.rear==MaxSize~~ 這里應當注意到，上述判斷隊滿條件實際是不正確的，比如當front指向隊尾元素，而rear的值剛好等于MaxSize。 此時從data[0]到data[MaxSize?2]的所有元素中，均沒有存儲任何元素，但是根據上述判斷條件卻“已滿”，造成“假溢出”。 為了解決這個問題，常見的有兩種解決方法。 > 1. 將隊列元素向前“平移”重新占用0至rear-front-1的空間 > 1. 將隊列看成首尾相連的循環隊列 因為平移會浪費大量的無用時間，因此一般使用循環隊列解決判斷是否隊滿的問題。 ## 二.循環隊列 ### 2.1定義 循環隊列將一個順序隊列“臆造”成一個環狀的空間，即把存儲隊列元素的表從邏輯上看成一個環，物理上依舊使用順序存儲結構。 在引入循環隊列的同時，也引入判斷隊列是否為空或滿的三種常見方法。 **1). 犧牲一個單元來區分隊空和隊滿** > - 隊空條件：Q.front==Q.rear > - 隊滿條件：(Q.rear+1)%MaxSize==Q.front > - 隊列中元素的個數：(Q.rear-Q.front+MaxSize)%MaxSize **2). 增設表示元素個數的數據成員size** > 隊空條件：Q.size==0 隊滿條件：Q.size=MaxSize 隊列中元素的個數：Q.size **3). 增設數據成員標志tag** > 隊空條件：Q.tag==0&&Q.front==Q.rear 隊滿條件：Q.tag==1&&Q.front==Q.rear ### 2.2基本操作 初始化操作，完成對隊首指針和隊尾指針的復位操作。 ~~~ void InitQueue(SqQueue* Q) { Q->front=0; Q->rear=0; } ~~~ 入隊操作，因為隊列中規定隊尾指針指向隊尾元素的下一個位置，因此在入隊后需對隊尾指針自增1。 ~~~ int EnQueue(SqQueue* Q, ElemType x) { if((Q->rear+1)%MaxSize==Q->front){ return -1; } Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%MaxSize; return 0; } ~~~ 出隊操作，如果隊空則返回-1；否則返回數據元素。 ~~~ int DeQueue(SqQueue* Q, ElemType* x) { if(Q->rear==Q->front){ return -1; } *x=Q->data[Q->front]; Q->front=(Q->front+1)%MaxSize; return 0; } ~~~ 判斷隊列是否為空，若為空則返回0；否則返回-1。 ~~~ int QueueEmpty(SqQueue* Q) { if(Q->rear==Q->front){ return 0; }else{ return -1; } } ~~~ ## 三.鏈隊列 ### 3.1定義 采用單鏈表結構存儲的隊列稱為鏈隊列。它同時帶有指向隊頭結點的指針點和指向隊尾結點的尾結點，一般為了方便在隊頭取出元素和在隊尾中添加元素，故一般采用待有頭節點的單鏈表。 如圖所示：  這里對鏈隊列的判斷條件進行說明。 > - 隊空條件：Q.front==Q.rear 隊列的鏈式存儲類型則可以描述為： ~~~ typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; typedef struct{ LNode *front; LNode *rear; }LinkQueue; ~~~ 鏈隊特別適合元素數據變化比較大和需要同時使用多個隊列的情形，因為不會存在由于隊滿而溢出的問題。 ### 3.2基本操作 初始化操作。 ~~~ void InitQueue(LinkQueue *Q) { Q->front=(LNode*)malloc(sizeof(LNode)); Q->rear=Q->front; Q->front->next=NULL; } ~~~ 判斷隊列是否為空，如若為空，則返回0；否則返回-1。 ~~~ int QueueEmpty(LinkQueue *Q) { if(Q->front==Q->rear){ return 0; }else{ return -1; } } ~~~ 入隊操作，創建新的結點，然后插入隊尾 ~~~ void EnQueue(LinkQueue *Q, ElemType x) { LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=x; Q->rear->next=s; Q->rear=s; } ~~~ 出隊操作，如果隊列為空，則返回-1；若不為空，則返回0。 ~~~ int DeQueue(LinkQueue *Q, ElemType *x) { LNode *p; if(Q->front==Q->rear){ return -1; } p=Q->front->next; *x=p->data; Q->front->next=p->next; if(Q->rear==p){ Q->rear=Q->front; } free(p); return 0; } ~~~ ## 四.雙端隊列 ### 4.1定義 雙端隊列是允許兩端都可以進行入隊和出隊操作的隊列。 在雙端隊列進隊時，前端進的元素排列在隊列中后端進的元素的前面，后端進的元素排列在隊列中前端進的元素的后面。在雙端隊列出隊時，無論前端還是后端出隊，先出的元素排列在后出的元素的前面。如下圖所示：  輸出受限的雙端隊列：允許在一端進行插入和刪除，但在另一端只允許插入的雙端隊列 稱為輸出受限的雙端隊列。如下圖所示：  輸入受限的雙端隊列：允許在一端進行插入和刪除，但在另一端只允許刪除的雙端隊列，而如果限定雙端隊列從某個端點插入的元素只 能從該端點刪除，則該雙端隊列就蛻變為兩個棧底相鄰接的棧了。如下圖所示：