stack底层实现细节

一、stack 和 queue

在 STL 中 stack 和 queue 已经不算是容器了，而是容器适配器，适配器模式也是常用的模式之一，体现在 stack 和 queue 中就是他们两个的实现不是单独写的，而是复用了前面合适的优秀的STL 容器的代码而实现的具有 stack 和 queue 特点的容器。

二、部分代码展示

#pragma once
#include<vector>
#include<list>
using namespace std;
namespace bit
{// 适配器模式：封装前面已有的优秀容器实现栈// 模板参数也可以默认，这里默认容器适配器是vector，即复用vector实现stack// queue用list，vector头删效率低template<class T, class Container = vector<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.push_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}T& top(){return _con.back();}private:Container _con;};
}

适配器模式在这里说白了就是用模板来复用 vector 或 list 来实现 stack 的后进先出。

三、vector list deque

容器	优点	缺点
vector	随机访问效率高	头删效率低，扩容有消耗
list	插入删除效率高	访问效率低
deque	兼容 vector list 优点	优点都不极致

deque 支持随机访问，头插头删尾插尾删，但是效率都不够极致。

结构是有一组中控指针数组存放这每一个小数组的指针，可以较快访问，插入，删除。

上面 stack 我们用 vector 和 list 适配，在 STL 中是用 deque 适配