【C++】stack和queue

📌 个人主页： 孙同学_
🔧 文章专栏：C++
💡 关注我，分享经验，助你少走弯路！

文章目录

• • 一. stack的介绍及使用
  • • 1.1 stack的介绍
    • 1.2 stack的使用
    • 1.3 stack的模拟实现
  • 二. queue的介绍和使用
  • • 2.1 queue的介绍
    • 2.2 queue的使用
    • 2.3 queue的模拟实现
  • 三. priority_queue的介绍和使用
  • • 3.1 priority_queue的介绍
    • 3.2 priority_queue的使用
    • 3.3 在OJ中的使用
    • 3.4 priority_queue的模拟实现
  • 四. 容器适配器
  • • 3.1 什么是适配器
    • 3.2 STL标准库中stack和queue的底层结构
  • 五. deque的介绍
  • • 5.1 deque的原理介绍
    • 5.2 deque的缺陷
    • 5.3 为什么选择deque作为stack和queue的底层默认容器

一. stack的介绍及使用

1.1 stack的介绍

stack的文档介绍

• stack是一种后进先出（LIFO）的数据结构。
• 底层默认使用deque实现，但可以指定其他容器（如vector或list）。
• 头文件：#include 。
  

1.2 stack的使用

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

155. 最小栈


解题思路：
这道题要求时间复杂度是O(1),我们可以定义两个栈，一个栈叫做st,一个栈叫做minst,当st中插入5时minst中也插入5,当 st 中插入4时，minst 也插入4，当st中插入6时，此时 minst 中不用做更新了，因为没有插入更小的值。此时 st 中删除与 minst中相同的值，minst 就跟着删，否则minst不动。
代码实现：

class MinStack {public: MinStack() { } void push(int val) { _st.push(val); if(_minst.empty() || val <= _minst.top()) //如果minst为空或者 要插入的值小于minst的栈顶元素就插入 _minst.push(val); } void pop() { if(_st.top() == _minst.top()) //如果删除的值和minst中的值相等，同时删，否则只删st _minst.pop(); _st.pop(); } int top() { return _st.top(); } int getMin() { return _minst.top(); }private: stack<int> _st; stack<int> _minst; };

拓展： 我们插入时如果有许多的重复数据有什么优化方案呢？
答案是我们可以定义一个结构体，结构体中的变量一个是int val，另一个是int cout用来计数

---

JZ31 栈的压入、弹出序列

解题思路：

1. 先入栈pushi位置的数据
2. 栈顶数据跟popi位置的数据比较，如果匹配则出栈popi++
3. 如果不匹配就继续入栈
   
   代码实现：

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

---

150. 逆波兰表达式求值


解题思路：

1. 遇到操作数则入栈
2. 遇到操作符，取栈顶两个数进行运算，运算结果继续入栈

代码实现：

class Solution {public: int evalRPN(vector<string>& tokens) { stack<int> s;//定义一个栈 for(auto& str : tokens) //用范围for遍历 { //如果是操作符 if(\"+\" == str || \"-\" == str || \"*\" == str || \"/\" == str) { int right = s.top(); s.pop(); int left = s.top(); s.pop(); switch(str[0]) {  case \'+\': s.push(left + right); break;  case \'-\': s.push(left - right); break;  case \'*\': s.push(left * right); break;  case \'/\': s.push(left / right); break; } } else {  //操作数 s.push(stoi(str));//stoi将字符串转化为int类型 } } return s.top(); }};

1.3 stack的模拟实现

template<class T, class Continer = std::deque<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;};

二. queue的介绍和使用

2.1 queue的介绍

queue的文档介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

• empty：检测队列是否为空
• size：返回队列中有效元素的个数
• front：返回队头元素的引用
• back：返回队尾元素的引用
• push_back：在队列尾部入队列
• pop_front：在队列头部出队列

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

2.2 queue的使用

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

2.3 queue的模拟实现

queue中因为要支持头删，所以就不能用vector

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;};

三. priority_queue的介绍和使用

3.1 priority_queue的介绍

priority_queue文档介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

• empty()：检测容器是否为空
• size()：返回容器中有效元素个数
• front()：返回容器中第一个元素的引用
• push_back()：在容器尾部插入元素
• pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

3.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

函数声明 接口说明 priority_queue()/priority_queue(first,last) 构造一个空的优先级队列 empty( ) 检测优先级队列是否为空，是返回true，否则返回false top( ) 返回优先级队列中最大(最小元素)，即堆顶元素 push(x) 在优先级队列中插入元素x pop() 删除优先级队列中最大(最小)元素，即堆顶元素

【注意】: 默认情况下，priority_queue是大堆。

如果要调成小堆就要通过仿函数来实现：

3.3 在OJ中的使用

215. 数组中的第K个最大元素

解题思路：
将数组放入优先级队列中，优先级队列的第一个元素是最大的，要第k大，则只需要pop k-1次
代码实现：

class Solution {public: int findKthLargest(vector<int>& nums, int k) { //将数组中的元素先放入优先级队列中 priority_queue<int> p(nums.begin(),nums.end()); while(--k) //--k是走k-1次 k--是走k次 { p.pop(); } return p.top(); }};

3.4 priority_queue的模拟实现

未加仿函数版：

#include //默认用vector来适配namespace myPriorityQueue{template<class T,class Container = std::vector<T>>class priority_queue{public:void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}void AdjustDown(int parent){int child = parent * 2 + 1; //算出左孩子的位置while (child < _con.size()){//假设法，选出左右孩子大的那个if (child + 1 < _con.size() && _con[child + 1] > _con[child])//如果右孩子大于左孩子{++child;}if (_con[child] > _con[parent]) //如果孩子大于父亲{swap(_con[child],_con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){//堆里面插入数据采用的是向上调整算法_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0],_con[_con.size() - 1]);//交换堆顶数据和最后一个数据_con.pop_back(); //删除最后一个数据AdjustDown(0);//向下调整，从根位置开始}bool empty(){return _con.empty();}const T& top(){return _con[0];//返回根位置数据}size_t size(){return _con.size();}private:Container _con;};}

加上仿函数版本的：

首先来看什么是仿函数：
仿函数是一种可以像函数一样被调用的对象，仿函数是一个类或者结构体，它重载了operator(),使其可以向函数一样被调用。

库里面传<是大堆，传>是小堆，为了保持 和库里面的是一致的，所以我们也这样实现：
代码实现：

namespace myPriorityQueue{template<class T>struct less //小于{bool operator() (const T& x, const T& y) const{return x < y;}};template<class T>struct greater //大于{bool operator() (const T& x, const T& y) const{return x > y;}};template<class T,class Container = std::vector<T>,class Compare = greater<T>>class priority_queue{public://强制生成默认构造priority_queue() = default;//迭代器区间控制template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last)//用迭代器区间初始化{//建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){/*if (_con[child] > _con[parent])*/if (com(_con[parent], _con[child])) //比较大小用compare来替代{swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}void AdjustDown(int parent){Compare com;int child = parent * 2 + 1; //算出左孩子的位置while (child < _con.size()){//假设法，选出左右孩子大的那个//if (child + 1  _con[child])//如果右孩子大于左孩子if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[child] > _con[parent]) //如果孩子大于父亲if (com(_con[parent], _con[child])){swap(_con[child],_con[parent]);parent = child;child = parent * 2 + 1;}else{break;} }}void push(const T& x){//堆里面插入数据采用的是向上调整算法_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0],_con[_con.size() - 1]);//交换堆顶数据和最后一个数据_con.pop_back(); //删除最后一个数据AdjustDown(0);//向下调整，从根位置开始}bool empty(){return _con.empty();}const T& top(){return _con[0];//返回根位置数据}size_t size(){return _con.size();}private:Container _con;};}

---

支持迭代器控制

---

四. 容器适配器

3.1 什么是适配器

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

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

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

五. deque的介绍

5.1 deque的原理介绍

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

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

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

那deque是如何借助其迭代器维护其假想连续的结构呢？

5.2 deque的缺陷

• 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比vector高的。
• 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
• 但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
• deque之所以不能替代vector和List是因为：下标访问没有vector效率高，中间插入删除没有list效率高

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

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

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

---

👍 如果对你有帮助，欢迎：

• 点赞 ⭐️
• 收藏 📌
• 关注 🔔