C++STL剖析（四）—— stack和queue的概念和使用

---

1. stack的介绍

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

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

也就是说， 「stack」的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

• empty：判空操作
• back：获取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部删除元素操作

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

2. stack的构造

它的构造方式如下：

（1）使用默认的适配器构造一个空栈

stack<int> st1;

（2）使用其他的容器适配器构造一个空栈

stack<int, vector<int>> st2;
stack<int, list<int>> st3;

3. stack的使用

相对于前面学习的容器，「Stack」的接口更简单也更少，基本的使用函数如下。

🍑 push

在堆栈顶部插入一个新元素，位于其当前顶部元素之上。

代码示例

void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);
}

🍑 top

返回堆栈顶部元素的引用。

代码示例

void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);cout << st.top() << endl;
}

运行结果

🍑 pop

删除堆栈顶部的元素，有效地将其大小减小 1。

代码示例

void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);cout << st.top() << endl;st.pop();cout << st.top() << endl;
}

可以看到，最开始栈顶元素是 5，删除以后，就变成了 4

🍑 empty

返回堆栈是否为空，即它的大小是否为 0。

因为栈是不支持遍历的，所以这个接口可以用来实现栈的遍历。

void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()){cout << st.top() << " ";st.pop();}}

运行结果

🍑 size

返回栈中元素的数量。

代码示例

void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);st.push(6);st.push(7);st.push(8);st.push(9);st.push(10);cout << st.size() << endl;
}

运行结果

🍑 swap

将容器适配器（*this）的内容与 x 的内容交换。

其实就是交换两个栈的元素数据。

代码示例

void test_stack()
{stack<int> st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);st1.push(5);stack<int> st2;st2.push(6);st2.push(7);st2.push(8);st2.push(9);st2.push(10);st1.swap(st2);while (!st1.empty()) {cout << st1.top() << " ";st1.pop();}while (!st2.empty()) {cout << st2.top() << " ";st2.pop();}
}

运行结果

🍑 emplace

在栈顶部添加一个新元素，位于其当前顶部元素之上。

在适当的位置构造这个新元素，并将 args 作为其构造函数的参数传递。

代码示例

void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);st.emplace(10);while (!st.empty()) {cout << st.top() << " ";st.pop();}
}

可以看到这个函数确实没啥用处…

4. queue的介绍

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

可以看到「queue」也是作为容器适配器实现的，容器适配器即将特定容器类封装作为其底层容器类，「queue」提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

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

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

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

5. queue的构造

它的构造方式如下：

（1）使用默认的适配器构造一个空栈

queue<int> q1;

（2）使用其他的容器适配器构造一个空栈

queue<int, vector<int>> q2;
queue<int, list<int>> q2;

6. queue的使用

相对于前面学习的容器，「queue」的接口更简单也更少，基本的使用函数如下。

🍑 push

在队列的末尾插入一个新元素，位于当前最后一个元素之后。

代码示例

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);
}

🍑 size

返回队列中元素的数量。

代码示例

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << q.size() << endl;
}

运行结果

🍑 front

返回对队列中下一个元素的引用。

也就是获取队头的元素。

代码示例

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << q.front() << endl;
}

运行结果

🍑 back

返回对队列中最后一个元素的引用。

也就是获取队尾元素。

代码示例

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << q.back() << endl;
}

运行结果

🍑 pop

删除队列中的下一个元素，有效地将其大小减少 1。

也就是删除队头元素

代码示例

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);q.pop(); // 删除队头元素cout << q.size() << endl;cout << q.front() << endl;
}

运行结果

🍑 empty

返回队列是否为空，即队列大小是否为 0。

因为队列是先进先出，不支持遍历的，所以这个接口可以用来实现队列的遍历。

void test_queue()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);q.push(6);while (!q.empty()) {cout << q.front() << " ";q.pop();}}

运行结果

🍑 swap

将容器适配器（*this）的内容与 x 的内容交换。

其实就是交换两个队列中的元素数据。

代码示例

void test_queue()
{queue<int> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);q1.push(5);q1.push(6);queue<int> q2;q2.push(8);q2.push(9);q2.push(10);q1.swap(q2);while (!q1.empty()) {cout << q1.front() << " ";q1.pop();}while (!q2.empty()) {cout << q2.front() << " ";q2.pop();}
}

运行结果

🍑 emplace

在队列的末尾添加一个新元素，位于当前最后一个元素之后。

在适当的位置构造这个新元素，并将 args 作为其构造函数的参数传递。

代码示例

void test_queue()
{queue<int> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);q1.push(5);q1.push(6);while (!q1.empty()) {cout << q1.front() << " ";q1.pop();}q1.emplace(100);while (!q1.empty()) {cout << q1.front() << " ";q1.pop();}
}

这个接口和 stack 一样，没太大用处…

7. 容器适配器

🍑 什么是适配器

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

🍑 stack和queue的底层结构

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

注意：容器支持迭代器，但是容器适配器不支持迭代器，因为栈和队列这种数据结构不能随便去遍历，不然会导致性质不易维护。

🍑 deque的原理介绍

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

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

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

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

🍑 deque的缺陷

「vector」的优缺点：

• 优点：适合尾插尾删，随机访问
• 缺点：不适合头部或者中部插入删除，效率低，需要挪动数据；扩容有一定性能消耗，还可能存在一定程度的空间浪费。

「list」的优缺点：

• 优点：任意位置插入删除效率高；按需申请释放空间。
• 缺点：不支持随机访问；cpu 高速缓存命中低

「deque」就是结合了「vector」和「list」的优缺点而发明的！！！

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

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

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

「deque」的应用并不多，而目前能看到的一个应用就是，STL 用其作为「stack」和「queue」的底层数据结构。

🍑 选择deque的原因

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

「stack」是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为「stack」的底层容器，比如「vector」和「list」都可以；

「queue」是先进先出的特殊线性数据结构，只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为「queue」的底层容器，比如「list」。

但是 STL 中对「stack」和「queue」默认选择「deque」作为其底层容器，主要是因为：

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

总的来说，就是结合了「deque」的优点，而完美的避开了其缺陷。

8. 模拟实现「stack」和「queue」

🍑 stack的模拟实现

关于 stack 的模拟实现很简单，主要就是针对一些常用的接口，具体代码如下：

namespace edc
{template<class T, class Container = deque<T>>class Stack{public:// 入栈void push(const T& x){_con.push_back(x);}// 出栈void pop(){_con.pop_back();}// 获取栈顶元素T& top(){return _con.back();}const T& top() const{return _con.back();}//获取栈中有效元素个数size_t size() const{return _con.size();}//判断栈是否为空bool empty() const{return _con.empty();}//交换两个栈中的数据void swap(Stack<T, Container>& st){_con.swap(st._con);}private:Container _con;};// 测试函数void test_stack(){Stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);st.push(6);cout << "栈中元素个数：" << st.size() << endl;cout << "出栈顺序：";while (!st.empty()) {cout << st.top() << " ";st.pop();}}
}

测试结果：

🍑 queue的模拟实现

关于 queue 的模拟实现也很简单，主要就是针对一些常用的接口，具体代码如下：

namespace edc
{template<class T, class Container = deque<T>>class Queue{public:// 入队void push(const T& x){_con.push_back(x);}// 出队void pop(){_con.pop_front();}// 获取队头元素T& front(){return _con.front();}const T& front() const{return _con.front();}// 获取队尾元素T& back(){return _con.back();}const T& back() const{return _con.back();}//获取队列中有效元素个数size_t size() const{return _con.size();}//判断队列是否为空bool empty() const{return _con.empty();}//交换两个栈中的数据void swap(Queue<T, Container>& q){_con.swap(q._con);}private:Container _con;};// 测试函数void test_queue(){Queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);q.push(6);q.push(7);cout << "队列中元素个数：" << q.size() << endl;cout << "出队顺序：";while (!q.empty()) {cout << q.front() << " ";q.pop();}}
}

测试结果：

9. 总结

对于栈和队列，我相信只要数据结构的基础还不错，那么本篇文章的接口函数肯定是手到擒来！

最后我们再看一下栈和队列在实际生活中的应用吧。

栈典型应用：

• 浏览器中的后退与前进、软件中的撤销与反撤销。 每当我们打开新的网页，浏览器就讲上一个网页执行入栈，这样我们就可以通过「后退」操作来回到上一页面，后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么则需要两个栈来配合实现。
• 程序内存管理。 每当调用函数时，系统就会在栈顶添加一个栈帧，用来记录函数的上下文信息。在递归函数中，向下递推会不断执行入栈，向上回溯阶段时出栈。

队列典型应用：

• 淘宝订单。 购物者下单后，订单就被加入到队列之中，随后系统再根据顺序依次处理队列中的订单。在双十一时，在短时间内会产生海量的订单，如何处理「高并发」则是工程师们需要重点思考的问题。
• 各种待办事项。 例如打印机的任务队列、餐厅的出餐队列等等。