C++ stack、queue以及deque

1、stack和queue常用接口

严格来说栈和队列的实现是容器适配器
1、常用接口：
栈：top、push、pop、size、emptystack - C++ Reference (cplusplus.com)

队列：top、push、pop、swap、size、emptyqueue - C++ Reference (cplusplus.com)

2、deque：双端队列

deque - C++ Reference (cplusplus.com)
queue使用的是deque实现的
deque是一个比较复杂的容器
结合了list和vector的优势
但是，在结构的设计上做出了必要的牺牲
deque是一个一个的小数组，小数组的大小N固定
每一个小数组使用一个中控数组控制
中控数组内部是每一个小数组的开始位置
访问数据第i个数据时：
小数组就是i/N
小数组内部的位置是i%N
同时，中控数组从中间开始开辟，这是为了支持尾插和头插
尾插就是在中控数组空间的右边开辟小数组，进行小数组的头插
头插就是在中控数组空间的左边开辟小数组，但是是小数组的尾插

尽管deque结构的设计使得其在尾插和头插方面具备了list和vector不具备的优势
但是，这样的结构设计也导致了一个致命的弱点：
1、中间插入很麻烦
2、[]访问相对不快，没有vector快
所以说，中间插入不如list，访问遍历不如vector
但是综合来说，已经不错了
所以说，stack和queue的底层是使用deque实现的，因为基本不会有中间插入的场景

3、容器适配器设计模式

栈：

#pragma once
#include<vector>
using namespace std;namespace myspace
{template <class T, class Container = vector<T> >class stack{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}T& top(){return _con.back();}private:Container _con;};};

队列：

#pragma once
#include<deque>
//使用deque实现
using namespace std;namespace mysapce2
{template<class T,class Container = deque<T>>class queue{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}T& front(){return _con.front();}T& back(){return _con.back();}private:Container	_con;};}