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

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

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<minS.top()) minS.push(val);
        else minS.push(minS.top());
    }
    
    void pop() {
        s1.pop();
        minS.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int getMin() {
        return minS.top();
    }
private:
    stack<int> s1;
    stack<int> minS;
};

【LeetCode链接:155.最小栈】

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

思路分析:

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

思路1:模拟实现

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


  • 代码实现:
class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int> s;
        int j=0;
        for(int i=0;i<pushV.size();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<string>& tokens) {
        stack<int> s;
        for(int i=0;i<tokens.size();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<int> s1;      //正常栈
    stack<int> s2;      //辅助栈
};

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

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

思路分析:

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

思路1:一个队列实现

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

代码实现:

class MyStack {
public:
    queue<int> 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<int> queue1;
    queue<int> 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<int> q1;
    queue<int> q2;
};

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

相关文章
|
22天前
|
存储 算法 测试技术
力扣经典150题第五十四题:最小栈
力扣经典150题第五十四题:最小栈
17 0
|
25天前
|
存储 算法 索引
力扣每日一题 6/24 模拟 数组 单调栈
力扣每日一题 6/24 模拟 数组 单调栈
9 0
|
28天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
13天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
13天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
存储 算法 Python
二刷力扣--栈和队列
二刷力扣--栈和队列
|
1月前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值