本文主要是介绍十六、栈和队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Ⅰ . stack 类
01 栈的概念
栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作
进行数据插入和删除操作的一端叫做 栈顶，另一端叫做 栈底
栈中的元素遵守后进先出的原则，即 LIFO原则（Last In First Out）
压栈：栈的插入操作叫做进栈 / 压栈 / 入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈，出数据也在栈顶
02 stack 的介绍
文档介绍：stack - C++ Reference
① stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作
② stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部（即栈顶）被压入和弹出
③ 标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器，默认情况下使用 deque
④ stack 的底层容器可以是任何标准的容器模板或者一些其他特定的容器类，这些容器应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
通过观察文档我们不难发现，接口相较于之前的 string、vector 和 list 少了很多
甚至连拷贝构造和析构都没有自己实现，然而这些都得益于容器适配器的使用
不难发现，stack 、queue 也没有迭代器
03 stack 的使用
代码演示：
#include<iostream>
#include<stack>
using namespace std;void test_stack()
{/* 创建一个存储整型的栈 */stack<int> st;/* 入栈 */st.push(1);st.push(2);st.push(3);st.push(4);/* 打印栈 */while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;
}运行结果如下：4 3 2 1
Ⅱ . queue 类
01 队列的概念
队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
入队列时，进行插入操作的一端称为 队尾，出队列时，进行删除操作的一端称为 队头
队列中的元素遵守先进先出的原则，即 FIFO原则（First In First Out）
02 queue 的介绍
文档介绍：queue - C++ Reference
① 队列是一种容器适配器，专门用在先进先出上下文中操作，其中从一端插入元素，从另一端提取元素
② 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素，元素从队尾入队列，从 队头出队列
③ 标准容器 deque、list 符合这些需求，默认情况下，如果没有为 queue 指定特定的底层容器，默认情况下使用 deque
④ queue 的底层容器可以是任何标准的容器模板或者一些其他特定的容器类，这些容器应该支持以下操作：
empty：判空操作
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
03 queue 的使用
代码演示：
#include<iostream>
#include<stack>
#include<queue>
using namespace std;void test_queue()
{/* 创建一个存储整型的队列 */queue<int> Q;/* 入队 */Q.push(1);Q.push(2);Q.push(3);Q.push(4);/* 打印队列 */while (!Q.empty()){cout << Q.front() << " ";Q.pop();}cout << endl;
}运行结果如下：1 2 3 4
Ⅲ . 优先级队列（priority queue）
01 priority queue 的介绍
文档介绍：priority queue - C++ Reference
① 优先级队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是比它所包含的元素中最大的
② 此上下文类似堆，在堆中可以随时插入元素，并且只能检索最大堆元素
③ 优先级队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素，元素从特定容器的尾部弹出，其称为优先级队列的顶部
④ 标准容器类 vector 和 deque 满足这些需求，默认情况下，如果没有为特定的 priority queue 类实例化指定容器类，则默认使用 vector
⑤ 需要支持随机访问迭代器，以便始终在内部保持堆结构，容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作
⑥ 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类，容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty：判空操作
size：返回容器中有效元素的个数
front：返回容器中第一个元素的引用
push_back：在容器尾部插入元素
pop_back：删除容器尾部元素
02 优先级队列的使用
优先级队列默认使用 vector 作为其底层存储数据的容器
在 vector 上又使用堆算法将 vector 中元素构造成堆的结构，因为优先级队列就是堆
所有需要用到堆的地方，都可以考虑使用优先级队列
值得注意的是，优先级队列默认为大根堆
优先级队列默认大的优先级高，传的是 less 仿函数，底层是一个大堆
如果想控制小的优先级高，需要手动传 greater 仿函数，其底层是一个小堆
代码演示：默认大的优先级高
#include<iostream>
#include<stack>
#include<queue>
#include<functional>
using namespace std;void test_priority_queue()
{priority_queue<int> pQ;pQ.push(2);pQ.push(5);pQ.push(1);pQ.push(6);pQ.push(8);while (!pQ.empty()){cout << pQ.top() << " ";pQ.pop();}cout << endl;
}运行结果如下：8 6 5 2 1
默认是用 vector 存储的，注意这里没有明确指定 less 还是 greater，所以默认是 less
代码演示：小的优先级高
我们前面说了，优先级队列默认使用 vector 作为其底层存储数据的容器
但也可以使用其他容器去存储，比如 list
#include<stack>
#include<queue>
#include<functional>
using namespace std;void test_priority_queue()
{priority_queue<int, vector<int>, greater<int>> pQ;pQ.push(2);pQ.push(5);pQ.push(1);pQ.push(6);pQ.push(8);while (!pQ.empty()){cout << pQ.top() << " ";pQ.pop();}cout << endl;
}运行结果如下：1 2 5 6 8
我们在定义优先级队列时主动去传 greater<int> 即可令该优先级队列以小的优先级高
注意：如果想传第三个模板参数，必须得先传第二个
下面是定义：
template <class T, class Container = vector<T>,class Compare = less<typename Container::value_type> > class priority_queue;Ⅳ . 双端队列（double ended queue）
01 deque 的介绍
deque 是一种双开口的连续空间的数据结构，deque 可以在头尾两端进行插入和删除操作
且时间复杂度为 ，与 vector 相比，头插效率高，不需要搬移元素
与 list 相比，deque 的空间利用率更高。
02 deque 的实现原理
deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的
实际的 deque 类似于一个动态的二维数组，其底层结构如下所示：
双端队列底层是一个假想的连续空间，实际是分段连续
为了维护其整体连续，以及随机访问的假象，其重任落在了 deque 的迭代器身上
因此 deque 的迭代器设计尤为复杂，如下图所示：
那 deque 是如何借助其他迭代器维护其假想连续的结构呢？
03 deque 的缺陷
deque 有点像 vector 和 list 的结合体
那什么场景下适合用 deque 呢？
大量头尾插入删除，偶尔随机访问的情况可以使用 deque
04 deque stack 和 queue 的底层默认容器
在 stack 和 queue 的实现上，是选择 deque 作为底层默认容器的
那为什么选择 deque 作为默认底层容器呢？
① stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back 和 pop_back 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以
② queue 是先进先出的特殊线性数据结构，只要具有 push_back 和 pop_back 操作的线性结构，都可以作为 queue 的底层容器，比如 list
但 STL 最终选择用 deque ，其主要原因如下：
① stack 和 queue 不需要遍历，只需要在固定的一端或者两端进行操作
② 在 stack 中元素增长时， deque 比 vector 的效率高，queue 中的元素增长时， deque 不仅效率高，而且内存使用率高，结合了 deque 的优点完美避开了其缺陷
这篇关于十六、栈和队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
