一、stack、queue的接口

（一）stack 接口說明

• stack()
  • 構造空的棧
• empty()
  • 檢測stack是否為空
• size()
  • 返回stack中元素的個數(shù)
• top()
  • 返回棧頂元素的引用
• push()
  • 將元素val壓入stack中
• pop()
  • 將stack中尾部的元素彈出

（二）queue 接口說明

• empty：
  • 檢測隊列是否為空
• size：
  • 返回隊列中有效元素的個數(shù)
• front：
  • 返回隊頭元素的引用
• back：
  • 返回隊尾元素的引用
• push_back：
  • 在隊列尾部入隊列
• pop_front：
  • 在隊列頭部出隊列

二、stack、queue的模擬實現(xiàn)

（一）stack、queue是容器適配器

雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和queue只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque.

stack、queue底層默認容器–deque

1、deque概念及原理

deque(雙端隊列)：可以在頭尾兩端進行插入和刪除操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。

deque并不是真正連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成的，實際deque類似于一個
動態(tài)的二維數(shù)組，其底層結(jié)構如下圖所示：

雙端隊列底層是一段假象的連續(xù)空間，實際是分段連續(xù)的，為了維護其“整體連續(xù)”以及隨機訪問
的假象，落在了deque的迭代器身上

2、stl中deque迭代器的實現(xiàn)（部分）

在stl源碼實現(xiàn)中，下面截取了迭代器的部分，有很多知識值得學習。

1、普通迭代器和const迭代器實現(xiàn)技巧

我們知道const對象的實現(xiàn)就是不能修改值，因此只需要在實現(xiàn)迭代器時針對一下->和*的返回值即可，源碼庫中使用兩個模板參數(shù)巧妙的解決這個問題。

2、非類型模板參數(shù)

在模板進階中我們會講到非類型模板參數(shù)的使用，使用size_t作為參數(shù)相當于一個宏的使用。
template <class T, class Ref, class Ptr, size_t BufSiz>

3、重載的復用

先實現(xiàn)重載符號 += 接著的 +、-、-=都采用了復用的方式，使得代碼更簡潔。
在實現(xiàn)++、–時，先實現(xiàn)前置++，前置–，再實現(xiàn)后置++，后置–，這里也可以復用

#pragma once
template <class T, class Ref, class Ptr, 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;//構造函數(shù)//有參構造__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) {}//更新結(jié)點信息void set_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); }bool operator==(const self& x) const { return cur == x.cur; }bool operator!=(const self& x) const { return !(*this == x); }bool operator<(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的模擬實現(xiàn)

通過stack的實現(xiàn)可以看出，stack的實現(xiàn)是基于deque。棧的實現(xiàn)就是將雙端隊列進行包裝，這個過程就像是deque是交流電，而stack就是這個插頭，為用戶提供需要的接口。

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

（三）queue的模擬實現(xiàn)

和stack類似，在它的參數(shù)列表中也有一個參數(shù)類型Container(容器），它也存在默認參數(shù)deque。這里的參數(shù)不能傳入vector,因為vector不支持頭部出元素的pop_front操作。

#pragma once
#include<vector>
#include<list>
#include<deque>
using namespace std;namespace wgm {template<class T, class Container = deque<T>>class queue {public:void push(const T& val) {_con.push_back(val);}void pop() {_con.pop_front();}bool empty() 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;};
}

三、優(yōu)先隊列

（一）優(yōu)先隊列的概念

優(yōu)先隊列是一種容器適配器，根據(jù)嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大（小）的。實際上，這就和之前學過的數(shù)據(jù)結(jié)構堆的性質(zhì)一樣。

（二）優(yōu)先隊列的接口說明

• empty()：
  • 檢測容器是否為空
• size()：
  • 返回容器中有效元素個數(shù)
• front()：
  • 返回容器中第一個元素的引用
• push_back()：
  • 在容器尾部插入元素
• pop_back()：
  • 刪除容器尾部元素

（三）優(yōu)先隊列的模擬實現(xiàn)

#pragma once
#include<vector>
#include<iostream>
using namespace std;namespace wgm {template <class T>struct less{bool operator() (const T& x, const T& y) const{return x < y;}};template <class T>struct greater{bool operator() (const T& x, const T& y) const{return x > y;}};template<class T , class Container = vector<T>, class Compare = less<T>>class priority_queue {public:
#define FATHER(i) (((i) - 1) / 2)
#define LEFT(i) (((i) * 2) + 1)
#define RIGHT(i) (((i) * 2) + 2)void AdjustUp(int i){Compare cmp;while (FATHER(i) >= 0 && Compare()(_con[FATHER(i)], _con[i])) {swap(_con[i], _con[FATHER(i)]);i = FATHER(i);}}void AdjustDown(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;}}void push(const T& val){_con.push_back(val);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T& top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}

四、結(jié)束語

這個部分相對于之前學的容器要簡單，只不過這個雙端隊列的實現(xiàn)源碼還是挺有意思的，可以嘗時著實現(xiàn)實現(xiàn)。