1.用棧實現隊列

• LeetCode：232.用棧實現隊列

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

實現 MyQueue 類：

void push(int x)將元素x推到隊列的末尾
int pop()從隊列的開頭移除并返回元素
int peek()返回隊列開頭的元素
boolean empty() 如果隊列為空，返回true；否則，返回false
說明：

你只能使用標準的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty操作是合法的。
你所使用的語言也許不支持棧。你可以使用list或者deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。

示例 1：

輸入：

[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”] [[], [1], [2], [],[], []]
輸出： [null, null, null, 1, 1, false]

解釋：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

• 解題思路：

用棧來實現隊列的操作時我們應該要明白，棧有一個口，而隊列有兩個，因此棧只能先進后出，而隊列可以先進先出，因此棧需要兩個才能滿足隊列的先進先出。圖片來源：代碼隨想錄

（1）push(int x)為入隊操作，其時間復雜度為O(1)，可直接將新元素壓入輸入棧stIn，新元素總是添加到隊列尾部。

 void push(int x) {stIn.push(x);}

（2）pop() 為出隊操作，其平均時間復雜度為O(1)（最壞情況為O(n)），如果輸出棧stOut為空，就將輸入棧 stIn 所有元素轉移到stOut中，然后從stOut彈出并返回棧頂元素。

 int pop() {//確保輸出棧中有元素可用if (stOut.empty()) {//將輸入棧的所有元素轉移到輸出棧（反轉順序）while(!stIn.empty()) {stOut.push(stIn.top()); //復制棧頂元素stIn.pop();             //移除輸入棧頂元素}}int result = stOut.top(); //獲取輸出棧頂元素（隊列首部）stOut.pop();              //移除輸出棧頂元素return result;}

（3）peek()為查看隊首函數，其平均時間復雜度為O(1)（最壞情況為O(n)），在工業級別代碼開發中，最忌諱的就是實現一個類似的函數，直接把代碼粘過來改一改就完事了，這樣的項目代碼會越來越亂，因此我們需要復用pop()獲取元素，然后再將元素壓回輸出棧（因為peek操作不應移除元素）

int peek() {int res = this->pop(); //復用pop方法獲取元素stOut.push(res);       //將元素放回輸出棧（因為peek不移除元素）return res;}

其中this是一個指向當前對象的指針，在成員函數內部，可以通過this訪問當前對象的所有成員。因此this->pop()等價于直接調用pop()，顯式表示調用當前對象的pop成員函數。

由于peek()和pop()都需要獲取隊列頭部元素，而pop()已經實現了：檢查并轉移棧元素（當stOut為空時）和返回隊列頭部元素，因此，不需要在peek()中重復相同的棧轉移邏輯，這樣寫可以避免邏輯重復，也就是我們之前說的：不能直接復制粘貼過來就完事了。

（4）empty()為檢查空隊列函數，時間復雜度為O(1)，實現邏輯為當且僅當兩個棧都為空時隊列為空。

bool empty() {return stIn.empty() && stOut.empty(); //兩個棧都空時隊列為空}

完整代碼如下：

class MyQueue {
public:stack<int> stIn;  //輸入棧，用于接收新元素stack<int> stOut; //輸出棧，用于隊列操作//初始化隊列MyQueue() {} //構造函數不需要特別操作//將元素推入隊列尾部void push(int x) {stIn.push(x); //直接將新元素壓入輸入棧}//移除并返回隊列首部元素int pop() {//確保輸出棧中有元素可用if (stOut.empty()) {//將輸入棧的所有元素轉移到輸出棧（反轉順序）while(!stIn.empty()) {stOut.push(stIn.top()); //復制棧頂元素stIn.pop();             //移除輸入棧頂元素}}int result = stOut.top(); //獲取輸出棧頂元素（隊列首部）stOut.pop();              //移除輸出棧頂元素return result;}//獲取隊列首部元素（不移除） int peek() {int res = this->pop(); //復用pop方法獲取元素stOut.push(res);       //將元素放回輸出棧（因為peek不移除元素）return res;}//檢查隊列是否為空bool empty() {return stIn.empty() && stOut.empty(); //兩個棧都空時隊列為空}
};

2.用隊列實現棧

• LeetCode：225.用隊列實現棧

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。

實現MyStack類：

void push(int x)將元素x壓入棧頂。
int pop()移除并返回棧頂元素。
int top()返回棧頂元素。
boolean empty()如果棧是空的，返回true；否則，返回false。

注意：

你只能使用隊列的標準操作 —— 也就是push to back、peek/pop from front、size和is empty這些操作。
你所使用的語言也許不支持隊列。 你可以使用list（列表）或者deque（雙端隊列）來模擬一個隊列 , 只要是標準的隊列操作即可。

示例：

輸入： [“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2],[], [], []]
輸出： [null, null, null, 2, 2, false]

解釋：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

• 解題思路：

由于隊列是先進先出，要想實現棧的后進先出，就需要將隊列前面的n - 1個元素依次重新插入隊列，然后將原隊尾元素出隊列即可。圖片來源：代碼隨想錄

（1）push(int x) 為入棧操作，時間復雜度:為O(1)

 void push(int x) {//直接將新元素添加到隊列尾部que.push(x);}

（2）pop()為出棧操作，為時間復雜度O(n)

 int pop() {//獲取當前隊列中元素數量int size = que.size();//我們需要保留最后一個元素作為棧頂元素//所以需要旋轉 size-1 次size--;//旋轉隊列：將前 size-1 個元素移動到隊列尾部// 樣原隊列的最后一個元素就會成為隊列的第一個元素while (size--) {//將隊首元素添加到隊尾que.push(que.front());//移除原隊首元素que.pop();}//此時隊列的第一個元素就是棧頂元素int result = que.front();//移除棧頂元素（隊列的第一個元素）que.pop();return result;}

我們來模擬一下上述代碼流程：
假設我們執行三次push后調用pop，假設依次執行：

stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();  // 移除并返回 3

步驟1：
初始狀態（push(1), push(2), push(3) 后）
隊列 que: [1, 2, 3] 1為隊首, 3為隊尾

步驟2：
計算旋轉次數

int size = que.size();  // size = 3
size--;                 // size = 2 (需要旋轉2次)

步驟3：
第一次旋轉 (size=2)

que.push(que.front());  // 將隊首1移到隊尾 → [1,2,3,1]
que.pop();              // 移除原隊首1 → [2,3,1]
// 隊列狀態: [2, 3, 1]

步驟4：
第二次旋轉 (size=1)

que.push(que.front());  // 將隊首2移到隊尾 → [2,3,1,2]
que.pop();              // 移除原隊首2 → [3,1,2]
// 隊列狀態: [3, 1, 2]

步驟5：
彈出棧頂元素

int result = que.front();   // result = 3 (棧頂元素)
que.pop();                  // 移除3 → [1, 2]
return result;              // 返回3

最終狀態：
隊列 que: [1, 2]
棧頂元素：2（下一次pop將返回2）

（3）top()為返回棧頂元素，其時間復雜度為O(n)，執行步驟:

1.執行與 pop() 相同的旋轉操作
2.獲取棧頂元素但不移除
3.恢復隊列原始狀態： 將棧頂元素重新加入隊尾，然后移除隊列頭部的副本
4.返回棧頂元素

int top() {// 獲取當前隊列中元素數量int size = que.size();// 我們需要保留最后一個元素作為棧頂元素// 所以需要旋轉 size-1 次size--;// 旋轉隊列：將前 size-1 個元素移動到隊列尾部while (size--) {// 將隊首元素添加到隊尾que.push(que.front());// 移除原隊首元素que.pop();}// 此時隊列的第一個元素就是棧頂元素int result = que.front();// 關鍵步驟：為了保持棧的結構不變（因為我們只是查看棧頂元素，不是真的彈出）// 需要將棧頂元素重新放回隊列尾部que.push(que.front());// 然后移除隊列頭部的這個元素que.pop();// 返回棧頂元素return result;}

當然，也可以寫的更加簡便：

int top() {int res = this -> pop();que.push(res);return res;
}

（4）empty() 為檢查空棧，其時間復雜度為O(1)

 bool empty() {// 如果隊列為空，則棧也為空return que.empty();}

完整代碼如下：

class MyStack {
public:queue<int> que;  // 使用一個標準隊列來實現棧的功能// 構造函數，不需要特殊初始化MyStack() {// 構造函數體為空，因為隊列在聲明時已自動初始化}// 元素入棧（壓棧）操作// 時間復雜度：O(1)void push(int x) {// 直接將新元素添加到隊列尾部que.push(x);}// 元素出棧（彈棧）操作// 時間復雜度：O(n)，因為需要旋轉隊列int pop() {// 獲取當前隊列中元素數量int size = que.size();// 我們需要保留最后一個元素作為棧頂元素// 所以需要旋轉 size-1 次size--;// 旋轉隊列：將前 size-1 個元素移動到隊列尾部// 這樣原隊列的最后一個元素就會成為隊列的第一個元素while (size--) {// 將隊首元素添加到隊尾que.push(que.front());// 移除原隊首元素que.pop();}// 此時隊列的第一個元素就是棧頂元素int result = que.front();// 移除棧頂元素（隊列的第一個元素）que.pop();// 返回被移除的棧頂元素return result;}// 獲取棧頂元素但不移除// 時間復雜度：O(n)，因為需要旋轉隊列int top() {// 獲取當前隊列中元素數量int size = que.size();// 我們需要保留最后一個元素作為棧頂元素// 所以需要旋轉 size-1 次size--;// 旋轉隊列：將前 size-1 個元素移動到隊列尾部while (size--) {// 將隊首元素添加到隊尾que.push(que.front());// 移除原隊首元素que.pop();}// 此時隊列的第一個元素就是棧頂元素int result = que.front();// 關鍵步驟：為了保持棧的結構不變（因為我們只是查看棧頂元素，不是真的彈出）// 需要將棧頂元素重新放回隊列尾部que.push(que.front());// 然后移除隊列頭部的這個元素que.pop();// 返回棧頂元素return result;}// 檢查棧是否為空// 時間復雜度：O(1)bool empty() {// 如果隊列為空，則棧也為空return que.empty();}
};

3.有效的括號

• LeetCode：20.有效的括號

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串s，判斷字符串是否有效。

有效字符串需滿足：

1.左括號必須用相同類型的右括號閉合。
2.左括號必須以正確的順序閉合。
3.每個右括號都有一個對應的相同類型的左括號。

示例 1：

輸入：s = “()”

輸出：true

示例 2：

輸入：s = “()[]{}”

輸出：true

示例 3：

輸入：s = “(]”

輸出：false

示例 4：

輸入：s = “([])”

輸出：true

• 解題思路：

本題的核心思想是利用棧的先進后出特性進行括號匹配，即棧非常適合做對稱匹配類的題目。

（1）首先由題可知，若想括號全部匹配，必須是兩兩對應的，即必須為偶數，否則奇數肯定會出現不匹配的情況，因此在開始，我們要先做一個偶數的判斷，其時間復雜度O(1)

if(s.size() % 2 != 0) return false;

（2）對棧進行初始化

stack<char> res;

（3）接著遍歷s中的每個字符，那么在開始之前，我們先要想明白，若是不匹配會出現哪幾種情況，這有利于我們書寫代碼的邏輯性和速度。
情況一：已經遍歷完了字符串，但是棧不為空，說明沒有相應的括號來匹配。

情況二：遍歷字符串匹配的過程中，發現棧里沒有要匹配的字符。

情況三：遍歷字符串匹配的過程中，棧已經為空了，沒有匹配的字符了，說明右括號沒有找到對應的左括號。

那么根據這三種情況就可以很快判斷出是否為有效括號，接下來我們如何來解決括號的匹配問題呢？由題目可知，左括號一定是先出現的，不然先出現右括號就沒有左括號與他匹配，那么根據這一點我們不難想到：

if(s[i] == '(') res.push(')');
else if(s[i] == '[') res.push(']');
else if(s[i] == '{') res.push('}');

即當我們遇到左括號時，將對應的右括號壓入棧中，依次記錄后續需要匹配的右括號類型。這些都完成后，我們就可以開始寫判斷是否為有效括號的部分了，那么（3）的整體代碼如下：

for(int i = 0; i < s.size(); ++i){if(s[i] == '(') res.push(')');else if(s[i] == '[') res.push(']');else if(s[i] == '{') res.push('}');// 情況三：遍歷字符串匹配的過程中，棧已經為空了，沒有匹配的字符了，說明右括號沒有找到對應的左括號// 情況二：遍歷字符串匹配的過程中，發現棧里沒有我們要匹配的字符。所else if(res.empty() || s[i] != res.top()) return false;else res.pop();
}return res.empty();// 情況一：此時我們已經遍歷完了字符串，若棧不為空，說明有相應的左括號沒有右括號來匹配

整體代碼如下所示：

class Solution {
public:bool isValid(string s) {if(s.size() % 2 != 0) return false;//如果s的長度為奇數，一定不符合要求stack<char> res;for(int i = 0; i < s.size(); ++i){if(s[i] == '(') res.push(')');else if(s[i] == '[') res.push(']');else if(s[i] == '{') res.push('}');// 第三種情況：遍歷字符串匹配的過程中，棧已經為空了，沒有匹配的字符了，說明右括號沒有找到對應的左括號 return false// 第二種情況：遍歷字符串匹配的過程中，發現棧里沒有我們要匹配的字符。所以return falseelse if(res.empty() || s[i] != res.top()) return false;else res.pop();}return res.empty();// 第一種情況：此時我們已經遍歷完了字符串，但是棧不為空，說明有相應的左括號沒有右括號來匹配，所以return false，否則就return true}
}; 

4.刪除字符串中的所有相鄰重復項

• LeetCode：1047.刪除字符串中的所有相鄰重復項

給出由小寫字母組成的字符串s，重復項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們。

在s上反復執行重復項刪除操作，直到無法繼續刪除。

在完成所有重復項刪除操作后返回最終的字符串。答案保證唯一。

示例：

輸入：“abbaca”
輸出：“ca”
解釋：
例如，在 “abbaca” 中，我們可以刪除 “bb” 由于兩字母相鄰且相同，這是此時唯一可以執行刪除操作的重復項。之后我們得到字符串 “aaca”，其中又只有 “aa” 可以執行重復項刪除操作，所以最后的字符串為 “ca”。

• 解題思路

（1）初始化棧

// 1. 使用棧存儲待匹配的字符
stack<char> sta;

（2）遍歷字符串：若當棧空或當前字符≠棧頂元素值時，將當前字符壓入棧中；若當前字符=棧頂 元素，則彈出棧頂元素，即刪除重復字母對。

// 2. 遍歷輸入字符串for(char c : s) {// 情況1: 棧空或當前字符與棧頂不同 → 壓棧if(sta.empty() || c != sta.top()) {sta.push(c);} // 情況2: 當前字符與棧頂相同 → 彈出棧頂(刪除重復對)else {sta.pop();}}

（3）構建結果：將棧中剩余字符彈出，此時彈出的結果為逆序，我們需要反轉操作，才能得到最終字符串。

// 3. 構建結果字符串string res = "";// 將棧中字符彈出(此時為逆序)while(!sta.empty()) {res += sta.top();sta.pop();}// 反轉得到正確順序reverse(res.begin(), res.end());return res;

運行過程如下圖所示：

完整代碼如下所示：

class Solution {
public:string removeDuplicates(string s) {// 1. 使用棧存儲待匹配的字符stack<char> sta;// 2. 遍歷輸入字符串for(char c : s) {// 情況1: 棧空或當前字符與棧頂不同 → 壓棧if(sta.empty() || c != sta.top()) {sta.push(c);} // 情況2: 當前字符與棧頂相同 → 彈出棧頂(刪除重復對)else {sta.pop();}}// 3. 構建結果字符串string res = "";// 將棧中字符彈出(此時為逆序)while(!sta.empty()) {res += sta.top();sta.pop();}// 反轉得到正確順序reverse(res.begin(), res.end());return res;}
};