演算法隊列

1. 數據結構與演算法-隊列

隊列是一種特殊的線性表，特殊之處在於它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

隊列這個概念非常好理解。你可以把它想像成排隊買票，先來的先買，後來的人只能站末尾，不允許插隊。先進者先出，這就是典型的「隊列」。

我們知道，CPU 資源是有限的，任務的處理速度與線程個數並不是線性正相關。相反，過多的線程反而會導致 CPU 頻繁切換，處理性能下降。所以，線程池的大小一般都是綜合考慮要處理任務的特點和硬體環境，來事先設置的。當我們向固定大小的線程池中請求一個線程時，如果線程池中沒有空閑資源了，這個時候線程池如何處理這個請求？是拒絕請求還是排隊請求？各種處理策略又是怎麼實現的呢？

看完下面隊列C語言實現，相信你會多少有些了解

隊列只支持兩個基本操作：入隊 enqueue()，放一個數據到隊列尾部；出隊 dequeue()，從隊列頭部取一個元素。
隊列跟棧一樣，也是一種操作受限的線性表數據結構。

隊列跟棧一樣，也是一種抽象的數據結構。它具有先進先出的特性，支持在隊尾插入元素，在隊頭刪除元素。
跟棧一樣，隊列可以用數組來實現，也可以用鏈表來實現。用數組實現的棧叫作順序棧，用鏈表實現的棧叫作鏈式棧。同樣，用數組實現的隊列叫作順序隊列，用鏈表實現的隊列叫作鏈式隊列。

隨著不停地進行入隊、出隊操作， front 和 rear 都會持續往後移動。當 rear 移動到最右邊，即使數組中還有空閑空間，也無法繼續往隊列中添加數據了。同時也不好判斷隊滿條件，可以使用循環隊列來實現

循環隊列，顧名思義，它長得像一個環。原本數組是有頭有尾的，是一條直線。現在我們把首尾相連，扳成了一個環。

經過推算，可以發現:
隊空 Q.rear==Q.front。
隊滿 (Q.rear+1)%MAXSIZE==Q.front。

注意，當隊列滿時，圖中的 Q.rear 指向的位置實際上是沒有存儲數據的。所以，循環隊列會浪費一個數組的存儲空間。

1.初始化空隊列

2.清空隊列

4.判斷隊滿

5.入隊

6.出隊

7.獲取隊列當前元素個數

8.若隊列不空,則用e返回Q的隊頭元素,並返回OK,否則返回ERROR

9.從隊頭到隊尾依次對隊列的每個元素數組

10.主函數中驗證

輸出結果

1.初始化

2.銷毀

3.置空

4.判斷隊列是否為空

5.獲取元素個數

6.入隊

7.出隊

8.獲取隊頭元素

9.遍歷隊列

驗證

輸出

2. 數據結構與演算法——隊列之循環隊列

隊列是一種特殊的線性表，特殊之處在於它只允許在表的前端進行刪除操作，在表的後端進行插入操作。插入操作的端稱為隊尾，刪除操作的端為對頭。
隊列核心是 先進先出 。
隊列又可因為存儲方式不同分為順序存儲和鏈式存儲。今天就先講一下順序存儲結構—— 循環隊列 。
建立循環隊列結構，必須為其靜態或者動態申請一片 連續的存儲空間 ，並且設置兩個指針管理，一個是隊頭指針front，指向對頭元素。另外一個是隊尾指針rear，指向下一個入隊元素的存儲位置。如圖所示

2.初始化

3.將隊列清空

6 若隊列不空,則用e返回Q的隊頭元素,並返回OK,否則返回ERROR

3. 數據結構與演算法-隊列

同樣是線性表，隊列也有類似線性表的各種操作，不同的就是插入數據只能在隊尾進行，刪除數據只能在隊頭進行。

線性表有順序存儲和鏈式存儲，棧是線性表，所以有這兩種存儲方式。同樣，隊列作為一種特殊的線性表，也同樣存在這兩種存儲方式。

我們假設一個隊列有n個元素，則順序存儲的隊列需建立一個大於n的數組，並把隊列的所有元素存儲在數組的前n個單元，數組下標為0的一端即是隊頭。所謂的入隊列操作，其實就是在隊尾追加一個元素，不需要移動任何元素，因此時間復雜度為 。

與棧不同的是，隊列元素的出列是在隊頭，即下標為0的位置，那也就意味著，隊列中的所有元素都得向前移動，以保證隊列的隊頭，也就是下標為0的位置不為空，此時時間復雜度為 。

可有時想想，為什麼出隊列時一定要全部移動呢，如果不去限制隊列的元素必須存儲在數組的前n個單元這一條件，出隊的性能就會大大增加。也就是說，隊頭不需要一定在下標為0的位置，

為了避免當只有一個元素時，隊頭和隊尾重合使處理變得麻煩，所以引入兩個指針，front指針指向隊頭元素，rear指針指向隊尾元素的下一個位置，這樣當front等於rear時，此隊列不是還剩一個元素，而是空隊列。

假設是長度為5的數組，初始狀態，空隊列列如圖所示，front與rear指針均指向下標為0的位置。然後入隊a1、a2、a3、a4，front指針依然指向下標為0位置，而rear指針指向下標為4的位置。

出隊a1、a2，則front指針指向下標為2的位置，rear不變，如圖4-12-5的左圖所示，再入隊a5，此時front指針不變，rear指針移動到數組之外。嗯？數組之外，那將是哪裡？如下圖的右圖所示。

假設這個隊列的總個數不超過5個，但目前如果接著入隊的話，因數組末尾元素已經佔用，再向後加，就會產生數組越界的錯誤，可實際上，我們的隊列在下標為0和1的地方還是空閑的。我們把這種現象叫做「假溢出」。

所以解決假溢出的辦法就是後面滿了，就再從頭開始，也就是頭尾相接的循環。我們把隊列的這種頭尾相接的順序存儲結構稱為循環隊列。

如果將rear的指針指向下標為0的位置，那麼就不會出現指針指向不明的問題了，如下圖所示。

接著入隊a6，將它放置於下標為0處，rear指針指向下標為1處，如下圖的左圖所示。若再入隊a7，則rear指針就與front指針重合，同時指向下標為2的位置，如下圖的右圖所示。

由於rear可能比front大，也可能比front小，所以盡管它們只相差一個位置時就是滿的情況，但也可能是相差整整一圈。

所以若隊列的最大尺寸為QueueSize，那麼隊列滿的條件是(rear+1)%QueueSize==front（取模「%」的目的就是為了整合rear與front大小為一圈問題）。比如上面這個例子，QueueSize=5，上圖的左圖中front=0，而rear=4，(4+1)%5=0，所以此時隊列滿。

再比如圖下圖中的，front=2而rear=1。(1+1)%5=2，所以此時隊列也是滿的。

而對於下圖，front=2而rear=0，(0+1)%5=1，1≠2，所以此時隊列並沒有滿。

另外，當rear>front時，此時隊列的長度為rear-front。

但當rear<front時，，隊列長度分為兩段，一段是QueueSize-front，另一段是0+rear，加在一起，隊列長度為rear-front+QueueSize。因此通用的計算隊列滿隊公式為：

單是順序存儲，若不是循環隊列，演算法的時間性能是不高的，但循環隊列又面臨著數組可能會溢出的問題，所以我們還需要研究一下不需要擔心隊列長度的鏈式存儲結構。

隊列的鏈式存儲結構，其實就是線性表的單鏈表，只不過它只能尾進頭出而已，我們把它簡稱為鏈隊列。為了操作上的方便，我們將隊頭指針指向鏈隊列的頭結點，而隊尾指針指向終端結點。

空隊列時，front和rear都指向頭結點。

鏈隊列的結構為：

初始化一個空隊列

入隊操作時，其實就是在鏈表尾部插入結點，如圖所示。

出隊操作時，就是頭結點的後繼結點出隊，將頭結點的後繼改為它後面的結點，若鏈表除頭結點外只剩一個元素時，則需將rear指向頭結點，如圖所示。

對於循環隊列與鏈隊列的比較，可以從兩方面來考慮，從時間上，其實它們的基本操作都是常數時間，即都為O(1)的，不過循環隊列是事先申請好空間，使用期間不釋放，而對於鏈隊列，每次申請和釋放結點也會存在一些時間開銷，如果入隊出隊頻繁，則兩者還是有細微差異。對於空間上來說，循環隊列必須有一個固定的長度，所以就有了存儲元素個數和空間浪費的問題。而鏈隊列不存在這個問題，盡管它需要一個指針域，會產生一些空間上的開銷，但也可以接受。所以在空間上，鏈隊列更加靈活。

總的來說，在可以確定隊列長度最大值的情況下，建議用循環隊列，如果你無法預估隊列的長度時，則用鏈隊列。

棧和隊列也都可以通過鏈式存儲結構來實現，實現原則上與線性表基本相同如圖所示。

4. 隊列初始化 入隊列和出隊列的演算法

#include <iostream.h>
#include <stdlib.h>
void main()
{

}

#define Status bool
#define ElemType int
typedef struct list{
ElemType data;
struct list *next;
struct list *pre;
}*CLQueue;

Status InitCLQueue(CLQueue &rear)
{
CLQueue q = (CLQueue )malloc(sizeof(struct list));
rear = q;
rear->next = rear->pre = rear;
return true;
}

Status EnCLQueue(CLQueue &rear, ElemType x)
{
CLQueue q = (CLQueue)malloc(sizeof(struct list));
q->data = x;
if(rear->next == rear)
{
rear->next = rear->pre =q;
q->next = q->pre = rear;
rear = q;
}
else
{
q->pre = rear->next;
q->next = rear->next->next;
rear->next->next->pre = q;
rear->next->next = q;
}
return true;
}

Status DeCLQueue(CLQueue &rear, ElemType &x)
{
if(rear->next == rear) return false;
rear = rear->pre;
CLQueue q = rear->next;
q->next->pre = rear;
rear->next = q->next;
free(q);
return true;
}