class MyQueue {
public:stack<int> in;//输入栈stack<int> out;//输出栈MyQueue() {}void push(int x) {in.push(x);}int pop() {if(!out.empty()){int res=out.top();out.pop();return res;}else{//可能有人会疑惑会不会重复插入实则不会 因为之前插入的在非空情况下都会被弹出while(!in.empty()){out.push(in.top());in.pop();}}int res=out.top();out.pop();return res;}int peek() {if(!out.empty()){int res=out.top();return res;}else{//可能有人会疑惑会不会重复插入实则不会 因为之前插入的在非空情况下都会被弹出while(!in.empty()){out.push(in.top());in.pop();}}int res=out.top();return res;} bool empty() {if(in.empty()&&out.empty())return true;return false;}
};
栈实现队列
思路:很不错的题 利用输入输出流的原理 使得输入缓冲 到输出的时候 进入输出栈 实现队列
队列实现栈
思路:
用一个队列就可以实现很厉害的思路
class MyStack {
public:queue<int> q;MyStack() {}void push(int x) {q.push(x);}int pop() {int size=q.size();size--;while(size--){int temp=q.front();q.pop();q.push(temp);}int res=q.front();q.pop();return res;}int top() {int size=q.size();size--;while(size--){int temp=q.front();q.pop();q.push(temp);}int res=q.front();int temp=q.front();q.pop();q.push(temp);return res;}bool empty() {if(q.empty())return true;return false;}
};
匹配括号
思路:用栈对匹配
class Solution {
public:bool isValid(string s) {if (s.empty())return true;stack<char> st;for (char c : s) {if (c == '(' || c == '{' || c == '[') {st.push(c); // 左括号入栈} else {// 右括号处理if (st.empty()) {// 如果栈为空,说明没有匹配的左括号return false;}char now = st.top();st.pop(); // 匹配成功,弹出栈顶元素// 检查匹配的括号if ((now == '(' && c != ')') ||(now == '{' && c != '}') ||(now == '[' && c != ']')) {return false;}}}// 最终栈应该为空,如果不为空说明有未匹配的左括号return st.empty();}
};
重复项删除操作
思路:栈实现
class Solution {
public:string removeDuplicates(string s) {stack<char> st;for(char c:s){if(st.empty())st.push(c);else{char temp=st.top();if(c==temp){st.pop();} else{st.push(c);}}}string res;while(!st.empty()){res+=st.top();st.pop();}reverse(res.begin(),res.end());return res;}
};