深入解析：【C++】stack|queue|deque

容器适配器

什么是适配器？

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

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

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

---

一、stack

1. stack的介绍和使用

• stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
• stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
• stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
  empty：判空操作
  back：获取尾部元素操作
  push_back：尾部插入元素操作
  pop_back：尾部删除元素操作
• 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。（下面我们模拟实现的时候先使用vector来实现。）

栈常见的基本接口：

---

2. stack的模拟实现

由于我们上面大概介绍了一下容器适配器，所以这里我们使用适配器作为类的第二个模板参数。并将类的第二个模板参数的缺省值设置为vector<T>类型，因为无论从在后面我们可以通过给定第二个模板参数来使用不同的容器适配stack。有了适配容器后，我们就可以通过调用适配容器的接口实现stack的接口了。

namespace cjl
{
//适配器模式
template<class T,class Container = vector<T>>class stack{private:Container _con;};#pragma once#include<iostream>using namespace std;#include<vector>#include<list>namespace cjl{//适配器模式template<class T,class Container = vector<T>>class stack{public://压栈void push(const T& x){_con.push_back(x);}//出栈void pop(){_con.pop_back();}//取栈顶元素const T& top(){return _con.back();}//栈的判空操作bool empty(){return _con.empty();}//取栈中元素个数size_t size(){return _con.size();}private:Container _con;};}

3. stackOJ习题

最小栈

解题思路：

开两个栈，一个普通的栈和一个_minst，_minst是一个专门用来记录最小值
的栈，当插入的元素小于等于_minst栈顶元素或者_minst栈中为空时，就将该元素插入_minst栈中，如果要是插入的元素比_minst栈中的元素大时，就将该元素插入另一个栈中。

当pop元素时，如果pop的元素和_minst中的top元素相等时，弹出_minst中的栈顶元素，否则仅仅弹出普通栈中的元素。这样我们每次都弹出_minst的栈顶元素时，都一定会是最小值。

解题代码：

class MinStack {
public:
MinStack()
{}
void push(int val) {
_st.push(val);
if(_minst.empty() || val <= _minst.top())
_minst.push(val);
}
void pop() {
if(_minst.top()==_st.top())
_minst.pop();
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
private:
stack<int> _st;stack<int> _minst;};

---

栈的压入、弹出序列

解题思路：

这道题的大思路是模拟入栈和出栈的过程，入栈的同时，如果发现栈顶的元素和需要出栈的元素相同且栈不为空，那就以此作为循环条件持续出栈。如果元素全部入栈且经过循环条件全部出栈，那么栈最后一定为空栈，所以最后判断栈是否为空栈即可。

解题代码：

class Solution {
public:
//模拟入栈和出栈的过程
bool IsPopOrder(vector<int> pushV,vector<int> popV) {int pushi = 0,popi = 0;//利用入栈来控制外循环while(pushi<pushV.size()){st.push(pushV[pushi++]);while(!st.empty()&&st.top()==popV[popi]){st.pop();popi++;}}return st.empty();}private:stack<int> st;};

---

逆波兰表达式求值

解题思路：

这道题的核心思路是根据逆波兰表达式（后缀表达式）来计算结果，思路如下：我们先开一个栈，遍历vector容器中的每一个字符串，遇到运算数就入栈，遇到运算符依次取栈顶元素作为右操作数和左操作数。然后再进行运算，运算后将元素入栈，继续下一次的遍历，直到将vector容器中的元素全部遍历完成。

解题代码：

class Solution {
public:
int evalRPN(vector<string>& tokens) {stack<int> st;for(auto& e:tokens){if(e=="+" || e=="-" || e=="*" || e=="/"){int right = st.top();st.pop();int left = st.top();st.pop();switch(e[0]){case '+':st.push(left + right);break;case '-':st.push(left - right);break;case '*':st.push(left * right);break;case '/':st.push(left / right);break;}}else{st.push(stoi(e));}}return st.top();}};

---

二、queue

1. queue的介绍和使用

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
   empty：检测队列是否为空
   size：返回队列中有效元素的个数
   front：返回队头元素的引用
   back：返回队尾元素的引用
   push_back：在队列尾部入队列
   pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

队列常见的基本接口

---

2. queue的模拟实现

namespace cjl
{
template<class T,class Container = list<T>>class queue{public://入队void push(const T& x){_con.push_back(x);}//出队void pop(){_con.pop_front();}//返回队首元素const T& front(){return _con.front();}//返回队尾元素const T& back(){return _con.back();}//返回队列中元素个数size_t size(){return _con.size();}//队列判空操作bool empty(){return _con.empty();}private:Container _con;};}

---

三、deque

1. deque的原理介绍

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

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

---

2. deque的迭代器设计

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

---

3. deque的优缺点

deque的优点如下：

• 具有vector支持随机访问、缓存命中率高的优点。
• 头插头删、尾插尾删效率高，同时他相对于vector来说，扩容代价更低。

deque的缺点：

• deque的中间插入删除比较难搞，因为需要挪动数据，但是它只需要挪动一部分数据，所以它的中间插入数据的效率是比vector高但是比list低。
• deque的随机访问效率比较低，因为需要先通过中控数组找到对应的buffer数组，然后再找具体的位置。如果要是从头开始找的话，那就需要一次跳过一个buffer数组，然后跳动多次后才能定位具体数组的具体位置，所以它的效率是比list要高的，但是vector低。
• 序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

虽然deque有以上的缺点和不足，但是他也有自己的用途：适合做stack和deque的默认适配容器。具体原因如下：

• stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
• stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
• 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。

//queue
namespace cjl
{
template<class T,class Container = deque<T>>class queue{public://入队void push(const T& x){}//...private:Container _con;};}//stacknamespace cjl{//适配器模式template<class T,class Container = deque<T>>class stack{public://压栈void push(const T& x){}//...private:Container _con;};}