棧與隊列

一、用棧實現隊列

題目

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（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（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。

232. 用棧實現隊列 - 力扣（LeetCode）

題解

class MyQueue {
public:stack<int> inPut;stack<int> outPut;MyQueue() {}void push(int x) {inPut.push(x);}int pop() {if(outPut.empty()){while(!inPut.empty()){int tmp = inPut.top();outPut.push(tmp);inPut.pop();}}int result = outPut.top();outPut.pop();return result;}int peek() {int tmp = this->pop();outPut.push(tmp);return tmp;}bool empty() {if(inPut.empty() && outPut.empty()){return true;}else{return false;}}
};

二、用隊列實現棧

題目

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

實現 MyStack 類：

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

225. 用隊列實現棧 - 力扣（LeetCode）

題解

class MyStack {
public:queue<int> numOut;queue<int> copyOut;MyStack() {}void push(int x) {numOut.push(x);}int pop() {int count = numOut.size();// 計算主的隊列長度，注意留下最后一個元素while(--count){copyOut.push(numOut.front());numOut.pop();}// push出最后一個元素int result = numOut.front();numOut.pop();// 將備份的數據拿出來numOut = copyOut;// 清空備份區while(!copyOut.empty()){copyOut.pop();}return result;}int top() {return numOut.back();}bool empty() {return numOut.empty();}
};

三、有效的括號

題目

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

有效字符串需滿足：

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

20. 有效的括號 - 力扣（LeetCode）

題解

class Solution {
public:bool isValid(string s) {stack<char> stk;for(int i = 0; i < s.size(); i++){if(s[i] == '('){stk.push(')');}else if(s[i] == '{'){stk.push('}');}else if(s[i] == '['){stk.push(']');}else if(s[i] == ')'){if(!stk.empty() && stk.top() == s[i]){stk.pop();}else return false;}else if(s[i] == ']'){if(!stk.empty() && stk.top() == s[i]){stk.pop();}else return false;}else if(s[i] == '}'){if(!stk.empty() && stk.top() == s[i]){stk.pop();}else return false;}}if(stk.empty()){return true;}else return false;}
};

簡化版本

class Solution {
public:bool isValid(string s) {if(s.size() % 2 != 0) return false;stack<char> stk;for(int i = 0; i < s.size(); i++){if(s[i] == '('){stk.push(')');}else if(s[i] == '{'){stk.push('}');}else if(s[i] == '['){stk.push(']');}else if(!stk.empty() && stk.top() == s[i]){stk.pop();}else return false;}return stk.empty();}
};

四、刪除字符串中的所有相鄰重復項

題目

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

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

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

1047. 刪除字符串中的所有相鄰重復項 - 力扣（LeetCode）

題解

class Solution {
public:string removeDuplicates(string s) {stack<char> result;for (int i = 0; i < s.size(); i++) {if (!result.empty() && s[i] == result.top()) {result.pop();}else{result.push(s[i]);}}string final;int length = result.size();for (int i = 0; i < length; i++) {final += result.top();result.pop();}for (int i = 0, j = final.size() - 1; i < j; i++, j--) {swap(final[i], final[j]);}return final;}
};

五、逆波蘭表達式求值

知識點

• stoll 將字符串轉換為 long long int
• 后綴表達式：遇到數字則入棧，遇到運算符則去除棧頂兩個數字進行運算，并將結果壓入棧中

題目

給你一個字符串數組 tokens ，表示一個根據 逆波蘭表示法 表示的算術表達式。

請你計算該表達式。返回一個表示表達式值的整數。

注意：

• 有效的算符為 '+'、'-'、'*' 和 '/' 。
• 每個操作數（運算對象）都可以是一個整數或者另一個表達式。
• 兩個整數之間的除法總是 向零截斷 。
• 表達式中不含除零運算。
• 輸入是一個根據逆波蘭表示法表示的算術表達式。
• 答案及所有中間計算結果可以用 32 位 整數表示。

150. 逆波蘭表達式求值 - 力扣（LeetCode）

題解

class Solution {
public:int evalRPN(vector<string>& tokens) {// 力扣修改了后臺測試數據，需要用longlongstack<long long> st; for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}int result = st.top();st.pop(); // 把棧里最后一個元素彈出（其實不彈出也沒事）return result;}
};