概念

隊列（queue）是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作。

和棧一樣，隊列是一種操作受限制的線性表。隊列是先進先出（FIFO）的。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

隊列和棧非常相似，棧有入棧和出棧兩個基本操作操作，隊列也有兩個基本操作：入隊（enqueue），把數據放到隊尾。出隊（dequeue）,從隊頭取出一個數據。

隊列出隊和入隊的時間復雜度都是O(1)。

順序隊列

用數組實現的隊列叫做順序隊列。

// 用數組實現的隊列
public class ArrayQueue {
    // 數組：arr，數組大小：len
    private String[] arr;
    private int len = 0;
    // front 隊頭下標，rear 隊尾下標
    private int front = 0;
    private int rear = 0;


    // 創建一個數組
    public ArrayQueue(int length) {
        items = new String[length];
        n = length;
    }

    // 入隊
    public boolean enqueue(String item) {
        // 隊列已滿
        if (rear == len) return false;
        items[rear] = item;
        rear++;
        return true;
    }

    // 出隊
    public String dequeue() {
        // 隊列為空
        if (front == rear) return null;
        String result = items[front];
        front++;
        return result;
    }
}

隊列有兩個指針一個是front指向隊頭，一個是rear指向隊尾。

如a、b、c、d、e 入列后，隊頭指針指向是的下標為0的位置，隊尾指針指向的是下標為6的位置。

然后不斷進行出列和入列的操作，兩個指針也不斷往后移動，當隊尾指針到達最右邊的位置，就算數組中還有一個空閑的空間，但也沒有辦法繼續向隊列中加數據了。

回想數組空間不足，進行擴容，遷移數據的操作。

同理在這里也要對隊列進行數據搬遷，只要在入列的時候判斷一下 （rear == len ）隊列尾是已經到最后的話就進行數據遷移，然后重新計算兩個指針的指向，然后再入列就可以了。

鏈式隊列

用鏈表實現的隊列叫做鏈式隊列。同樣需要兩個指針，隊頭指向第一個節點，隊尾指向最后一個節點。

入隊：rear -> next = newnode , rear = rear -> next

出隊：front = front-> next

循環隊列

用數組實現隊列的時候，如果 rear == len ，就需要進行數據遷移操作。

為了避免進行數據遷移操作，可以用循環隊列來解決。

循環隊列首尾相接。

隊空條件：front == rear

隊滿條件：(rear + 1) % len = front

確定好上面的兩個條件，代碼實現就很容易了。

阻塞隊列

在隊列的基礎上增加了阻塞操作。

隊列為空，隊頭取數據阻塞，等隊列中有數據才會返回數據。

隊列已滿，隊尾插數據阻塞，等隊列中有空閑位置再插入數據。

其實這就是「生產者 - 消費者模型」，還可以通過配置多個「消費者」來對應一個「生產者」。

并發隊列

在多線程情況下，會有多個線程訪問隊列，會存在線程安全問題。

線程安全的隊列叫做并發隊列。

通過在 enqueue() 、dequeue() 加鎖來實現。