僅使用兩個佇列 (Queue) 來實作一個後進先出 (LIFO) 的堆疊。需支援
push、top、pop和empty操作。
Example:
Input: [“MyStack”, “push”, “push”, “top”, “pop”, “empty”], [[], [1], [2], [], [], []] Output: [null, null, null, 2, 2, false]
Intuition
TIP
核心思路：每次 push 後，將佇列中前面的元素全部重新排到後面，使最新元素永遠在佇列前端。
- Queue 是 FIFO，Stack 是 LIFO，需要翻轉順序
- 關鍵是在哪個操作上付出代價：push 時重排（push O(n)）或 pop 時重排（pop O(n)）
Approaches
1. Two Queues — push O(n), others O(1) / O(n)
- Idea: 用兩個佇列互相搬移。push 時先放入空佇列，再把另一個佇列的元素搬過來
- Time: push
O(n)，其餘O(1) - Space:
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. Single Queue — push O(n), others O(1) / O(n)
- Idea: 只用一個佇列，push 後將前面
size - 1個元素依次取出再放回尾端，使新元素排到最前面 - Time: push
O(n)，其餘O(1) - Space:
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: 用一種資料結構模擬另一種，核心是理解兩者行為差異並在適當操作上做轉換
- Key trick: 單一 Queue 解法中，push 後旋轉
size - 1次就能把新元素推到前端，非常簡潔