算法训练营第十天|232.用栈实现队列 ，225. 用队列实现栈，20. 有效的括号，1047. 删除字符串中的所有相邻重复项

前置知识

• 栈和队列都是以deque为缺省底部结构，实际上可以自己指定vector，deque，list都可以
• 栈和队列都被归类为container adapter（ 容器适配器）
• 使用栈实现队列的操作：
  • push(x) -- 将一个元素放入队列的尾部。
  • pop() -- 从队列首部移除元素。
  • peek() -- 返回队列首部的元素。
  • empty() -- 返回队列是否为空。

232.用栈实现队列

文章链接：https://programmercarl.com/0232.用栈实现队列.html
视频链接：https://www.bilibili.com/video/BV1nY4y1w7VC/?spm_id_from=pageDriver&vd_source=6cb513d59bf1f73f86d4225e9803d47b
题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/

class MyQueue {
public:
    stack<int> In;
    stack<int> Out;
    MyQueue() {

    }
    
    void push(int x) {
        In.push(x);
    }
    
    int pop() {   //取加删
        if(Out.empty()){
            while(!In.empty()){
                Out.push(In.top());
                In.pop();
            }
        }
        int result=Out.top();
        Out.pop();
        return result;
    }
    
    int peek() {   //只取不删
        int res=this->pop();
        Out.push(res);
        return res;
    }
    
    bool empty() {
        return In.empty()&&Out.empty();
    }
};

225. 用队列实现栈

文章链接：https://programmercarl.com/0225.用队列实现栈.html
视频链接：https://www.bilibili.com/video/BV1Fd4y1K7sm/?vd_source=6cb513d59bf1f73f86d4225e9803d47b
题目链接：https://leetcode.cn/problems/implement-stack-using-queues/

class MyStack {
    queue<int> que;
public:
    MyStack() {

    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int size=que.size();
        size--;
        while(size--){
            que.push(que.front());
            que.pop();
        }
        int res=que.front();
        que.pop();
        return res;
    }
    
    int top() {
        int res=this->pop();
        que.push(res);//确保数据结构没有发生变化
        return res;
    }
    
    bool empty() {
        return que.empty();
    }
};

20. 有效的括号

文章链接：https://programmercarl.com/0020.有效的括号.html
视频链接：
题目链接：https://leetcode.cn/problems/valid-parentheses/description/

这里我直接用的switch-case结构来写的：

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

1047. 删除字符串中的所有相邻重复项

文章链接：https://programmercarl.com/1047.删除字符串中的所有相邻重复项.html
视频链接：
题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;      
        for(int i=0;i<s.size();i++){
            if(!st.empty()&&s[i]==st.top()){
                st.pop();
            }
            else st.push(s[i]); 
        }
        string res="";
        while(!st.empty()){
            res+=st.top();
            st.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};