文章出處：極客時間《數據結構和算法之美》-作者：王爭。該系列文章是本人的學習筆記。

1 隊列

隊列：可以想象成排隊買票，先來的人先買，后到的人站在隊尾。先進者先出，這就是隊列。

隊列的操作：入隊（enqueue）、出隊（dequeue）。入隊：在隊列尾部添加一個元素。出隊：在隊列頭部移除一個元素。

2 隊列的實現

隊列的實現可以用數組，也可以用鏈表，分別稱為順序隊列、鏈式隊列。

2.1 基于數組的實現

public class ArrayQueue {private String[] items;private int n = 0;private int head;private int tail;public ArrayQueue(int capacity){this.n = capacity;items = new String[this.n];head = tail = 0;}/*** 在隊尾插入一個元素* @param value* @return*/public boolean enqueue(String value){if(tail >=n) return false;//超出容量items[tail] = value;tail++;return true;}/*** 出隊：從對頭刪除一個元素* @return*/public String dequeue(){if(head==tail) return null;String ret = items[head];head++;return ret;} }

舉個 例子，畫畫圖可以發現，隨著入隊、出隊操作，head、tail指針不斷向右移動，極端情況是head、tail都在右邊，即使數組有空間，也不能再做入隊操作。

如何解決這個問題呢？我們可以在不能入隊的時候，將head、tail之間的元素，拷貝到[0,tail-head]之間。

public boolean enqueue(String value){if(tail==n){if(head==0) return false;for(int i=head;i<tail;i++){items[i-head] = items[i];}tail = tail-head;head = 0;}items[tail] = value;tail++;return true;}

在這個版本實現中，出隊操作時間復雜度是O(1)，入隊時間復雜度是多少呢？直覺認為平均時間復雜度應該還是O(1)。無證明。

2.2 基于鏈表的實現

需要兩個指針head、tail分別指向隊列頭部、隊列尾部。入隊的時候tail.next=new node，tail=tail.next；出隊的時候，head=head.next。
代碼

3 循環隊列

3.1 數組實現

在2.1基于數組實現的隊列中有數據遷移的操作。如果是一個循環隊列就不需要數據遷移操作了。循環隊列是指它長的像一個環，原本隊列頭部、和隊列尾部形成一條直線。現在把隊列頭部和隊列尾部扳成了一個環。

圖中隊列長度為8，head=4，tail=7。
當插入a的時候，items[7]=a,tail=(tail+1)%8=0。
當插入b的時候，items[0]=b,tail=(tail+1)%8=1。

通過這樣的方式，就避免了數據搬移的工作。
循環隊列的實現重點是判斷什么時候為空，什么時候隊列已滿，不能再添加數據。
在一般隊列中，當head=tail的時候，隊列為空。循環隊列也是。
在一般隊列中，當tail=n的時候，隊列已滿，不能再添加數據。循環隊列需要多舉幾個例子，畫圖總結規律。

圖中head=4，tail=3，數組長度len=8。如果再插入數據tail=(tail+1)%8=head，tail=head，這與隊列為空的條件重復了。所以，我們在(tail+1)%8=head的時候后，就不再插入數據。也就是說items[tail]是沒有值的。
代碼

3.2 基于鏈表實現

基于鏈表實現就更簡單了，將tail.next=head即可。

4 并發隊列和阻塞隊列

阻塞隊列就是在隊列的基礎上加了阻塞的操作。例如當隊列為空的時候，在隊列頭部取數據的時候會進入阻塞狀態，直到隊列中有數據的時候才返回數據。當隊列滿了的時候，往隊列中插入數據的時候會進入阻塞狀態，直到隊列中有空間存儲數據的時候才入隊成功，然后返回。

其實，這就是一個生產者-消費者模型。

這種生產者消費者模型可以有效協調生產速度和消費速度。例如當生產者生產速度過快，消費者來不及消費的情況下，生產者很快會填滿隊列，生產者進入阻塞狀態，只有當消費者消費之后，有了剩余空間，生產者才能繼續生產。

不僅如此，我們開可以分配1個生產者，多個消費者。

在多線程情況下就會存在線程安全問題。如何實現一個線程安全的隊列呢？線程安全的隊列被稱為并發隊列。用CAS，可以實現一個高效地安全隊列。

5 隊列應用在有限資源的場景下

隊列主要應用在資源有限的場景下。例如數據庫連接池里的連接是有限的，服務器每秒能處理的請求量是有限的。

當服務器的請求池中有空閑的服務線程的時候，我們希望公平地處理每一個到訪的請求。這個時候我們將請求加入到隊列中。當服務器的請求池中有空閑服務線程的時候，從隊列取請求，進行服務。

隊列的實現有兩種方式：數組和鏈表。鏈表實現的隊列可以無限擴容，可以接受無限的請求，但這容易引起內存溢出。數組實現的隊列只能接受一定個數的請求，超出數量，直接返回無法訪問。但是隊列大小的設定需要權衡用戶體驗以及服務器的內存大小。

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。