代码随想录算法训练营43期 | Day 10——栈与队列part1

代码随想录算法训练营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// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以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 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入：“abbaca”
输出：“ca”
解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “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;}
};