【LeetCode刷题】栈和队列题目练习~

【LeetCode刷题】栈和队列题目练习~

码农世界 2024-05-19 前端 62 次浏览 0个评论

【LeetCode刷题】

  • 1. 题目：155.最小栈
    • 思路分析：
    • 思路1：两个栈实现最小栈
    • 2.题目: JZ31 栈的压入、弹出序列
      • 思路分析：
      • 思路1：模拟实现
      • 3.题目: 150.逆波兰表达式求值
        • 思路分析：
        • 思路1：暴力
        • 4.题目：232.用栈实现队列
          • 思路分析：
          • 思路1：两个栈
          • 5.题目：225.用队列实现栈
            • 思路分析：
            • 思路1：一个队列实现
            • 思路2：两个队列：入栈O(n),出栈O(1)
            • 思路3：两个队列：入栈O(1),出栈O(n)

              1. 题目：155.最小栈

              思路分析：

              从解释那段代码调用，我们可以知道MinStack是一个很普通的栈，就多一个函数而已。所以就可以在MinStack的属性里加一个stack，再加一个可以时刻记录栈内最小值的容器就可以。

              思路1：两个栈实现最小栈

              设计两个栈，一个正常栈（s1），一个用于记录正常栈每次push或者pop后的最小值（minS）。要获得MinStack的最小值，只需要访问minS的top就可以。

              代码实现：

              class MinStack {
public:
    MinStack() {}
    
    void push(int val) {
        s1.push(val);
        if(minS.empty()||val
        s1.pop();
        minS.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int getMin() {
        return minS.top();
    }
private:
    stack s1;
    stack minS;
};

              【LeetCode链接：155.最小栈】

              2.题目: JZ31 栈的压入、弹出序列

              思路分析：

              平时我们做这样的选择题是怎么做的？自己是不是要模拟实现一下。所以这里我们也同样可以来模拟实现一下，看匹不匹配。

              思路1：模拟实现

              • 模拟实现，判断栈的出入顺序匹不匹配，肯定要有个栈s1。
              • 再来过程，pushV把数据push到栈里，每次push后，栈顶元素与序列popV头元素（或者指针元素）对比，若相等，两个都头删（栈头删，popV指针后移），再比较，直到不相等，然后再接着pushV进栈（vector没有头删，所以用指针记录好些）。
              • 结果判断：可以判断popV的指针位置，也可以判断栈s1是否已经pop完了。

                代码实现： 

                class Solution {
public:
    bool IsPopOrder(vector& pushV, vector& popV) {
        // write code here
        stack s;
        int j=0;
        for(int i=0;i
            s.push(pushV[i]);
            while(!s.empty())
            {
                 if(s.top()==popV[j])
                {
                s.pop();
                j++;
                }
                else break;
            }
        }
        return j==popV.size();
    }
};

                【牛客链接：JZ31 栈的压入、弹出序列】

                3.题目: 150.逆波兰表达式求值

                思路分析：

                这题的要求就是计算逆波兰表达式的值，也叫后缀表达式（运算符放到后面），计算规则很简单，主要是设计一些判断。

                运算规则：符号前两个数字，通过这个运算符计算后再次存入，直到把最后一个运算符运算结束。

                思路1：暴力

                遍历tokens，是数字就按顺序存在容器里，遇到运算符，就取出最近插入的两个数字计算，注意前面的减后面的（减法和除法注意），然后再把计算结果返回到容器里。直到遍历完。

                代码实现：

                class Solution {
public:
    int evalRPN(vector& tokens) {
        stack s;
        for(int i=0;i
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/") 
            {
                if(tokens[i]=="+") 
                {
                    int k=s.top();
                    s.pop();
                    k+=s.top();
                    s.pop();
                    s.push(k);
                }
                else if(tokens[i]=="-") 
                {
                    int k=s.top();
                    s.pop();
                    k=s.top()-k;
                    s.pop();
                    s.push(k);
                }
                else if(tokens[i]=="*") 
                {
                   int k=s.top();
                    s.pop();
                    k*=s.top();
                    s.pop();
                    s.push(k);
                }
                else if(tokens[i]=="/") 
                {
                   int k=s.top();
                    s.pop();
                    k =s.top()/k;
                    s.pop();
                    s.push(k);
                }
            }
            else s.push(stoi(tokens[i]));
        }
        return s.top();
    }
};

                【LeetCode链接：150.逆波兰表达式求值】

                4.题目：232.用栈实现队列

                思路分析：

                用栈来实现队列，要从先进后出变到先进先出。

                思路1：两个栈

                其实只是需要一个辅助栈就可以了。正常栈push进数据，再要pop或者返回top的时候，几把数据push到辅助栈里，然后辅助栈pop、top都可以。

                代码实现：

                class MyQueue {
public:
    void push(int x) { s1.push(x); }
    int pop() {
        if (s2.empty())
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        int k = s2.top();
        s2.pop();
        return k;
    }
    int peek() {
        if (s2.empty())
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        return s2.top();
    }
    bool empty() { return s1.empty() && s2.empty(); }
    stack s1;			//正常栈
    stack s2;			//辅助栈
};

                【LeetCode链接：232.用栈实现队列】

                5.题目：225.用队列实现栈

                思路分析：

                这种题主要是设计，思路方面比较明确的。用队列实现栈。

                思路1：一个队列实现

                一个队列思路就是：一个元素进去，要保证它是在front位置，怎么保证，把前面的所有元素再一次push进队列就可以。

                代码实现：

                class MyStack {
public:
    queue q;
    /** Initialize your data structure here. */
    MyStack() {
    }
    /** Push element x onto stack. */
    void push(int x) {
        int n = q.size();
        q.push(x);
        for (int i = 0; i < n; i++) {
            q.push(q.front());
            q.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int r = q.front();
        q.pop();
        return r;
    }
    
    /** Get the top element. */
    int top() {
        int r = q.front();
        return r;
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
};
作者：力扣官方题解
来源：力扣（LeetCode）

                思路2：两个队列：入栈O(n),出栈O(1)

                入栈O(n),出栈O(1): 这就说明在push时候导元素。一个栈保持空队列，每次push就往里push，再把另一个栈顺序的队列的元素全部导到这个刚push一个的元素里。然后交换两个队列，push队列依旧是空，顺序队列依旧顺序和栈要求顺序一样（pop、front就是后进的元素）

                代码实现：

                class MyStack {
public:
    queue queue1;
    queue queue2;
    /** Initialize your data structure here. */
    MyStack() {
    }
    /** Push element x onto stack. */
    void push(int x) {
        queue2.push(x);
        while (!queue1.empty()) {
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1, queue2);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int r = queue1.front();
        queue1.pop();
        return r;
    }
    
    /** Get the top element. */
    int top() {
        int r = queue1.front();
        return r;
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return queue1.empty();
    }
};
作者：力扣官方题解
来源：力扣（LeetCode）

                思路3：两个队列：入栈O(1),出栈O(n)

                入栈O(1),出栈O(n): 这就说明pop处导元素。一个队列只是push进，不做其他处理。只有到了pop时候，就把这个队列的元素除了最后进的元素外，其他全部push到第二个队列。再次pop的话，就用第二个队列做同样的操作。top的话只需要看哪个队列不为空，返回最后一个元素就可以。

                代码实现：

                class MyStack {
public:
    void push(int x) { q1.push(x); }
    int pop() {
        int k;
        if (!q1.empty()) {
            while (q1.size() > 1) {
                q2.push(q1.front());
                q1.pop();
            }
            k = q1.front();
            q1.pop();
        } else {
            while (q2.size() > 1) {
                q1.push(q2.front());
                q2.pop();
            }
            k = q2.front();
            q2.pop();
        }
        return k;
    }
    int top() {
        if (!q1.empty())
            return q1.back();
        else
            return q2.back();
    }
    bool empty() { return q1.empty() && q2.empty(); }
    queue q1;
    queue q2;
};

                【LeetCode链接：225.用队列实现栈】

转载请注明来自码农世界，本文标题：《【LeetCode刷题】栈和队列题目练习~》

百度分享代码，如果开启HTTPS请参考李洋个人博客
37815篇文章 站点 微博
每一天，每一秒，你所做的决定都会改变你的人生！

发表评论

快捷回复：

评论列表 （暂无评论，62人围观）参与讨论

还没有评论，来说两句吧...

Top