C++ stack与queue的使用与简单实现
目录
0. 适配器
1. stack的简要介绍
2. stack的简单使用
3. queue的简要介绍
4. queue的简单使用
STL标准库中stack和queue的底层结构
deque简单介绍
5. stack的模拟实现
6. queue的模拟实现
0. 适配器
在文章开始前我们先了解一下适配器的概念
适配器是一种设计模式(设计模式是一套被反复使用的，多数人知晓的，经过分类编目的，代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
1. stack的简要介绍
是一个容器适配器，提供了后进先出(或先进后出)的数据结构，其元素仅能从容器的一端插入和提取。
使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的背面出栈
2. stack的简单使用
| 函数说明 | 接口说明 |
| stack() | 构造空的栈 |
| empty() | 检测stack |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中最后入栈的元素弹出 |
如下代码所示
#include<iostream>
#include<stack>
#include<queue>
using namespace std;int main()
{stack<int> st;st.push(1);//往栈里压入元素st.push(12);st.push(123);st.push(1234);while (!st.empty())//如果栈里没有元素了就停止循环{cout << "栈里的元素个数为: " << st.size() << " 栈顶的元素为: " << st.top() << endl;st.pop();//删除栈里的元素，后进来的先出去，所以先删1234}return 0;
}输出结果如下图所示
验证了我们所说的后入栈的先出栈，而栈顶的元素就是最后入栈的元素(如果入栈过程中没有元素提前pop出栈)。
3. queue的简要介绍
队列是一种容器适配器，专门用于先进先出中操作，从容器一端插入元素，另一端提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
4. queue的简单使用
| 函数声明 | 接口说明 |
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空，是返回true，否则返回false |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素val入队 |
| pop() | 将队头元素出队列 |
标准容器类deque和list满足了这些要求，如果我们没为queue实例化指定容器类(没使用下方定义)，则其默认使用deque。
queue<int,list<int>> qu;代码如下
#include<iostream>
#include<stack>
#include<queue>
#include<list>
using namespace std;int main()
{//queue<int,list<int>> qu;queue<int> qu;qu.push(1);//元素入队qu.push(12);qu.push(123);qu.push(1234);while (!qu.empty())//如果队列里里没有元素了就停止循环{cout << "队列里的元素个数为: " << qu.size() << " 队头的元素为: " << qu.front()<<" 队尾的元素为: " << qu.back()<< endl;qu.pop();//删除队列里的元素，先进来的先出去，所以先删1}return 0;
}输出结果如下
可以直观的看到，先入队的队头元素先出队了，后入队的队尾元素后出队
STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque
deque简单介绍
deque(双端队列)：是一种双开口的“连续”空间的数据结构，双开口的含义是: 可以在头尾两端进行插入和删除操作，且时间复杂度为O(1),与vector比较，头插效率高，不需要搬移元素；与list比较空间利用率比较高。
其并不是真正的连续的空间，而是由一段段连续的小空间拼接而成，实际deque类似一个动态的二维数组
双端队列底层是一段假想的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，就交给deque的迭代器了，所以deque的迭代器设计就比较复杂
迭代器元素与功能大致有
1. cur :用来遍历当前数组
2. first :指向一个数组的头
3. last :指向一个数组的尾
4. node :指向一个数组
优：
- 与vector相比：头插(如果前面没有空间了，就在前面再开一个数组，将元素插入新开辟数组的最后的位置)和尾删时，不需要搬移元素，效率特别高，而且在扩容时也不需要搬移大量的元素，因此效率比vector高
- 与list相比：其底层有连续空间，空间利用率比较高，不需要存储额外字段
劣：
不适合遍历，在遍历时deque的迭代器要去频繁地检测其是否移动到某段小空间的边界，导致效率低下，而有些场景中可能经常需要遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，STL用其作为stack和queue的底层数据结构。
5. stack的模拟实现
默认使用deque的原因
1. 头插头删效率极高，又不需要遍历
2. 扩容不用搬移元素，比vector强
实现非常简单，我们用容器自带的接口来实现即可
#include<iostream>
#include<deque>
#include<list>
#include<vector>
using namespace std;
namespace Pc
{//template<class T, class container = vector<T> >//template<class T, class container = list<T> >template<class T, class container = deque<T> >class stack{public:stack(){}void push(const T& x){_sta.push_back(x);}void pop(){_sta.pop_back();}T& top(){return _sta.back();//传最后的引用返回}const T& top() const{return _sta.back();//传最后的引用返回}size_t size() const{return _sta.size();}bool empty(){return _sta.empty();}private:container _sta;};
}由于我们上面的push_back、pop_back、size等无论list、vector还是deque都有所以这三个容器都可以实现
6. queue的模拟实现
默认使用deque的原因
1. 依然是不需要遍历，只需要尾插头删(vector没有头删)
2. deque元素在内存中相对集中，减少了缓存未命中的次数，提高程序运行效率。list元素太过分散，缓存命中率低
实现代码如下
#include<iostream>
#include<deque>
#include<list>
#include<vector>
using namespace std;
namespace Pc
{//template<class T, class container = list<T> >template<class T, class container = deque<T> >class queue{public:queue(){}void push(const T& x){_que.push_back(x);}void pop(){_que.pop_front();}T& back(){return _que.back();//传最后的引用返回}const T& back() const{return _que.back();//传最后的引用返回}T& front(){return _que.front();//传最后的引用返回}const T& front() const{return _que.front();//传最后的引用返回}size_t size() const{return _que.size();}bool empty(){return _que.empty();}private:container _que;};
}这篇就到这里啦~（づ￣3￣）づ╭❤～