【C++】开始使用stack 与 queue
【C++】开始使用stack 与 queue
送给大家一句话： 忍受现实给予我们的苦难和幸福，无聊和平庸。 – 余华 《活着》
开始使用queue 与 stack
- 1 前言
- 2 stack与queue
- 2.1 stack 栈
- 2.2 queue 队列
- 2.3 使用手册
- 3 开始使用
- Leetcode 155.最小栈
- 牛客 JZ31 栈的弹出压入序列
- Leetcode 150.逆波兰表达式求值
- Thanks?(?ω?)?谢谢阅读！！！
- 下一篇文章见！！！
1 前言
在之前的学习中，我们已经对 STL 模板中的 string list vector 等容器进行了详细的探讨，从而获得了对这些容器操作的清晰理解。基于这些知识，现在转向学习 stack（栈） 和 queue（队列）就显得相对简单了。然而，在有效使用这两种容器之前，我们还需要对它们的工作原理和使用场景有一个系统的了解。这样，我们才能更加准确地应用这些数据结构来解决实际问题。
2 stack与queue
2.1 stack 栈
stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。类似与向箱子里放入取出物品，只能一端进行操作
stack是作为容器适配器( 一种设计模式 )被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下 操作：
- empty：判空操作
- back：获取尾部元素操作
- push_back：尾部插入元素操作
- pop_back：尾部删除元素操作
标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。
2.2 queue 队列
队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端 提取元素。类似与排队打饭，只能从尾端进入，从头离开。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操 作:
- empty：检测队列是否为空
- size：返回队列中有效元素的个数
- front：返回队头元素的引用
- back：返回队尾元素的引用
- push_back：在队列尾部入队列
- pop_front：在队列头部出队列
标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque
2.3 使用手册
stack手册 和 queue手册 通过手册我们可以发现基本接口是一样的：
stack栈：
函数说明 | 接口说明 |
|---|---|
empty() | 检测stack是否为空 |
size() | 返回stack中元素的个数 |
top() | 返回栈顶元素的引用 |
push() | 将元素val压入stack中 |
pop() | 将stack中尾部的元素弹出 |
queue 队列：
函数声明 | 接口说明 |
|---|---|
empty() | 检测队列是否为空，是返回true，否则返回false |
size() | 返回队列中有效元素的个数 |
front( ) | 返回队头元素的引用 |
back() | 返回队尾元素的引用 |
push() | 在队尾将元素val入队列 |
pop() | 将队头元素出队列 |
3 开始使用
接下来我们在解题中体会stack与queue的使用方法
Leetcode 155.最小栈
链接：最小栈 题目描述
这道题看起来很简单奥，我们需要模拟一个特殊的栈：可以获取到栈中的最小元素。
我们解决的办法也很直接了当，我们建立两个栈_st 和_minst，一个用来记录栈中的所以元素，一个来记录当前最小值。这个记录当前最小值只需要在插入元素时判断插入的元素是否小于当前栈中的最小值（也就是_minst中的top()元素）
也就是我们需要对插入与删除进行特殊处理，其余部分与普通的栈区别不大。
PS： 不敢想象如果使用C语言搓轮子会是多么费劲！！！
class MinStack {
public:
MinStack() {
}
void push(int val) {
_st.push(val);
if(_minst.empty() || val <= _minst.top())
{
_minst.push(val);
}
}
void pop() {
if(_st.top() == _minst.top())
{
_st.pop();
_minst.pop();
}
else
{
_st.pop();
}
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
private:
stack<int> _st;
stack<int> _minst;
};牛客 JZ31 栈的弹出压入序列
上链接！！！栈的弹出压入序列 题目描述
这个题目比较好理解，我们需要通过一个插入序列，来判断弹出序列可不可以通过插入序列来获取。 思路也比较简单，我们只需模拟弹出过程即可：
- 首先创建一个栈
- 依照插入序列来插入元素
- 检查当前栈顶元素是否等于弹出序列的首元素（一样说明该弹出了）
- 重复 3 操作直到不一致为止，然后进行2 - 3 操作
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
// 使用两个下表来进行两个序列的读取
int pushi = 0, popi = 0;
stack<int> st ;
//所有元素全部插完为止
while(pushi < pushV.size())
{
//插入一个
st.push(pushV[pushi]);
//检查是否一致，一致就弹出
while(!st.empty() && st.top() == popV[popi] )
{
popi++;
st.pop();
}
pushi++;
}
//最后进行判断
if(st.empty()) return true;
else return false;
}
};Leetcode 150.逆波兰表达式求值
题目描述
我们先来认识一下逆波兰表达式：也被称为后缀表达式，是一种非常巧妙的数学表达式写法。在这种表达式中，运算符位于所有操作数的后面，这种布局使得表达式的计算不再需要括号来指示运算的优先级。逆波兰表达式的一个典型特点是其清晰的运算顺序——从左到右，这使得计算过程变得直观且易于通过计算机算法实现。
但为什么我们需要逆波兰表达式呢？主要是因为它极大地简化了计算机程序对表达式的处理。在传统的中缀表达式中，计算机需要处理复杂的优先级和括号，而逆波兰表达式通过其后缀形式自然地避免了这些复杂性。这不仅提高了计算效率，还减少了程序运行过程中的错误可能性。 因此，在很多需要快速且准确计算的领域，如编译器的设计和科学计算中，逆波兰表达式都发挥了不可替代的作用。
而这道题我们需要模拟计算逆波兰表达式，我们就要先知道逆波兰表达式是如何计算的： 举个例子： 输入：tokens = [“2”,“1”,“+”,“3”,“*”] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
这是如何做到的：
也就是：
- 依次读入数字 （压入栈中）
- 读到运算符就进行运算（取出栈前两个数字来进行相应运算）
- 然后再储存运算结果（压入栈中）
- 依次重复 1 - 3 操作
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<string> st;
int i = 0;
while(i != tokens.size())
{
string tmp = tokens[i];
//枚举运算符，反正运算符就那些
if(tmp.size() == 1 && (tmp[0] == '*' || tmp[0] == '/' || tmp[0] == '-' || tmp[0] == '+'))
{
int n1 = stoi(st.top());
st.pop();
int n2 = stoi(st.top());
st.pop();
//直接枚举运算符
switch(tmp[0])
{
//注意数字顺序很重要！！！
case '*': n2 *= n1;
break;
case '/': n2 /= n1;
break;
case '+': n2 += n1;
break;
case '-': n2 -= n1;
break;
default : break;
}
//压入计算结果
st.push(to_string(n2));
i++;
}
else
{
st.push(tokens[i]);
i++;
}
}
return stoi(st.top());
}
};队列的相关习题大部分是子啊BFS中使用，这里就不在说明了