題目描述:
僅使用兩個佇列(Queue)來實作一個後進先出(LIFO)的堆疊(Stack),支援 push、top、pop 和 empty 操作。
解題思路:
使用單個佇列即可模擬堆疊。關鍵在 push 操作:
這樣新元素就變成了佇列的前端(最先被 dequeue),達到堆疊的 LIFO 效果。
push(x):enqueue(x),然後旋轉佇列 size-1 次。O(n)。pop():直接 dequeue 前端元素。O(1)。top():回傳佇列前端元素。O(1)。empty():檢查佇列是否為空。O(1)。時間複雜度:push O(n),pop O(1),top O(1),empty O(1) — push 時需要旋轉 n-1 個元素。
空間複雜度:O(n) — 儲存 n 個元素,僅使用一個佇列。
1. Maintain a single queue q
2. push(x):
a. Enqueue x to q
b. For i from 0 to size(q) - 2:
- Enqueue front of q, then dequeue front
3. pop(): dequeue and return front of q
4. top(): return front of q
5. empty(): return whether q is empty兩個佇列法(Pop 昂貴):push 時直接加入主佇列 O(1)。pop 時將主佇列中除最後一個外的所有元素移至輔助佇列,取出最後一個元素,再交換兩個佇列。push O(1),pop O(n)。適用於 push 操作頻繁的場景。
兩個佇列法(Push 昂貴):push 時先放入空的輔助佇列,再將主佇列所有元素移至輔助佇列,最後交換。與單佇列旋轉法效果相同但用兩個佇列。邏輯上更清晰,但多用一個佇列。