用栈实现队列
[https://programmercarl.com/0232.用栈实现队列.html]
解法
class MyQueue {
private:stack<int> in;stack<int> out;void i2o(){while(!in.empty()){out.push(in.top());in.pop();}}
public:MyQueue() {}void push(int x) {in.push(x);}int pop() {if(out.empty()){i2o();}int num = out.top();out.pop();return num;}int peek() {if(out.empty()){i2o();}return out.top();}bool empty() {if(in.empty() && out.empty()) return true;return false;}
};
用队列实现栈
[https://programmercarl.com/0225.用队列实现栈.html#算法公开课]
解法
class MyStack {
private:queue<int> q;
public:MyStack() {}void push(int x) {q.push(x);}int pop() {int num = q.size();int n;int i = 0;while(i != num - 1){n = q.front();q.pop();q.push(n);i++;}n = q.front();q.pop();return n;}int top() {int num = q.size();int n;int i = 0;while(i < num - 1){n = q.front();q.pop();q.push(n);i++;}n = q.front();q.pop();q.push(n);return n;}bool empty() {if(q.empty()) return true;return false;}
};
有效的括号
[https://programmercarl.com/0020.有效的括号.html#算法公开课]
解法
class Solution {
public:bool isValid(string s) {stack<char> st;for(auto &p : s){if(is_left(p)){st.push(p);}else{if(st.empty() || !is_match(p,st.top())){return false;}else{st.pop();}}}if(st.empty()){return true;}else{return false;}}bool is_left(char p){if(p == '(' || p == '[' || p == '{'){return true;}else{return false;}}bool is_match(char p,char t){if(t == '(' && p == ')'){return true;}else if(t == '[' && p == ']'){return true;}else if(t == '{' && p == '}'){return true;}else{return false;}}
};删除字符串中的所有相邻重复项
[https://programmercarl.com/1047.删除字符串中的所有相邻重复项.html]
解法
class Solution {
public:string removeDuplicates(string s) {stack<char> st;for(char &p : s){if(st.empty()) st.push(p);else{if(p == st.top()){st.pop();}else{st.push(p);}}}string res;while(!st.empty()){res.push_back(st.top());st.pop();}reverse(res.begin(),res.end());return res;}
};