一、stack、queue的接口

（一）stack 接口說明

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

（二）queue 接口說明

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

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

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

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

stack、queue底層默認(rèn)容器–deque

1、deque概念及原理

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

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

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

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

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

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

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

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

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

3、重載的復(fù)用

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

#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;//構(gòu)造函數(shù)//有參構(gòu)造__deque_iterator(T* x, map_pointer y): cur(x), first(*y), last(*y + buffer_size()), node(y) {}//默認(rèn)構(gòu)造__deque_iterator() : cur(0), first(0), last(0), node(0) {}//拷貝構(gòu)造__deque_iterator(const iterator& x): cur(x.cur), first(x.first), last(x.last), node(x.node) {}//更新結(jié)點(diǎn)信息void set_node(map_pointer new_node) {node = new_node;first = *new_node;last = first + difference_type(buffer_size());}//運(yùn)算符重載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的模擬實(shí)現(xiàn)

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

#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的模擬實(shí)現(xiàn)

和stack類似，在它的參數(shù)列表中也有一個(gè)參數(shù)類型Container(容器），它也存在默認(rèn)參數(shù)deque。這里的參數(shù)不能傳入vector,因?yàn)?code>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)先隊(duì)列

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

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

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

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

（三）優(yōu)先隊(duì)列的模擬實(shí)現(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é)束語

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