留住用户网站百度站长工具网站提交
一、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 适配