【C++杂货铺】探索stack和queue的底层实现

一、stack的介绍和使用

1.1 stack的介绍

• stack 是一种容器适配器，专门用在具有后进先出的上下文环境中。只能从容器的一端进行元素的插入与提取操作。

• stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，使得元素在特定容器的尾部（栈顶）被压入和弹出。

• stack 的底层容器可以使任何标准的容器类模板或者一些其它特定的容器类，这些容器类应该支持以下操作：

  • empty：判空操作

  • back：获取尾部元素操作

  • push_back：尾部插入元素操作

  • pop_back：尾部删除元素操作

• 标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器，默认情况下使用 deque。

1.2 stack的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测栈 stack 是否为空
size()	返回 stack 中元素的个数
top()	返回栈顶元素的引用
push()	将元素 val 压入 stack 中
pop()	将 stack 中尾部的元素弹出

1.2.1 最小栈

本题的思路是用两个栈来实现，其中一个栈 _st 用来正常存储数据，另一个栈 _minst 用来存储最小的数据。具体实现就是在往 _st 中插入数据的时候进行判断，如果当前插入的数据 val 小于等于 _minst 栈顶的数据，那就将 val 也插入到 _minst 这个栈中。否则直将数据插入 _st 中。在 pop 数据的时候，先取 _st 的栈顶元素和 _minst 的栈顶元素进行比较，如果二者相等，那就同时 pop _st 和 _minst 的栈顶元素，否则就值 pop _st 的栈顶元素。要获取堆栈中的最小元素直接返回 _minst 的栈顶元素即可。

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()){_minst.pop();}_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stack<int> _st;stack<int> _minst;
};

1.2.2 栈的压入、弹出序列

本题的解题思路是用一个栈来模拟。即先定义一个栈 st 然后给栈中入一个数据，接着取栈顶的数据和出栈序列 popV 当前位置元素进行比较进行比较，如果不相等则继续从入栈序列 pushV 中拿数据往栈 st 中入，如果相等就出栈。这里需要注意，有可能需要连续多次出栈。直到最终将入栈序列 pushV 中的数据全入栈，最后判断栈 st 是否为空，如果为空，就说明该出栈序列正确。如果不空就说明该出栈序列有问题。

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> st;size_t push_pos = 0, pop_pos = 0;while(push_pos < pushV.size()){//先入一个元素st.push(pushV[push_pos++]);if(st.top() != popV[pop_pos]){//不匹配继续入数据continue;}while(!st.empty() && st.top() == popV[pop_pos]){//匹配，出数据st.pop();pop_pos++;}}return st.empty();}
};

代码优化：我们可以发现上面代码中不匹配逻辑里面其实啥也没干，因此我们可以把这段代码给删掉，上面加上是为了使逻辑更加清晰。

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> st;size_t push_pos = 0, pop_pos = 0;while(push_pos < pushV.size()){//先入一个元素st.push(pushV[push_pos++]);while(!st.empty() && st.top() == popV[pop_pos]){//匹配，出数据st.pop();pop_pos++;}}return st.empty();}
};

1.2.3 逆波兰表达式求值

逆波兰表达式也被叫做后缀表达式。什么是后缀表达式呢？先来了解一下中缀表达式，中缀表达式就是我们平时最常见的，例如：$2+3\ast 1$，就是一个典型的中缀表达式。将前面的中缀表达式变成后缀表达式得到：2 1 3 * +，这就是一个后缀表达式，后缀表达式相较于中中缀表达式，操作数顺序不变，操作符按优先级重排。这道题目就是要求我们对后缀表达式进行求解。求解后缀表达式，我们可以借助一个栈，遇到操作数入栈，遇到操作符从栈中出两个元素进行运算，将运算结果继续入栈。最终栈顶的元素就是整个逆波兰表达式的结果。

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;size_t pos = 0;while(pos < tokens.size()){if(tokens[pos] != "+" && tokens[pos] != "-" && tokens[pos] != "*" && tokens[pos] != "/"){//如果是数字就入栈int num = stoi(tokens[pos]);st.push(num);}else{//不是数字就从栈中取两个元素出来int val1 = st.top();st.pop();int val2 = st.top();st.pop();int ret = 0;if(tokens[pos] == "+"){ret = val2 + val1;}else if(tokens[pos] == "-"){ret = val2 - val1;}else if(tokens[pos] == "*"){ret = val2 * val1;}else if(tokens[pos] == "/"){ret = val2 / val1;}//将计算结果继续入栈st.push(ret);}pos++;}return st.top();}
};

注意：在写上面这段代码的时候有下面几点需要特别注意，首先这是一个 string 数组，会涉及到 string 转 int 。其次需要注意在从栈中取数的时候，第一次取出的是右操作数，第二次取出的是左操作数，因此 val2 应该做左操作数，val1 应该做右操作数，尤其是减法运算和除法运算，这两个操作数的顺序必须得到保证。

补充：这里补充一个小知识点：如何将中缀表达式转换成后缀表达式。主要过程分为以下几步：

1. 遇到操作数就输出（这里的输出是将其存储到某种容器里）。

2. 遇到操作符，根据优先级的顺序分为以下两种情况：

   • 栈为空或当前操作符比栈顶的优先级高，继续入栈。

   • 栈不为空且当前操作符比栈顶的优先级低或者相等，则输出栈顶操作符，继续执行第二步。

3. 中缀表达式结束后，依次出栈里面的操作符。

小Tips：当前操作符能否计算取决于后一个操作符的优先级是否高于自己，所以每当我们遇到一个操作符的时候，先不着急将它入栈，先和栈顶的操作符进行优先级比较，如果当前操作符的优先级比栈顶操作符的优先级低或者相等，我们就可以取出栈顶这个操作符进行运算。如果遇到括号可以走一个递归。其次就是需要想办法确定符号的优先级。

1.2.4 用栈实现队列

将一个栈当做输入栈，用于压入 push 传入的数据，另一个栈当做输出栈，用于 pop 和 peek 操作。每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

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

二、queue的介绍和使用

2.1 queue的介绍

• 队列是一种容器适配器，专门用于在FIFO上下文中执行先进先出操作，其中从容器的一端插入元素，另一端提取元素。

• 队列作为容器适配器实现，容器适配器即将特定的容器类封装最为其底层容器，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从对头出队列。

• 底层容器可以是标准容器模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：

  • empty：检查队列是否为空

  • size：返回队列中有效元素的个数

  • front：返回对头元素的引用

  • back：返回队尾元素的引用

  • push_back：在队列尾部入队列

  • pop_front：在队列头部出队列

• 标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque。

2.2 queue的使用

函数声明	接口说明
queue()	构造空队列
empty()	检测队列是否为空，是返回 true，否则返回 false
size()	返回队列中有效元素个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素 val 入队列
pop()	将队头元素出队列

2.2.1 二叉树的层序遍历

二叉树的层序遍历可以借助队列来实现，从根节点开始，先让父节点入队列，在出队尾节点的同时，将该节点的左孩子和右孩子依次入队列。直到队列为空，从队列中出出来的结果就是层序遍历的结果。这道题目需要将同一层的所有节点都存入一个一维数组，再将这些一维数组组合成一个二维数组返回。我们前面的这种做法会导致队列中出现两层节点混在意的情况，因此我们可以定义一个变量 levelSize 来记录每一层的节点数。具体代码如下：

class Solution 
{
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> retV;queue<TreeNode*> qu;int levelSize = 0;qu.push(root);while(!qu.empty()){vector<int> tmp;levelSize = qu.size();while(levelSize != 0){TreeNode* top = qu.front();if(top != nullptr){tmp.push_back(top->val);qu.push(top->left);qu.push(top->right);} qu.pop();levelSize--;}if(!tmp.empty()){retV.push_back(tmp);}}return retV;}
};

三、模拟实现

3.1 stack模拟实现

template<class T, class Continer = vector<T>>class stack{public:stack(){}void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}T& top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Continer _con;};

小Tips：stack 可以使用 vector 或者 list 来实现，效率相当。插入数据就相当于尾插，删除栈顶元素就相当于尾删。

3.2 queue模拟实现

template<class T, class Continer = std::list<T>>
class queue
{
public:queue(){}void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();//这里不再支持vector}T& front(){return _con.front();}T& back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}
private:Continer _con;
};

小Tips：栈不能借助 vector 来实现，因为出队列，相当于删除 vector 中的第一个元素，而对 vector 头删会涉及挪动数据，效率相较于 list 会有所下降。

四、容器适配器

4.1 什么是适配器？

适配器是一种设计模式（设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结），该种模式是将一个类的接口转换成客户希望的另外一个接口。

4.2 STL标准库中stack和queue的底层结构

虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器行列，而是将其称为容器适配器，这是因为 stack 和 queue 只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque。

4.3 deque的简单介绍

4.3.1 deque的原理介绍

deque（双端队列）：是一种双开口的“连续”空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了 deque 的迭代器身上，因此 deque 的迭代器设计的就比较复杂，如下图所示：

4.3.2 deque的缺陷

• 与 vector 比较，deque 的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比 vector 高的。

• 与 list 比较，其底层空间是连续的，空间利用率比较高，不需要存储额外字段。

• 但是，deque 有一个致命缺陷：不适合遍历，因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构式，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的一个应用场景就是，STL 用其作为 stack 和 queue 的底层数据结构。

4.4 为什么选择deque作为stack和queue的底层默认容器？

stack 是一种后进先出的特殊线性数据结构，因此只要是具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以；queue 是先进先出的特殊线性数据结构，只要具有 push_back() 和 pop_front() 操作的线性结构，都可以作为 queue de 底层容器，比如 list。但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：

• stack 和 queue 不需要遍历（因此 stack 和 queue 没有迭代器），只需要在固定的一端或者两端进行操作。

• 在 stack 中元素增长时，deque 比 vector 的效率高（扩容时不需要搬移大量数据）；queue 中的元素增长时，deque 不仅效率高，而且内存利用率高。

五、结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，春人的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！