代碼隨想錄算法訓練營43期 | Day 10

232.用棧實現隊列

class MyQueue {
public:stack<int> sIn;stack<int> sOut;MyQueue() {}void push(int x) {sIn.push(x);}int pop() {if(sOut.empty()){while(!sIn.empty()){sOut.push(sIn.top());sIn.pop();}}int result = sOut.top();sOut.pop();return result;}int peek() {int res = this->pop();sOut.push(res);return res;}bool empty() {return sIn.empty()&&sOut.empty();}
};

225. 用隊列實現棧

class MyStack {
public:queue<int> deq1;MyStack() {}void push(int x) {deq1.push(x);}int pop() {int size  = deq1.size();size--;while(size--){deq1.push(deq1.front());deq1.pop();}int result = deq1.front();deq1.pop();return result;}int top() {int size = deq1.size();size--;while (size--){// 將隊列頭部的元素（除了最后一個元素外） 重新添加到隊列尾部deq1.push(deq1.front());deq1.pop();}int result = deq1.front(); // 此時獲得的元素就是棧頂的元素了deq1.push(deq1.front());    // 將獲取完的元素也重新添加到隊列尾部，保證數據結構沒deq1有變化deq1.pop();return result;}sbool empty() {return deq1.empty();}
};

20. 有效的括號

需要解決的三種括號問題

1. 左括號多
2. 右括號多
3. 括號不匹配

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

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

給出由小寫字母組成的字符串 S，重復項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們。
在 S 上反復執(zhí)行重復項刪除操作，直到無法繼續(xù)刪除。
在完成所有重復項刪除操作后返回最終的字符串。答案保證唯一。
示例：
輸入：“abbaca”
輸出：“ca”
解釋：例如，在 “abbaca” 中，我們可以刪除 “bb” 由于兩字母相鄰且相同，這是此時唯一可以執(zhí)行刪除操作的重復項。之后我們得到字符串 “aaca”，其中又只有 “aa” 可以執(zhí)行重復項刪除操作，所以最后的字符串為 “ca”。

 class Solution {
public:string removeDuplicates(string S) {//定義一個棧stack<char> st;//遍歷字符串Sfor(auto s:S){//判斷 若當前遍歷元素 s 和棧頂元素 st.top() 相同則出棧，不同則入棧//注意：需判斷棧是否為空if(st.empty()||s!=st.top()){st.push(s);}else{st.pop();}}//遍歷結束，棧中存放字符為非重復項結果string result="";while(!st.empty()){result += st.top();st.pop();}//此時result順序是反的，需翻轉全部字符reverse(result.begin(),result.end());return result;}
};