【C++】5道经典面试题带你玩转栈与队列
🦄个人主页:修修修也
🎏所属专栏:C++
⚙️操作环境:Leetcode/牛客网
编辑
目录
一.最小栈
题目链接:
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就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. 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 ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
题目详情:
编辑
解题思路:
思路就是因为我们要返回的是二维数组,所以必须要记录下结点是哪一层的.有两种方法可以使用:
1. 一种是用两个队列,第一个队列先入第一层的结点,然后出第一个队列结点时将下一层结点存入第二个队列中,出第二个队列时再把下一层结点存入第一个队列中,边出边将数据存入相应层的vector里,直到两个队列中的结点出完代表二叉树层序遍历结束.
2. 另一种是使用一个队列,然后使用一个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;
}
};
提交运行:
编辑
结语
希望通过上面的题目能使大家对栈和队列的理解以及运用能够更上一层楼,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
相关文章推荐
【C++】9道 经 典面 试题带 你玩 转 string 类
【C++】 类 的六大默 认 成 员 函数及其特性 (万字 详 解 )
编辑
- 点赞
- 收藏
- 关注作者
评论（0）