解題說明
Implement Queue using Stacks（用堆疊實作佇列）
題目描述：僅使用兩個堆疊（stack）來實作一個先進先出（FIFO）的佇列，需支援 push、pop、peek、empty 四個操作，且 pop 和 peek 需均攤 O(1) 時間複雜度。
解題思路：堆疊是後進先出（LIFO），而佇列是先進先出（FIFO）。兩者的順序恰好相反，因此使用兩個堆疊可以「翻轉順序」來模擬佇列。
使用兩個堆疊：inputStack（輸入堆疊）和 outputStack（輸出堆疊）：
- push(x)：直接將元素壓入
inputStack，O(1)。 - pop() / peek()：若
outputStack為空，將inputStack的所有元素依序彈出並壓入outputStack——這個「搬移」動作會反轉順序，使最早進入的元素位於outputStack的頂部。接著從outputStack取出頂部元素即可。 - 關鍵：只有在
outputStack完全為空時才進行搬移，每個元素從inputStack到outputStack只搬移一次，因此均攤時間複雜度為 O(1)。 - empty()：兩個堆疊都為空時，佇列才為空。
C++ 解法
複雜度分析
時間複雜度：push O(1)；pop / peek 均攤 O(1) — 每個元素在整個生命週期中最多被搬移一次（從 inputStack 到 outputStack），因此雖然單次 pop 最壞情況為 O(n)，但 n 次操作的總成本為 O(n)，均攤每次為 O(1)。
空間複雜度：O(n) — 兩個堆疊合計最多儲存 n 個元素，其中 n 為佇列中的元素數量。
虛擬碼
1. Maintain two stacks: inputStack and outputStack 2. push(x): push x onto inputStack 3. move(): if outputStack is empty, pop all elements from inputStack and push onto outputStack 4. pop(): call move(), then pop and return top of outputStack 5. peek(): call move(), then return top of outputStack (without removing) 6. empty(): return true if both stacks are empty
其他解法
單堆疊模擬（需要遞迴）O(n)：只使用一個堆疊，每次 pop 時遞迴彈出所有元素，取出最底部的值後再將其他元素依序放回。實作較複雜且每次操作均為 O(n)，不符合本題的均攤要求。
雙端佇列（deque）O(1)：直接使用 C++ 標準函式庫的 std::deque 可以 O(1) 完成所有操作，但這不符合題目「只用堆疊」的限制，屬於繞過題意的做法，僅供參考。
延伸思考
- 本題的反問題——「用兩個佇列實作堆疊」（LeetCode 225）的解題思路為何？
- 「均攤分析」（Amortized Analysis）的概念是什麼？除了這題之外，還有哪些資料結構或演算法使用了均攤分析？
- 在實際系統設計中，什麼場景下會需要在堆疊和佇列之間進行轉換或組合使用？