解析 LeetCode 225. 用隊列實現棧：單隊列的巧妙運用

一、題目分析

（一）功能需求

實現 MyStack 類，支持棧的四種操作：

• push(int x)：將元素壓入棧頂。
• pop()：移除并返回棧頂元素。
• top()：返回棧頂元素。
• empty()：判斷棧是否為空。
  需用隊列（本題代碼用單隊列 ）模擬棧的 LIFO 特性。

（二）核心挑戰

隊列是先進先出（FIFO ）結構，而棧是后入先出（LIFO ）結構，如何通過隊列操作模擬棧的“棧頂操作”是關鍵。

二、算法思想：單隊列的反轉操作

（一）核心思路

利用單隊列，在每次 push 操作時，通過“將新元素入隊后，把隊列中之前的所有元素依次出隊再入隊”，讓新元素移動到隊列頭部，從而模擬棧的“棧頂”位置。這樣，隊列的頭部始終對應棧的棧頂，后續 pop、top 操作可直接操作隊列頭部。

（二）操作邏輯

• push 操作：
  1. 新元素入隊。
  2. 將隊列中除新元素外的所有元素依次出隊并重新入隊。這樣，新元素會被“移到”隊列頭部，成為棧頂。
• pop 操作：直接彈出隊列頭部元素（對應棧頂 ）。
• top 操作：返回隊列頭部元素（對應棧頂 ）。
• empty 操作：判斷隊列是否為空。

三、代碼實現與詳細解析

class MyStack {// 用于模擬棧的隊列，選擇 LinkedList 實現隊列（支持高效的入隊、出隊）Queue<Integer> queue; public MyStack() {// 初始化隊列queue = new LinkedList<>(); }public void push(int x) {// 新元素入隊queue.offer(x); int size = 0;// 遍歷隊列中除新元素外的所有元素（新元素是最后入隊的，所以循環 size < 隊列長度 - 1 次）while (size < queue.size() - 1) { // 隊首元素出隊，重新入隊到隊尾queue.offer(queue.poll()); size++;}}public int pop() {// 隊列頭部是棧頂，直接彈出return queue.poll(); }public int top() {// 隊列頭部是棧頂，直接返回return queue.peek(); }public boolean empty() {// 判斷隊列是否為空return queue.isEmpty(); }
}

（一）代碼流程拆解

1. 初始化：queue 用 LinkedList 實現（因 LinkedList 是 Queue 接口的常用實現，支持高效的 offer、poll、peek 操作 ）。
2. push 操作：
   • 新元素 x 入隊（queue.offer(x) ）。
   • 循環 size < queue.size() - 1 次（size 初始為 0 ）：每次將隊首元素出隊（queue.poll() ）并重新入隊（queue.offer(...) ）。此操作讓新元素前的所有元素“繞到”隊列尾部，新元素成為隊首，模擬棧頂。
3. pop 操作：調用 queue.poll() 彈出隊首元素（即棧頂 ）。
4. top 操作：調用 queue.peek() 返回隊首元素（即棧頂 ）。
5. empty 操作：調用 queue.isEmpty() 判斷隊列是否為空，即棧是否為空。

（二）關鍵邏輯解析

• push 操作的反轉技巧：通過將新元素入隊后，把之前的元素循環“出隊再入隊”，讓新元素移動到隊首。例如，隊列原是 [a, b, c]，入隊 d 后變為 [a, b, c, d]，循環 3 次（size < 4 - 1 ）：
  • 第一次：a 出隊入隊 → [b, c, d, a]
  • 第二次：b 出隊入隊 → [c, d, a, b]
  • 第三次：c 出隊入隊 → [d, a, b, c]
    最終新元素 d 成為隊首，對應棧頂。
• 單隊列的優勢：相比雙隊列實現（一個隊列存元素，一個隊列輔助 ），單隊列通過反轉操作，減少了隊列數量，代碼更簡潔，利用隊列自身操作完成模擬。
• 時間復雜度分析：push 操作的時間復雜度為 O(n)（n 是當前隊列長度，需循環 n - 1 次 ）；pop、top、empty 操作的時間復雜度為 O(1) 。

四、復雜度分析

（一）時間復雜度

• push：$O(n)$ ，n 是當前棧中元素個數（需移動 n - 1 個元素 ）。
• pop：$O(1)$ ，直接彈出隊首。
• top：$O(1)$ ，直接訪問隊首。
• empty：$O(1)$ ，直接判斷隊列是否為空。

（二）空間復雜度

所有操作僅使用一個隊列，空間復雜度為 $O(n)$（n 是棧中元素最大數量 ）。