「算法刷题」栈和队列的相关经典题目

Posted on 2021-10-27 Edited on 2024-02-02

LeetCode题目	相关题目类型	相关链接
232	用栈实现队列（简单难度）	232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从输出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。

输入栈的元素出栈再放到输出栈中，这样输出栈的输出顺序和队列顺序一样了（手画一下）

class MyQueue {
public:
    stack<int>sck1;
    stack<int>sck2;
    MyQueue() {

    }
    
    void push(int x) {
        sck1.push(x);
        return ;
    }
    
    int pop() {
        // 把输入栈sck1中的元素放到输出栈sck2，清空sck1
        // 这样stk2的出栈顺序和输入的元素入stk1的顺序是一样的了
        while(!sck1.empty()){
            int num=sck1.top();// 获取栈顶元素，但不删除
            sck1.pop();// 删除栈顶元素，但不返回
            sck2.push(num); // 将元素压入栈顶
        }

        int val=sck2.top();// 返回栈顶元素
        sck2.pop();// 删除栈顶元素
        // 清空输出栈sck2
        while(!sck2.empty()){
            sck1.push(sck2.top());
            sck2.pop();
        }
        return val;
    }
    // 返回队列开头的元素
    int peek() {
        // 清空sck1，元素放入到sck2
        while(!sck1.empty()){
            sck2.push(sck1.top());
            sck1.pop();
        }
        //得到“队列”开头的元素
        int val=sck2.top();
        // 清空sck2，元素放入到sck1
        while(!sck2.empty()){
            sck1.push(sck2.top());
            sck2.pop();
        }
        return val;
    }
    
    bool empty() {
        if(sck1.empty()){
            return true;
        }
        return false;
    }
};

/**
 * 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();
 */

LeetCode题目	相关题目类型	关键点	相关链接
225	用队列实现栈（简单难度）		225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)

class MyStack {
public:
    queue<int> que1;
    queue<int> que2; // 辅助队列，用来备份
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** 将元素 x 压入栈顶。 */
    void push(int x) {
        que1.push(x);
    }

    /** 移除并返回栈顶元素。 */
    int pop() {
        int size=que1.size();
        size--;
        // 把que1元素放到que2，但保留最后一个
        while(size--){
            int num=que1.front();
            que1.pop();
            que2.push(num);
        }
        int res=que1.front();
        que1.pop();
        que1=que2;
        // 清空que2
        while(!que2.empty()){
            que2.pop();
        }
        return res;
    }

    /** 返回栈顶元素。 */
    int top() {
        return que1.back();
    }

    /** 如果栈是空的，返回 true ；否则，返回 false */
    bool empty() {
        return que1.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();
 */

LeetCode题目	相关题目类型	关键点	相关链接
20	有效的括号（简单难度）		20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com)

括号匹配是使用栈解决的经典问题。

由于栈结构的特殊性，非常适合做对称匹配类的题目。

首先要弄清楚，字符串里的括号不匹配有几种情况。

先来分析一下这里有三种不匹配的情况，

第一种情况，字符串里左方向的括号多余了，所以不匹配。

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

2.第二种情况，括号没有多余，但是括号的类型没有匹配上。

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

3.第三种情况，字符串里右方向的括号多余了，所以不匹配。

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出动手之前分析好题目的重要性。

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

class Solution {
public:
    bool isValid(string s) {
        stack<int> 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(']');
            }
            // 右括号出现
            // 右括号多余s.empty()
            // 左右不匹配
            else if(st.empty()||s[i]!=st.top()){
                return false;
            }
            else{
                st.pop();//左右括号匹配，
            }
        }
        // 左括号多余，则s.empty()==false;
        //都匹配，就是true
        return st.empty();
    }
};

LeetCode题目	相关题目类型	关键点	相关链接
1047	删除字符串中的所有相邻重复项（简单难度）		1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode） (leetcode-cn.com)

题目中有字符串的基本操作：

s.back();返回字符串最后一个元素

s.push_back(a);字符串末尾添加一个元素

s.pop_back();删除字符串末尾的元素

本题要删除相邻相同元素，其实也是匹配问题，相同左元素相当于左括号，相同右元素就是相当于右括号，匹配上了就删除。

那么再来看一下本题：可以把字符串顺序放到一个栈中，然后如果相同的话栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。

拿字符串直接作为栈，这样省去了栈还要转为字符串的操作。


class Solution {
public:
    string removeDuplicates(string S) {
        string res;
        for(char s:S){
            if(res.empty()||res.back()!=s){
                res.push_back(s);
            }
            else{
                res.pop_back();
            }
        }
        return res;
    }
};

LeetCode题目	相关题目类型	关键点	相关链接
150	逆波兰表达式求值（中等难度）		150. 逆波兰表达式求值 - 力扣（LeetCode） (leetcode-cn.com)

1、理解逆波兰表达式的求值方式

2、解题思路

遍历数组：

如果是运算符，弹出栈的两个栈顶元素num1，num2，进行相应运算，把结果放到栈中

如果是数字，把数字放到栈中

遍历结束：结果为栈中唯一的元素，返回结果。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i=0;i<tokens.size();i++){
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
                int nums1=st.top();
                st.pop();
                int nums2=st.top();
                st.pop();
                if(tokens[i]=="+")st.push(nums2+nums1);
                if(tokens[i]=="-")st.push(nums2-nums1);
                if(tokens[i]=="*")st.push(nums2*nums1);
                if(tokens[i]=="/")st.push(nums2/nums1);
            }
            else{
                st.push(stoi(tokens[i]));//stoi()将字符串转为int型
            }
        }
        int res=st.top();
        st.pop();
        return res;
    }
};