03.04、化棧為隊

1、題目描述

實現(xiàn)一個 MyQueue 類，該類用兩個棧來實現(xiàn)一個隊列。

2、解題思路

本題要求使用兩個棧來實現(xiàn)一個隊列。隊列遵循先進先出（FIFO）的原則，而棧遵循后進先出（LIFO）的原則。因此，我們需要兩個棧來模擬隊列的行為：

1. pushS：用于存儲入隊的元素。
2. popS：用于反轉(zhuǎn)元素順序，以實現(xiàn)隊列的出隊操作。

3、解題步驟

1. 入隊操作 (push)：
   • 將新元素直接壓入到 pushS 棧中。
2. 出隊操作 (pop)：
   • 檢查 popS 棧是否為空：
     • 如果 popS 為空，將 pushS 中的所有元素逐個彈出并壓入 popS。這一步將反轉(zhuǎn)元素的順序，從而實現(xiàn)隊列的 FIFO 行為。
     • 如果 popS 不為空，直接彈出并返回 popS 的棧頂元素。
3. 獲取隊首元素 (peek)：
   • 類似于 pop 操作，只是我們不彈出 popS 棧的棧頂元素，而是返回它。
4. 檢查隊列是否為空 (empty)：
   • 隊列為空的條件是 pushS 和 popS 都為空。

4、代碼詳解

class MyQueue {
private:stack<int> pushS; // 入隊棧stack<int> popS;  // 出隊棧public:MyQueue() {}void push(int x) { pushS.push(x); }int pop() {// 如果出隊棧為空，將入隊棧的所有元素移到出隊棧中if (popS.empty()) {while (!pushS.empty()) {popS.push(pushS.top());pushS.pop();}}int ret = popS.top(); // 獲取出隊棧的棧頂元素popS.pop();           // 彈出該元素return ret;}int peek() {// 如果出隊棧為空，將入隊棧的所有元素移到出隊棧中if (popS.empty()) {while (!pushS.empty()) {popS.push(pushS.top());pushS.pop();}}return popS.top(); // 返回出隊棧的棧頂元素}bool empty() { return pushS.empty() && popS.empty(); }
};

5、時間復雜度

• 入隊操作 (push)：O(1)
• 出隊操作 (pop)：均攤 O(1)，因為每個元素最多只會從 pushS 轉(zhuǎn)移到 popS 一次。
• 獲取隊首元素 (peek)：均攤 O(1)
• 檢查隊列是否為空 (empty)：O(1)

6、空間復雜度

• 使用了兩個棧存儲元素，空間復雜度為 O(n)，其中 n 是隊列中元素的數(shù)量。

這道題通過使用兩個棧，成功模擬了隊列的行為，展示了棧和隊列之間的轉(zhuǎn)換關(guān)系。