【C++】五道经典面试题带你玩转栈与队列

修修修也

发布于 2024-08-06 09:12:04

2930

文章被收录于专栏：修也的进阶日记修也的进阶日记

一.最小栈

题目链接:

155. 最小栈

https://leetcode.cn/problems/min-stack/

题目描述:

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

题目详情:

解题思路:

我们设计两个栈,一个存正常数据,一个存当前的最小值. 当有新元素入栈时,我们先将它入正常栈,然后将它和最小栈的栈顶元素比较(即和当前的最小值比较),如果比最小栈的栈顶元素小,就入最小栈,更新最小元素,如果大于栈顶元素就不入最小栈,保持最小栈的栈顶元素是当前栈里的最小值.而当有元素出栈时,判断它是不是最小栈的栈顶元素,如果是,就两个栈一起出栈,如果不是,就只出正常栈,最小栈不变.

解题代码:

class MinStack 
{
public:
    MinStack() 
    {}
    
    void push(int val) 
    {
        //不能先判断minst.top()因为minst可能为空,就会导致越界
        if(minst.empty()||val<=minst.top())
        {
            minst.push(val);
        }
        st.push(val);
    }
    
    void pop() 
    {
        if(st.top()==minst.top())
        {
            minst.pop();
        }
        st.pop();
    }
    
    int top() 
    {
        return st.top();
    }
    
    int getMin() 
    {
        return minst.top();
    }

    stack<int> st;
    stack<int> minst;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

提交运行:

二.JZ31 栈的压入、弹出序列

题目链接:

JZ31 栈的压入、弹出序列

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

题目描述:

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

0<=pushV.length == popV.length <=1000
-1000<=pushV[i]<=1000
pushV 的所有数字均不相同

题目详情:

解题思路:

我们用一个栈模拟栈的压入和弹出,先入栈一个压入顺序元素,然后开始判断它是不是和弹出序列的首个元素相等,如果相等,就从栈里弹出它,如果不相等就继续压入,直到新压入的元素和弹出序列的元素相等为止.总之,两个序列交替着向后遍历,中途如果遇到相等,就令弹出栈向后走,如果不相等,就让压入栈向后走,直到压入栈的元素全部压入栈里,如果弹出栈也刚好走完,那么就代表是合理的.如果没有走完,代表不合理.

解题代码:

class Solution 
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        stack<int> st;
        int pushi=0;
        int popi=0;
        while(popi<popV.size())
        {
            if(st.empty() || st.top()!=popV[popi])
            {
                if(pushi==pushV.size())
                    break;
                st.push(pushV[pushi++]);
            }
            else 
            {
                st.pop();
                popi++;
            }
        }
        return popi==popV.size() ? true : false;
    }
};

提交运行:

三.逆波兰表达式求值

题目链接:

150. 逆波兰表达式求值

https://leetcode.cn/problems/evaluate-reverse-polish-notation/

题目描述:

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。 注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

题目详情:

解题思路:

计算后缀表达式思路较简单:创建一个栈然后遍历序列,如果碰到数字,就入栈,如果碰到运算符,就出两个栈顶的元素进行运算,然后将结果再入栈.本题需要注意的就是序列是string类型的,数字和操作符都是string类型,不能进行直接运算,需要进行一定的转化才可以.

解题代码:

class Solution 
{
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> sti;
        int i=0;
        while(i<tokens.size())
        {
            if(tokens[i].size()==1 && tokens[i][0]>='*' && tokens[i][0]<='/') 
            {
                int right = sti.top();
                sti.pop();
                int left = sti.top();
                sti.pop();
                if(tokens[i] == "+") sti.push(left+right);
                else if(tokens[i] == "-") sti.push(left-right);
                else if(tokens[i] == "*") sti.push(left*right);
                else sti.push(left/right);
            }
            else
            {
                sti.push(stoi(tokens[i]));
            }
            i++;
        }
        return sti.top();
    }
};

提交运行:

四.用栈实现队列

题目链接:

232. 用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

题目描述:

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

题目详情:

解题思路:

该题我们在C语言接触栈时就已经完成过,贴个思路供大家参考,在C++这里思路是一模一样的,只是C++部分栈的实现比C语言简洁方便了不少,可以说是更简单了一些:

解题代码:

class MyQueue 
{
public:
    MyQueue() {}
    void push(int x) 
    {
        while(!st2.empty())
        {
            st1.push(st2.top());
            st2.pop();
        }
        st1.push(x);
    }
    
    int pop() 
    {
        int top = peek();
        st2.pop();
        return top;
    }
    
    int peek() 
    {
        while(!st1.empty())
        {
            st2.push(st1.top());
            st1.pop();
        }
        return st2.top();
    }
    
    bool empty() 
    {
        return st1.empty()&&st2.empty();
    }
    private:
    stack<int> st1;
    stack<int> st2;
};

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

提交运行:

五.二叉树的层序遍历

题目链接:

102. 二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/

题目描述:

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

题目详情:

解题思路:

思路就是因为我们要返回的是二维数组,所以必须要记录下结点是哪一层的.有两种方法可以使用:

一种是用两个队列,第一个队列先入第一层的结点,然后出第一个队列结点时将下一层结点存入第二个队列中,出第二个队列时再把下一层结点存入第一个队列中,边出边将数据存入相应层的vector里,直到两个队列中的结点出完代表二叉树层序遍历结束.
另一种是使用一个队列,然后使用一个levelSize变量来记录下上一层结点出的时候入了多少个,下一层就循环多少次将数据放入vector里,直到队列出空,代表二叉树遍历结束.

解题代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        //因为要返回的是二维数组,所以必须双队列或者用一个变量控制levelSize
        //我们就是一层一层入,一层一层出,一层入完统计有多少个,出下层就出多少个
        queue<TreeNode*> q;
        vector<vector<int>> vv;
        int levelSize=0;

        if(root)
        {
            q.push(root);
            levelSize=1;
        }
        while(!q.empty())//while循环一次就是一层
        {
            vector<int> v;
            for(int i=0;i<levelSize;i++)
            {
                TreeNode*front=q.front();
                q.pop();
                v.push_back(front->val);
                if(front->left!=nullptr)
                {
                    q.push(front->left);
                }
                if(front->right!=nullptr)
                {
                    q.push(front->right);
                }
            }
            vv.push_back(v);
            levelSize=q.size();
        }
        return vv;
    }
};

提交运行: