面試官讓手寫隊列，差點沒寫出來

前言

棧和隊列是一對好兄弟，前面我們介紹過一篇棧的文章(棧，不就後進先出)，棧的機制相對簡單，後入先出，就像進入一個狹小的山洞，山洞隻有一個出入口，隻能後進先出(在外面的先出去，堵在裡面先進去的就有點倒黴)。而隊列就好比是一個隧道，後面的人跟着前面走，前面人先出去(先入先出)。日常的排隊就是隊列運轉形式的一個描述！

棧是一種喜新厭舊的資料結構，來了新的就會處理新的把老的先停滞在這(我們找人、約人辦事最讨厭這種人)，隊列就是大公無私的一種資料結構，排隊先來先得，講究順序性，是以這種資料結構在程式設計、中間件等都非常廣泛的應用，例如消息隊列、FIFO磁盤排程、二叉樹層序周遊、BFS寬度優先搜尋等等。

隊列的核心理念就是：先進先出！

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

隊列介紹

我們設計隊列時候可以選擇一個标準，這裡就拿力扣622設計循環隊列作為隊列設計的标準。

隊頭front：删除資料的一端。

隊尾rear： 插入資料的一端。

對于數組，從數組後面插入更容易，數組前面插入較困難，是以一般用數組實作的隊列隊頭在數組前面，隊尾在數組後面；而對于連結清單，插入删除在兩頭分别進行那麼頭部(前面)删除尾部插入最友善的選擇。

實作方法：

• MyCircularQueue(k): 構造器，設定隊列長度為 k 。
• Front: 從隊首擷取元素。如果隊列為空，傳回 -1 。
• Rear: 擷取隊尾元素。如果隊列為空，傳回 -1 。
• enQueue(value): 向循環隊列插入一個元素。如果成功插入則傳回真。
• deQueue(): 從循環隊列中删除一個元素。如果成功删除則傳回真。
• isEmpty(): 檢查循環隊列是否為空。
• isFull(): 檢查循環隊列是否已滿。

普通隊列

按照上述的介紹，我們很容易知道數組實作的方式。用數組模拟表示隊列。要考慮初始化，插入，問題。

在這個普通隊列一些操作需要注意的有：

初始化：數組的front和rear都指向0. (front和rear下标相等的時候說明隊列為空)

入隊：隊不滿，數組不越界，先隊尾位置傳值，再隊尾下标+1(隊尾rear實際上超前一位，為了區分空隊列情況)

出隊：隊不空，先取隊頭位置元素，在隊頭+1。

循環隊列(數組實作)

針對上述的問題。有個較好的解決方法！就是對已經申請的(數組)記憶體重複利用。這就是我們所說的循環隊列。循環隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列裡，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環隊列，我們能使用這些空間去存儲新的值。

數組實作的循環隊列就是在邏輯上作修改。因為我們隊列中隻需要front和rear兩個指針。rear在邏輯上在後面，front在邏輯上是在前面的，但實際上它們不一定誰在前誰在後，在計算距離的時候需要給rear先補上數組長度減去front，然後求餘即可。

初始化：數組的front和rear都指向0. 這裡需要注意的是：front和rear位于同一個位置時候，證明隊列裡面是空的。還有在這裡我具體實作時候将數組申請大了一個位置空出來，防止隊列滿的情況又造成front和rear在同一個位置。

入隊：隊不滿，先隊尾位置傳值，再

rear=(rear + 1) % maxsize;

出隊：隊不空，先取隊頭位置元素，

front=(front + 1)% maxsize;

這裡出隊入隊名額相加如果遇到最後需要轉到頭位置，這裡直接+1求餘找到位置(相比判斷是否在最後更加簡潔)，其中maxsize是數組實際大小。

是否為空：

return rear == front;

大小：

return (rear+maxsize-front)%maxsize;

這裡很容易了解，一張圖就能解釋清楚，無論是front實際在前在後都能滿足要求。

這裡面有幾個大家需要注意的，就是名額相加如果遇到最後需要轉到頭的話。可以判斷是否到數組末尾位置。也可以直接+1求餘。其中maxsize是數組實際大小。

具體實作：

public class MyCircularQueue {
    private int data[];// 數組容器
    private int front;// 頭
    private int rear;// 尾
    private int maxsize;// 最大長度
    public MyCircularQueue(int k) {
        data = new int[k+1];
        front = 0;
        rear = 0;
        maxsize = k+1;
    }

    public boolean enQueue(int value)  {
        if (isFull())
            return  false;
        else {
            data[rear] = value;
            rear=(rear + 1) % maxsize;
        }
        return  true;
    }

    public boolean deQueue() {
        if (isEmpty())
            return false;
        else {
            front=(front+1)%maxsize;
        }
        return  true;
    }

    public int Front() {
        if(isEmpty())
            return -1;
        return data[front];
    }

    public int Rear() {
        if(isEmpty())
            return -1;
        return data[(rear-1+maxsize)%maxsize];
    }

    public boolean isEmpty() {
        return rear == front;
    }

    public boolean isFull() {
        return (rear + 1) % maxsize == front;
    }
}           

循環隊列(連結清單實作)

對于連結清單實作的隊列，要根據先進先出的規則考慮頭和尾的位置

我們知道隊列是先進先出的，對于連結清單，我們能采用單連結清單盡量采用單連結清單，能友善盡量友善，同時還要兼顧效率。使用連結清單大概有兩個實作方案：

方案一 如果隊列頭設在連結清單尾，隊列尾設在連結清單頭。那麼隊尾進隊插入在連結清單頭部插入沒問題，容易實作，但是如果隊頭删除在連結清單尾部進行，如果不設定尾指針要周遊到隊尾，但是設定尾指針删除需要将它前驅節點需要雙向連結清單，都挺麻煩的。

方案二如果隊列頭設在連結清單頭，隊列尾設在連結清單尾，那麼隊尾進隊插入在連結清單尾部插入沒問題(用尾指針可以直接指向next)，容易實作，如果隊頭删除在連結清單頭部進行也很容易，就是我們前面常說的頭節點删除節點。

是以我們最終采取的是方案2的帶頭節點、帶尾指針的單連結清單!

主要操作為：

初始化：設立一個頭結點，是front和rear都先指向它。

return rear == front;

或者自定義維護len判斷

return len==0

大小：節點front周遊到rear的個數，或者自定義維護len直接傳回(這裡并沒實作)。

實作代碼：

public class MyCircularQueue{
     class node {
        int data;// 節點的結果
        node next;// 下一個連接配接的節點
        public node() {}
        public node(int data) {
            this.data = data;
        }
    }
    node front;//相當于head 帶頭節點的
    node rear;//相當于tail/end
    int maxsize;//最大長度
    int len=0;
    public MyCircularQueue(int k) {
        front=new node(0);
        rear=front;
        maxsize=k;
        len=0;
    }
    public boolean enQueue(int value)  {
        if (isFull())
            return  false;
        else {
            node va=new node(value);
            rear.next=va;
            rear=va;
            len++;
        }
        return  true;
    }
    public boolean deQueue() {
        if (isEmpty())
            return false;
        else {
            front.next=front.next.next;
            len--;
            //注意 如果被删完 需要将rear指向front
            if(len==0)
                rear=front;
        }
        return  true;
    }

    public int Front() {
        if(isEmpty())
            return -1;
        return front.next.data;
    }

    public int Rear() {
        if(isEmpty())
            return -1;
        return rear.data;
    }

    public boolean isEmpty() {
        return  len==0;
        //return rear == front;
    }

    public boolean isFull() {
        return len==maxsize;
    }    
}           

雙向隊列(加餐)

設計實作雙端隊列，其實你經常使用的ArrayDeque就是一個經典的雙向隊列，其基于數組實作，效率非常高。我們這裡實作的雙向隊列模闆基于力扣641 設計循環雙端隊列 。

你的實作需要支援以下操作：

• MyCircularDeque(k)：構造函數,雙端隊列的大小為k。
• insertFront()：将一個元素添加到雙端隊列頭部。 如果操作成功傳回 true。
• insertLast()：将一個元素添加到雙端隊列尾部。如果操作成功傳回 true。
• deleteFront()：從雙端隊列頭部删除一個元素。 如果操作成功傳回 true。
• deleteLast()：從雙端隊列尾部删除一個元素。如果操作成功傳回 true。
• getFront()：從雙端隊列頭部獲得一個元素。如果雙端隊列為空，傳回 -1。
• getRear()：獲得雙端隊列的最後一個元素。 如果雙端隊列為空，傳回 -1。
• isEmpty()：檢查雙端隊列是否為空。
• isFull()：檢查雙端隊列是否滿了。

其實有了上面的基礎，實作一個雙端隊列非常容易，有很多操作和單端的循環隊列是一緻的，隻有多了一個隊頭插入和隊尾删除的操作，兩個操作分别簡單的分析一下：

隊頭插入：隊友front下标位置本身是有值的，是以要将front退後一位然後再指派，不過要考慮是否為滿或者數組越界情況。

隊尾删除：隻需要rear位置減1，同時也要考慮是否為空和越界情況。

具體實作代碼：

public class MyCircularDeque {
    private int data[];// 數組容器
    private int front;// 頭
    private int rear;// 尾
    private int maxsize;// 最大長度
    /*初始化 最大大小為k */
    public MyCircularDeque(int k) {
        data = new int[k+1];
        front = 0;
        rear = 0;
        maxsize = k+1;
    }

    /** 頭部插入 */
    public boolean insertFront(int value) {
        if(isFull())
            return false;
        else {
            front=(front+maxsize-1)%maxsize;
            data[front]=value;
        }
        return  true;
    }

    /** 尾部插入 */
    public boolean insertLast(int value) {
        if(isFull())
            return  false;
        else{
            data[rear]=value;
            rear=(rear+1)%maxsize;
        }
        return  true;
    }

    /** 正常頭部删除 */
    public boolean deleteFront() {
        if (isEmpty())
            return false;
        else {
            front=(front+1)%maxsize;
        }
        return  true;
    }

    /** 尾部删除 */
    public boolean deleteLast() {
        if(isEmpty())
            return false;
        else {
            rear=(rear+maxsize-1)%maxsize;
        }
        return true;
    }

    /** Get the front item  */
    public int getFront() {
        if(isEmpty())
            return -1;
        return data[front];
    }

    /** Get the last item from the deque. */
    public int getRear() {
        if(isEmpty())
            return -1;
        return  data[(rear-1+maxsize)%maxsize];
    }

    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        return front==rear;
    }

    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        return (rear+1)%maxsize==front;
    }
}           

總結

對于隊列來說資料結構相比棧複雜一些，但是也不是很難，搞懂先進先出然後用數組或者連結清單實作即可。

對于數組，隊尾tail指向的位置是空的，而連結清單的front（head一樣）為頭指針為空的，是以在不同結構實作相同效果的方法需要注意一下。