大廠面試高頻題詳解：用棧實作隊列

正如标題所述，你需要使用兩個棧來實作隊列的一些操作。

隊列應支援push(element)，pop() 和 top()，其中pop是彈出隊列中的第一個(最前面的)元素。

pop和top方法都應該傳回第一個元素的值。

線上評測位址：

領扣題庫官網 例1:

輸入:
    push(1)
    pop()    
    push(2)
    push(3)
    top()    
    pop()     
輸出:
    1
    2
    2           

例2:

輸入:
    push(1)
    push(2)
    push(2)
    push(3)
    push(4)
    push(5)
    push(6)
    push(7)
    push(1)
輸出:
[]           

解題思路

先考慮隻有一個棧的時候，由于棧的先入後出特性FILO，棧中的元素的順序是反的，我們無法直接通路棧底的元素。但是當把1号棧中所有元素依次彈出并壓入到2号棧中，2号棧頂的元素就變成了原來1 号棧的棧底，即正序。是以我們要提取元素時，隻需從2号棧提取即可。

但是由于2号棧中棧頂元素是最先加入隊列的元素，是以隻有當2号棧為空時，才能将1号棧中所有元素加入到2号棧中。

舉例說明：

首先我們有一個主要棧stack1：[1,2,3) ，以下所有棧的表示方式中，圓括号 ')' 均為棧頂。 那麼stack1的出棧順序為3-2-1，其中 1 為我們要找到的元素，也就是隊首。

我們需要借助一個輔助棧stack2：[)，将stack1中的元素依次放到stack2中：stack2 [3,2,1)。這時我們發現stack2的棧頂就是我們要找的元素，彈出即可。

此時我們再向主要棧stack1中壓入 4 和 5。兩個棧狀态：stack1 [4,5) 、stack2 [3,2)。

現在我們需要隊首的話，應該先彈出輔助棧stack2的棧頂。

如果此時輔助棧空，我們就要執行之前轉移的操作，将stack1的所有元素壓入stack2，然後彈出stack2的棧頂即可。

代碼思路

定義move()，操作是将元素從1号棧轉移到2号棧。當要提取元素，且2号棧為空時，調用move()。

複雜度分析

時間複雜度

• 每個元素最多會别push，pop，move一次，每個操作的均攤時間複雜度為O(1)。

  空間複雜度

• 假設一共操作了N次push，空間複雜度為O(N)。

public class MyQueue {
    public MyQueue() {
        // do intialization if necessary
    }
    /*
     * @param element: An integer
     * @return: nothing
     */
    public void push(int element) {
        stack1.push(element);
    }
    /*
     * @return: An integer
     */
    public int pop() {
        if (stack2.isEmpty()) {
            move();
        }
        return stack2.pop();
    }
    /*
     * @return: An integer
     */
    public int top() {
        if (stack2.isEmpty()) {
            move();
        }
        return stack2.peek();
    }
    
    // 将1号棧中的元素移動到2号棧中
    private void move() {
        while (! stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
    
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();
}           

更多題解參考：[九章官網solution

](

https://www.jiuzhang.com/solution/implement-queue-by-two-stacks/?utm_source=sc-tianchi-sz-20nov)