stack介绍
stack模拟实现
以前我们实现stack，需要像list,vector一样手动创建成员函数，成员变量。但是stack作为容器适配器，我们有更简单的方法来实现它。
可以利用模板的强大之处！
namespace xty { template<class T, class Container = deque<T>> //template<class T, class Container = vector<T>> class stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } const T& top() { return _con.back(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; }; }
该段代码使用了vector当作了默认的模板容器，这样可以使我们的代码量和复杂度大大减少。
queue 介绍
queue模拟实现
queue也是一个容器适配器，因此我们使用现有的容器当作模板，即可简便的实现queue功能。
template<class T, class Container = deque<T>> //template<class T, class Container = list<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } const T& front() { return _con.front(); } const T& back() { return _con.back(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; };
只需修改少量代码即可完成复现。
deque
观察stack和queue的容器模板后，发现其实是deque，那这个容器是什么样的呢？
从官方库中可以发现，它既有vector的随机访问的优点，也有list插入删除的优点。但是都并没有将二者效率发挥到极致，是一个折中的容器。
具体图例如下：
缺点：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
