刷题了：232.用栈实现队列| 225. 用队列实现栈 |20. 有效的括号 | 1047. 删除字符串中的所有相邻重复项

232.用栈实现队列

题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/description/
文章讲解:https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html
视频讲解:https://www.bilibili.com/video/BV1nY4y1w7VC/?spm_id_from=333.788&vd_source=e70917aa6392827d1ccc8d85e19e8375
实现情况：

int peek():得到队列的前端元素

/*
 * @lc app=leetcode.cn id=232 lang=cpp
 *
 * [232] 用栈实现队列
 */

// @lc code=start

// #include <stack>
class MyQueue {
public:
     stack<int> stIn;
     stack<int> stOut;
    
    MyQueue() {

    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        if(stOut.empty()){//这里是当出栈位空
            while(!stIn.empty()){
                stOut.push(stIn.top());//将入栈全部元素发送到出栈
                stIn.pop();//入栈元素弹出
                            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;

    }
    
    int peek() {
        int result = this->pop();
        stOut.push(result);
        return result;
    }
    
    bool empty() {
        return stIn.empty() && stOut.empty();

    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */
// @lc code=end

225. 用队列实现栈

题目链接:https://leetcode.cn/problems/implement-stack-using-queues/description/
文章讲解:https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html
视频讲解:https://www.bilibili.com/video/BV1Fd4y1K7sm/?spm_id_from=333.788&vd_source=e70917aa6392827d1ccc8d85e19e8375
实现情况：

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

/*
 * @lc app=leetcode.cn id=225 lang=cpp
 *
 * [225] 用队列实现栈
 */

// @lc code=start
class MyStack {
public:
    queue<int> que; 
    MyStack() {

    }
    
    void push(int x) {
        que.push(x);

    }
    
    int pop() {
        int size = que.size();//记录size
        size--;//需要弹出的元素
        while (size--)
        {
            que.push(que.front());
            que.pop();
        }
        int result = que.front();
        que.pop();
        return result;
    }
    
    int top() {
        return que.back();

    }
    
    bool empty() {
        return que.empty();

    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
// @lc code=end

20. 有效的括号

题目链接:https://leetcode.cn/problems/valid-parentheses/description/
文章讲解:https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
视频讲解:https://www.bilibili.com/video/BV1AF411w78g/?spm_id_from=333.788&vd_source=e70917aa6392827d1ccc8d85e19e8375
实现情况：

不匹配的情况：
1、左右括号没有匹配
2、左括号多
3、右括号多
思路：
遇到右括号，我们及那个对应的左括号放入栈中，
遇到左括号我们弹出一样的左括号
还没有遍历结束，栈变为空，或者和遇到右括号不一样，就错误了

/*
 * @lc app=leetcode.cn id=20 lang=cpp
 *
 * [20] 有效的括号
 */

// @lc code=start
class Solution {
public:
    bool isValid(string s) {
        if(s.size() % 2!= 0 ){
            return false;
        }
        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('}');
            }else if(st.empty() || st.top()!= s[i]) {
                //还没有遍历结束，栈变为空，或者和遇到右括号不一样，就错误了
                return false;
            }else{
                 st.pop(); // 遇到左括号我们弹出一样的左括号
            }
        }
        return st.empty();//栈是空的就是全部匹配 返回true ；否则返回false
         


    }
};
// @lc code=end

题目链接:
文章讲解:https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html
视频讲解:https://www.bilibili.com/video/BV12a411P7mw/?spm_id_from=333.788&vd_source=e70917aa6392827d1ccc8d85e19e8375
实现情况：

/*
 * @lc app=leetcode.cn id=1047 lang=cpp
 *
 * [1047] 删除字符串中的所有相邻重复项
 */

// @lc code=start
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.push(s[i]);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
       
        string stmp = "";
        while (!st.empty())
        {
            stmp+= st.top();
            st.pop();
        }
        
        reverse (stmp.begin(), stmp.end()); // 此时字符串需要反转一下
        return stmp;
        

    }
};
// @lc code=end

/*
 * @lc app=leetcode.cn id=1047 lang=cpp
 *
 * [1047] 删除字符串中的所有相邻重复项
 */

// @lc code=start
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
         for (char c : s){
            if (st.empty() || c != st.top()) {
                st.push(c);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
         string result = "";
        while (!st.empty())
        {
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;
        

    }
};
// @lc code=end

原文地址：https://blog.csdn.net/qq_43441284/article/details/140725794

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！