雙堆疊

解題思路

我們使用兩個 stack 來模擬一個 queue 的操作。 一個 stack 叫做 input stack，用來存放新加入的資料。另一個 stack 叫做 output stack，用來取出最先加入的資料。

當我們要 pop 或 peek 最先加入的資料時，我們先檢查 output stack 是否為空。 如果 output stack 為空，我們就把 input stack 的所有資料依次 pop 並 push 到 output stack，這樣就把順序反轉了。 如果 output stack 不為空，我們就直接從 output stack pop 或 peek 頂部的資料，這就是最先加入的資料。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！ 立即加入「面試讀書會」，和大家一起準備面試！

內推機會	加入讀書會 (邀請碼：2059)

程式

class MyQueue() {
    private val s1: Stack<Int> = Stack()
    private val s2: Stack<Int> = Stack()
    private var front = -1
    fun push(x: Int) {
        if (s1.isEmpty()) {
            front = x
        }
        s1.push(x)
    }

    fun pop(): Int {
        while (s1.isNotEmpty()) {
            val obj = s1.pop()
            s2.push(obj)
        }
        val e = s2.pop()
        while (s2.isNotEmpty()) {
            val obj = s2.pop()
            if (s1.isEmpty()) {
                front = obj
            }
            s1.push(obj)
        }
        return e
    }

    fun peek(): Int {
        return front
    }

    fun empty(): Boolean {
        return s1.isEmpty()
    }

}

複雜度分析

• 時間複雜度:
  push 和 empty 操作的時間複雜度都是 ，也就是說它們的運行時間是固定的，不會隨著數據量的增加而增加。
  pop 和 peek 操作的時間複雜度均攤下來是 ，也就是說它們的平均運行時間是固定的。雖然有時候會需要把 input stack 的所有資料 pop 並 push 到 output stack，但這種情況並不常發生，所以平均下來每次操作的運行時間還是固定的。
  對於每個元素，它最多只會被 push 和 pop 各兩次，所以每個元素的平均操作時間還是固定的。

• 空間複雜度:
  。其中 是操作總數。
  如果有 次 push 操作，那麼 queue 中最多會有 個元素，所以空間複雜度為 。
  也就是說，空間需求會隨著操作數量的增加而增加，但增加的速度是線性的。如果操作數量增加一倍，空間需求也會增加一倍。如果操作數量增加十倍，空間需求也會增加十倍。所以空間複雜度為 。

　更多 LeetCode 解答在此，一起來學習！

內推機會來啦！

跟一流的人才幹大事，享受成功進步的高級樂趣！

內推機會	加入讀書會 (邀請碼：2059)