我們上次對std中的list進行實現，今天我們要實現stack、queue、priority_queue以及仿函數。

stack堆

堆的原則就是先進后出，后進先出。如圖：

從上圖我們可以看出來stack準確說就是一個vector，所以我們就可以利用vector來建。

堆的框架

既然是實現STL庫，一定是相似與庫中，我們先不看他用的是誰，我們剛剛也分析了用vector來實現，所以我們可以用vector來封裝。

這里的Con表示Container(容器)，我們只需要傳一個容器類型就可以，這里用vector是因為stack的特性，也可以用deque(他是鏈表與順序表的結合，這里不會多說)。

    template<class T, class Con = vector<T>>class stack{public:private:Con _c;};

構造函數

沒錯，你沒看錯，這里我們的構造函數什么都沒有寫，其實你不寫構造函數也可以，我們也說了構造函數對內置類型不做處理，但是對內置類型會去調用它的默認構造，這里我們用了container容器，我們傳什么容器類型就是什么容器，我們就可以間接區調用它的構造函數。

stack()
{}

push插入

push其實很簡單，vector中插入數據是不是用的push_back();那么我們可以調用那個成員函數，來達到插入效果。

 void push(const T& x){_c.push_back(x);}

pop刪除

pop也是一樣的。復用接口。因為我們是后進的先出，所以我們就尾刪。

       void pop(){_c.pop_back();}

size()大小

 size_t size()const{return _c.size();}

empty()判斷空

bool empty()const
{return  _c.empty();
}

top()取棧頂的元素

那么什么是棧頂呢？如果數據1的位置是0，那么數據3的位置一定是n-1，所以我們有了size就可以，用size()-1;而且vector支持下標。

  T& top(){return _c[size() - 1];}

queue隊列

隊列的特性是先進先出，后進后出。

隊列框架

其實隊列和棧的框架是一樣的。

template<class T, class Con = deque<T>>class queue{public:private:Con _c;};

問題： 這里我們為什么用deque?

因為頭刪問題，我們也知道頭刪vector是效率很低的，你會說為什么不用list，list不支持下標訪問，但是這里用deque就能很好的避免，因為庫中deque既有頭刪，也可以下標訪問。

deque的結構其實就是鏈表和vector的結合。但是deque的缺點也很致命。

• deque的優點
  ①.頭插尾插很快，不需要挪數據，只需要開空間插入
  ②支持連續訪問
• deque的缺點
  ①.中間的插入刪除效率麻煩且一般。
  ②.方括號的效率并不極致。

插入

void push(const T& x)
{_c.push_back(x);
}

刪除

void pop()
{_c.pop_front();
}

取頭數據

 T& front(){return _c.front();}const T& front()const{return _c.front();}

取尾數據

        T& back(){return _c.back();}const T& back()const{return _c.back();}

判斷空和大小

  size_t size()const{return   _c.size();}bool empty()const{return  _c.empty();}

priority_queue堆

優先級隊列和隊列沒有任何關系！優先級隊列是堆，并且他默認是大堆！我們看庫中會發現，他和queue共用一個頭文件。

我們在看一下庫中的實現。有模板參數有 T、Container、那么Compare是啥啊？我們先不管，看庫的時候，遇到不懂得，我們可以先往下看看，如果不影響我們就先不看他，所以我們先排除Compare。先把架子搭出來。

priority_queue的架構

我們還是復用容器類型，堆是完全二叉樹，并且之前我們用vector就可以，通過上下調整位置，達到堆。

template<class T ,class Container=vector<T>, class Compare = less<T> >
class priority_queue
{
public:private:Container _con;
};

empty()判斷空

我們從上圖可以看出來priority_queue的成員函數并不多。

bool empty() const
{return _con.empty();
}	

size()大小

size_t size() const
{return _con.size();
}

top()取堆頂元素

堆頂元素是誰？是不是root根啊，我們用的也是vector,所以堆頂很好取。

T& top() 
{return _con[0];
}

sawp()交換

	void swap(T& p1,T&p2){std::swap(p1,p2);}

push()插入

我們之前學習堆的時候插入是怎么插入的？插到尾部，然后不斷向上調整。如圖，默認是大堆，我們在尾巴插入一個20，向上調整。通過父子對比，孩子比父親大，我們就向上調整。

		void push(const T& x){//尾插然后向上調整_con.push_back(x);AdjustUp(size()-1);}void AdjustUp(int child){//Compare c;int parent = (child - 1) / 2;//找父親while (child > 0){//不斷調整，直到不滿足要求了，結束//if (_con[child] > _con[parent])//if (c(_con[parent], _con[child]))if (_con[parent]<_con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}

pop()刪除

庫中說從頂部移除元素，所以我們需要刪除堆頂。刪除堆頂元素，我們可以首尾交換，然后尾刪，向下調整。

如圖：

void pop()
{//頭尾交換，刪除，然后向下調整swap(_con[0], _con[size() - 1]);_con.pop_back();AdjustDown(0);
}
void AdjustDown(int parent)
{//Compare c;int child = parent * 2 + 1;while (child < size()){if (child < size() - 1 && _con[child] < _con[child + 1])//if (child < size() - 1 && c(_con[child], _con[child + 1])){//這里需要判斷一下，因為我們找的都是左子樹，判斷一下右子樹是否存在//如果存在，在判斷一下那個大，哪個大就和哪個換。(默認大堆)child++;}if (_con[parent] < _con[child])//if (c(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

仿函數

上述我們只能實現默認的大堆，現在如果我希望你實現一個小堆，你怎么辦？ok，你會說我修改一下大于小于號，那么如果在實戰的項目中，讓你實現，你會和客戶說等我一下，我修改一下大于小于號？那不可能，那怎么做呢？仿函數！

其實我們也見過仿函數，在排序中，我們可以利用仿函數排升序降序。

如果你在C語言階段用過排序qsort();里面是不是會讓你們傳一個函數指針類型？其實仿函數就是解決了回調函數問題(函數指針)。

仿函數架構

其實在我們上面寫priority_queue的時候，你會發現默認給的less卻是大堆，這個我也不知道為什么，記住就好了。其實仿函數，你可以理解為，只要重載了operator() 就算是仿函數。
你看輸出的時候，是不是特別像一個函數？其實并不是的，其實只是重載了小括號。

	template<class T>class less{//控制大堆public:bool operator()( const T& x,const T&y){return x < y;}};template<class T>class greater{//控制小堆public:bool operator()(const T& x, const T& y){return x > y;}};template<class T ,class Container=vector<T>, class Compare = less<T> >class priority_queue{public:void push(const T& x){//尾插然后向上調整_con.push_back(x);AdjustUp(size()-1);}void pop(){//頭尾交換，刪除，然后向下調整swap(_con[0], _con[size() - 1]);_con.pop_back();AdjustDown(0);}private:void AdjustDown(int parent){Compare c;int child = parent * 2 + 1;while (child < size()){//if (child < size() - 1 && _con[child] < _con[child + 1])if (child < size() - 1 && c(_con[child], _con[child + 1])){child++;}//if (_con[parent] < _con[child])if (c(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}void AdjustUp(int child){Compare c;//創建比較的對象int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (_con[parent]<_con[child])if (c(_con[parent], _con[child]))//傳哪個仿函數調哪個{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}Container _con;};