九、stack和queue
1. stack和queue的介绍
stack 就是我们常说的 栈 ，而 queue 就是 队列 。栈就是 后进先出 的数据结构，队列就是 先进先出 的数据结构。从严格意义上来讲，这里的栈和队列已经不属于 容器 了，而是属于 容器适配器 。什么是 容器适配器 呢，我们待会再说。
2. stack和queue的使用
stack 和 queue 的使用非常简单。
栈就这么多接口，其中绝大部分接口我们已经非常非常熟悉了。
队列也只有这么点接口，同样我们都非常熟悉了。
我们发现，栈和队列有一个共同点：他们都不支持迭代器 。为什么呢？因为栈和队列有自己的输入和输出规则，栈是 后进先出 ，队列是 先进先出 ，而迭代器可能会打破这个规则，所以他们俩都不支持迭代器。
#include<iostream> #include<stack> #include<queue> using namespace std; int main() { 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(); } cout << endl; return 0; }
3. stack和queue的模拟实现
在 STL库 里，这俩其实是通过 适配器模式 实现的。适配器是什么意思呢？他就像电源转换器一样，将多少多少伏特电压转换成多少多少伏特电压。具有 转换 的功能。我们一般都是通过循序结构来实现栈和队列的，但是既然我们已经学了 vector 和 list ，所以我们就能把 vector 和 list 拿过来使用。
#pragma once #include<vector> #include<list> namespace my { template<class T, class Container> class stack { public: private: Container _con; }; }
在这里，如果是数组栈，那我们第二个参数传 vector 即可，如果是链式栈，那第二个参数传 list 即可。
// 数组栈 stack<int, vector<int>>; // 链式栈 stack<int, list<int>>;
这样实现的栈就是 适配器模式的栈 ，通过容器适配出来的栈。
所以说，我们栈所需要的函数和结果，通过调用其他容器的函数就行。我们来见证一下：首先创建一个 Stack.h 头文件。
// Stack.h #pragma once #include<vector> #include<list> namespace my { template<class T, class Container> class stack { public: void push(const T& x) { // 栈是栈顶入栈 _con.push_back(x); } void pop() { // 栈顶出栈 _con.pop_back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } const T& top() { return _con.back(); } private: Container _con; }; }
是不是很震惊？没错，调用其他容器的函数就能实现栈。我们来测试一下：
// test.cpp #include<iostream> #include"Stack.h" using namespace std; void test01() { my::stack<int, vector<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(); } cout << endl; } int main() { test01(); return 0; }
跟我们想的栈几乎没区别好吧。仅仅只是创建对象的时候需要两个参数而已，但是 STL库 里的栈和队列就没有第二个参数，我们需要将第二个参数给优化掉。怎么优化呢？ 缺省参数 。
// 函数模板给缺省参数就能够解决问题。 template<class T, class Container = vector<T>> class stack { public: // private: Container _con; };
这下若是使用数组栈，就可以只传一个参数了。
#include<iostream> #include"Stack.h" #include<queue> using namespace std; void test01() { my::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(); } cout << endl; } int main() { test01(); return 0; }
栈的实现这么简单，队列的实现同样非常简单，这里我直接给代码了：
#pragma once #include<list> namespace my2 { template<class T, class Container = list<T>> class queue { public: void push(const T& x) { // 尾部入队列 _con.push_back(x); } void pop() { // 头部出队列 _con.pop_front(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } const T& back() { return _con.back(); } const T& front() { return _con.front(); } private: Container _con; }; }
测试一下：
#include<iostream> #include"Queue.h" using namespace std; void test02() { my2::queue<int> q; q.push(1); q.push(2); q.push(3); q.push(4); q.push(5); while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; } int main() { test02(); return 0; }
4. deque的简单了解
deque 是什么？deque 是 双端队列 。但其本质不是队列，它并不要求先进先出。它集合了 vector 和 list 的优点。
vector的优缺点
优点：支持下标随机访问。
缺点：头部或者中间插入/删除效率低，扩容有消耗
list的优缺点
优点：支持任意位置插入/删除，效率都不错。
缺点：不支持下标随机访问。
那我们还需要使用 vector 和 list 吗？当然要使用，不然我们学他们干什么哈哈。deque 就像是一个链表，每个节点存的都是一个小数组，然后通过一个 中控指针数组 来指向每一个节点的地址，就像 页表 一样。可以快速访问数据。由于 deque 支持头插和尾插，所以 中控指针数组一开始只能在中间 ，头插的时候中控指针数组往左延申，尾插的时候往右延申。当中控指针数组满的时候给其扩容。
由于 deque 的逻辑难度和实现难度都比之前的难不少，这里就不再详细实现，通过看文档了解即可。
deque的优缺点
优点：头插/尾插的效率很好。
缺点：中间插入会非常麻烦，效率一般，[]访问的效率不够极致。
在 STL库 里的栈和队列当中，默认容器都是 deque ，原因就是 deque的头尾插入删除很优秀 ，而栈和队列也仅仅支持头尾插入删除。
