225. Implement Stack Using Queues

Easy

Description

僅使用兩個佇列 (Queue) 來實作一個後進先出 (LIFO) 的堆疊。需支援 push、top、pop 和 empty 操作。

Example:

Input: [“MyStack”, “push”, “push”, “top”, “pop”, “empty”], [[], [1], [2], [], [], []] Output: [null, null, null, 2, 2, false]

Intuition#

核心思路：每次 push 後，將佇列中前面的元素全部重新排到後面，使最新元素永遠在佇列前端。

Queue 是 FIFO，Stack 是 LIFO，需要翻轉順序
關鍵是在哪個操作上付出代價：push 時重排（push O(n)）或 pop 時重排（pop O(n)）

Approaches#

1: 兩個 Queue#

概念: 用兩個佇列互相搬移。push 時先放入空佇列，再把另一個佇列的元素搬過來
時間複雜度: push O(n)，其餘 O(1)
空間複雜度: O(n)

class MyStack() {
    private var q1: java.util.LinkedList<Int> = java.util.LinkedList()
    private var q2: java.util.LinkedList<Int> = java.util.LinkedList()

    fun push(x: Int) {
        q2.offer(x)
        while (q1.isNotEmpty()) {
            q2.offer(q1.poll())
        }
        val temp = q1
        q1 = q2
        q2 = temp
    }

    fun pop(): Int = q1.poll()

    fun top(): Int = q1.peek()

    fun empty(): Boolean = q1.isEmpty()
}

⭐2: 單一 Queue#

概念: 只用一個佇列，push 後將前面 size - 1 個元素依次取出再放回尾端，使新元素排到最前面
時間複雜度: push O(n)，其餘 O(1)
空間複雜度: O(n)

class MyStack() {
    private val queue: java.util.LinkedList<Int> = java.util.LinkedList()

    fun push(x: Int) {
        queue.offer(x)
        repeat(queue.size - 1) {
            queue.offer(queue.poll())
        }
    }

    fun pop(): Int = queue.poll()

    fun top(): Int = queue.peek()

    fun empty(): Boolean = queue.isEmpty()
}

🔑 Takeaways#

Pattern: 用一種資料結構模擬另一種，核心是理解兩者行為差異並在適當操作上做轉換
關鍵技巧: 單一 Queue 解法中，push 後旋轉 size - 1 次就能把新元素推到前端，非常簡潔