讀完本文，你可以去力扣拿下如下題目：

232.用棧實現佇列

225.用佇列實現棧

-----------

佇列是一種先進先出的資料結構，棧是一種先進後出的資料結構，形象一點就是這樣：

這兩種資料結構底層其實都是陣列或者連結串列實現的，只是 API 限定了它們的特性，那麼今天就來看看如何使用「棧」的特性來實現一個「佇列」，如何用「佇列」實現一個「棧」。

一、用棧實現佇列

首先，佇列的 API 如下：

class MyQueue {        /** 新增元素到隊尾 */    public void push(int x);        /** 刪除隊頭的元素並返回 */    public int pop();        /** 返回隊頭元素 */    public int peek();        /** 判斷佇列是否為空 */    public boolean empty();}

我們使用兩個棧 s1, s2 就能實現一個佇列的功能（這樣放置棧可能更容易理解）：

class MyQueue {    private Stack<Integer> s1, s2;        public MyQueue() {        s1 = new Stack<>();        s2 = new Stack<>();    }    // ...}

當呼叫 push 讓元素入隊時，只要把元素壓入 s1 即可，比如說 push 進 3 個元素分別是 1,2,3，那麼底層結構就是這樣：

/** 新增元素到隊尾 */public void push(int x) {    s1.push(x);}

那麼如果這時候使用 peek 檢視隊頭的元素怎麼辦呢？按道理隊頭元素應該是 1，但是在 s1 中 1 被壓在棧底，現在就要輪到 s2 起到一箇中轉的作用了：當 s2 為空時，可以把 s1 的所有元素取出再新增進 s2，這時候 s2 中元素就是先進先出順序了。

/** 返回隊頭元素 */public int peek() {    if (s2.isEmpty())        // 把 s1 元素壓入 s2        while (!s1.isEmpty())            s2.push(s1.pop());    return s2.peek();}

同理，對於 pop 操作，只要操作 s2 就可以了。

/** 刪除隊頭的元素並返回 */public int pop() {    // 先呼叫 peek 保證 s2 非空    peek();    return s2.pop();}

最後，如何判斷佇列是否為空呢？如果兩個棧都為空的話，就說明佇列為空：

/** 判斷佇列是否為空 */public boolean empty() {    return s1.isEmpty() && s2.isEmpty();}

至此，就用棧結構實現了一個佇列，核心思想是利用兩個棧互相配合。

值得一提的是，這幾個操作的時間複雜度是多少呢？有點意思的是 peek 操作，呼叫它時可能觸發 while 迴圈，這樣的話時間複雜度是 O(N)，但是大部分情況下 while 迴圈不會被觸發，時間複雜度是 O(1)。由於 pop 操作呼叫了 peek，它的時間複雜度和 peek 相同。

像這種情況，可以說它們的最壞時間複雜度是 O(N)，因為包含 while 迴圈，可能需要從 s1 往 s2 搬移元素。

但是它們的均攤時間複雜度是 O(1)，這個要這麼理解：對於一個元素，最多隻可能被搬運一次，也就是說 peek 操作平均到每個元素的時間複雜度是 O(1)。

二、用佇列實現棧

如果說雙棧實現佇列比較巧妙，那麼用佇列實現棧就比較簡單粗暴了，只需要一個佇列作為底層資料結構。首先看下棧的 API：

class MyStack {        /** 新增元素到棧頂 */    public void push(int x);        /** 刪除棧頂的元素並返回 */    public int pop();        /** 返回棧頂元素 */    public int top();        /** 判斷棧是否為空 */    public boolean empty();}

先說 push API，直接將元素加入佇列，同時記錄隊尾元素，因為隊尾元素相當於棧頂元素，如果要 top 檢視棧頂元素的話可以直接返回：

class MyStack {    Queue<Integer> q = new LinkedList<>();    int top_elem = 0;    /** 新增元素到棧頂 */    public void push(int x) {        // x 是佇列的隊尾，是棧的棧頂        q.offer(x);        top_elem = x;    }        /** 返回棧頂元素 */    public int top() {        return top_elem;    }}

我們的底層資料結構是先進先出的佇列，每次 pop 只能從隊頭取元素；但是棧是後進先出，也就是說 pop API 要從隊尾取元素。

解決方法簡單粗暴，把佇列前面的都取出來再加入隊尾，讓之前的隊尾元素排到隊頭，這樣就可以取出了：

/** 刪除棧頂的元素並返回 */public int pop() {    int size = q.size();    while (size > 1) {        q.offer(q.poll());        size--;    }    // 之前的隊尾元素已經到了隊頭    return q.poll();}

這樣實現還有一點小問題就是，原來的隊尾元素被提到隊頭並刪除了，但是 top_elem 變數沒有更新，我們還需要一點小修改：

/** 刪除棧頂的元素並返回 */public int pop() {    int size = q.size();    // 留下隊尾 2 個元素    while (size > 2) {        q.offer(q.poll());        size--;    }    // 記錄新的隊尾元素    top_elem = q.peek();    q.offer(q.poll());    // 刪除之前的隊尾元素    return q.poll();}

最後，API empty 就很容易實現了，只要看底層的佇列是否為空即可：

/** 判斷棧是否為空 */public boolean empty() {    return q.isEmpty();}

很明顯，用佇列實現棧的話，pop 操作時間複雜度是 O(N)，其他操作都是 O(1)。

個人認為，用佇列實現棧是沒啥亮點的問題，但是用雙棧實現佇列是值得學習的。

從棧 s1 搬運元素到 s2 之後，元素在 s2 中就變成了佇列的先進先出順序，這個特性有點類似「負負得正」，確實不太容易想到。

希望本文對你有幫助。