03.04、化棧為隊(duì)

1、題目描述

實(shí)現(xiàn)一個(gè) MyQueue 類(lèi)，該類(lèi)用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列。

2、解題思路

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

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

3、解題步驟

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

4、代碼詳解

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

5、時(shí)間復(fù)雜度

• 入隊(duì)操作 (push)：O(1)
• 出隊(duì)操作 (pop)：均攤 O(1)，因?yàn)槊總€(gè)元素最多只會(huì)從 pushS 轉(zhuǎn)移到 popS 一次。
• 獲取隊(duì)首元素 (peek)：均攤 O(1)
• 檢查隊(duì)列是否為空 (empty)：O(1)

6、空間復(fù)雜度

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

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