C++ : STL容器（适配器）之stack、queue剖析
STL容器适配器之stack、queue剖析
一、stack、queue的接口
（一）stack 接口说明
- stack()
- 构造空的栈
- empty()
- 检测stack是否为空
- size()
- 返回stack中元素的个数
- top()
- 返回栈顶元素的引用
- push()
- 将元素val压入stack中
- pop()
- 将stack中尾部的元素弹出
（二）queue 接口说明
- empty：
- 检测队列是否为空
- size：
- 返回队列中有效元素的个数
- front：
- 返回队头元素的引用
- back：
- 返回队尾元素的引用
- push_back：
- 在队列尾部入队列
- pop_front：
- 在队列头部出队列
二、stack、queue的模拟实现
（一）stack、queue是容器适配器
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque.
stack、queue底层默认容器–deque
1、deque概念及原理
deque(双端队列)：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个
动态的二维数组，其底层结构如下图所示：
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问
的假象，落在了deque的迭代器身上
2、stl中deque迭代器的实现（部分）
在stl源码实现中，下面截取了迭代器的部分，有很多知识值得学习。
1、普通迭代器和const迭代器实现技巧我们知道const对象的实现就是不能修改值，因此只需要在实现迭代器时针对一下->和*的返回值即可，源码库中使用两个模板参数巧妙的解决这个问题。
2、非类型模板参数在模板进阶中我们会讲到非类型模板参数的使用，使用size_t作为参数相当于一个宏的使用。template <class T, class Ref, class Ptr, size_t BufSiz>
3、重载的复用先实现重载符号 += 接着的 +、-、-=都采用了复用的方式，使得代码更简洁。
在实现++、–时，先实现前置++，前置–，再实现后置++，后置–，这里也可以复用
#pragmaoncetemplate<classT,classRef,classPtr, size_t BufSiz>struct__deque_iterator{typedef __deque_iterator<T, T&, T*, BufSiz> iterator;typedef __deque_iterator<T,const T&,const T*, BufSiz> const_iterator;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef T** map_pointer;typedef ptrdiff_t difference_type;typedef __deque_iterator self;//构造函数//有参构造__deque_iterator(T* x, map_pointer y):cur(x),first(*y),last(*y +buffer_size()),node(y){}//默认构造__deque_iterator():cur(0),first(0),last(0),node(0){}//拷贝构造__deque_iterator(const iterator& x):cur(x.cur),first(x.first),last(x.last),node(x.node){}//更新结点信息voidset_node(map_pointer new_node){ node = new_node; first =*new_node; last = first +difference_type(buffer_size());}//运算符重载 reference operator*()const{return*cur;} pointer operator->()const{return&(operator*());} self&operator++(){++cur;if(cur == last){set_node(node +1); cur = first;}return*this;} self operator++(int){ self tmp =*this;++*this;return tmp;} self&operator--(){if(cur == first){set_node(node -1); cur = last;}--cur;return*this;} self operator--(int){ self tmp =*this;--*this;return tmp;} self&operator+=(difference_type n){ difference_type offset = n +(cur - first);if(offset >=0&& offset <difference_type(buffer_size())) cur += n;else{ difference_type node_offset = offset >0? offset /difference_type(buffer_size()):-difference_type((-offset -1)/buffer_size())-1;set_node(node + node_offset); cur = first +(offset - node_offset *difference_type(buffer_size()));}return*this;} self operator+(difference_type n)const{ self tmp =*this;return tmp += n;} self&operator-=(difference_type n){return*this+=-n;} self operator-(difference_type n)const{ self tmp =*this;return tmp -= n;} reference operator[](difference_type n)const{return*(*this+ n);}booloperator==(const self& x)const{return cur == x.cur;}booloperator!=(const self& x)const{return!(*this== x);}booloperator<(const self& x)const{return(node == x.node)?(cur < x.cur):(node < x.node);}//成员变量private: T* cur; T* first; T* last; map_pointer node;};（二）stack的模拟实现
通过stack的实现可以看出，stack的实现是基于deque。栈的实现就是将双端队列进行包装，这个过程就像是deque是交流电，而stack就是这个插头，为用户提供需要的接口。
#pragmaonce#include<vector>#include<list>#include<deque>usingnamespace std;namespace wgm {template<classT,classContainer= deque<T>>classstack{public:voidpush(const T& val){ _con.push_back(val);}voidpop(){ _con.pop_back();}boolempty()const{return _con.empty();} size_t size()const{return _con.size();}const T&top()const{return _con.back();}private: Container _con;};}（三）queue的模拟实现
和stack类似，在它的参数列表中也有一个参数类型Container(容器），它也存在默认参数deque。这里的参数不能传入vector,因为vector不支持头部出元素的pop_front操作。
#pragmaonce#include<vector>#include<list>#include<deque>usingnamespace std;namespace wgm {template<classT,classContainer= deque<T>>classqueue{public:voidpush(const T& val){ _con.push_back(val);}voidpop(){ _con.pop_front();}boolempty()const{return _con.empty();} size_t size()const{return _con.size();}const T&front()const{return _con.front();}const T&back()const{return _con.back();}private: Container _con;};}三、优先队列
（一）优先队列的概念
优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大（小）的。实际上，这就和之前学过的数据结构堆的性质一样。
（二）优先队列的接口说明
- empty()：
- 检测容器是否为空
- size()：
- 返回容器中有效元素个数
- front()：
- 返回容器中第一个元素的引用
- push_back()：
- 在容器尾部插入元素
- pop_back()：
- 删除容器尾部元素
（三）优先队列的模拟实现
#pragmaonce#include<vector>#include<iostream>usingnamespace std;namespace wgm {template<classT>structless{booloperator()(const T& x,const T& y)const{return x < y;}};template<classT>structgreater{booloperator()(const T& x,const T& y)const{return x > y;}};template<classT,classContainer= vector<T>,classCompare= less<T>>classpriority_queue{public:#defineFATHER(i)(((i)-1)/2)#defineLEFT(i)(((i)*2)+1)#defineRIGHT(i)(((i)*2)+2)voidAdjustUp(int i){ Compare cmp;while(FATHER(i)>=0&&Compare()(_con[FATHER(i)], _con[i])){swap(_con[i], _con[FATHER(i)]); i =FATHER(i);}}voidAdjustDown(int i){while(LEFT(i)< _con.size()){int l =LEFT(i), r =RIGHT(i), ind = i; Compare cmp;if(cmp(_con[ind], _con[LEFT(i)])) ind =LEFT(i);if(RIGHT(i)< _con.size()&&cmp(_con[ind], _con[RIGHT(i)])) ind =RIGHT(i);if(ind == i)break;swap(_con[i], _con[ind]); i = ind;}}voidpush(const T& val){ _con.push_back(val);AdjustUp(_con.size()-1);}voidpop(){swap(_con[0], _con[_con.size()-1]); _con.pop_back();AdjustDown(0);}boolempty(){return _con.empty();}const T&top(){return _con[0];} size_t size(){return _con.size();}private: Container _con;};}四、结束语
这个部分相对于之前学的容器要简单，只不过这个双端队列的实现源码还是挺有意思的，可以尝时着实现实现。
