C++入門小館: STL 之queue和stack

嘿，各位技術潮人！好久不見甚是想念。生活就像一場奇妙冒險，而編程就是那把超酷的萬能鑰匙。此刻，陽光灑在鍵盤上，靈感在指尖跳躍，讓我們拋開一切束縛，給平淡日子加點料，注入滿滿的passion。準備好和我一起沖進代碼的奇幻宇宙了嗎？Let's go！

我的博客：yuanManGan

我的專欄：C++入門小館?C言雅韻集?數據結構漫游記? 閑言碎語小記坊?題山采玉?領略算法真諦

怎么使用隊列和棧：

隊列和棧的模擬實現：

deque：

priority_queue

先來了解

怎么使用隊列和棧：

這些接口看起來已經很熟悉了。

直接來看看使用吧：

使用就很簡單了。

隊列和棧的模擬實現：

我們先來了解一下適配器：

適配器大家比較熟悉的就是電源適配器，我們的充電器。

queue和stack都是一種容器適配器。

我們用其他類來封裝這兩個容器。

我們回憶一下stack只需要在一方插入和刪除，我們vector和list都能滿足要求，所以我們來簡單來實現一下。

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

deque：

這里的缺省值給的是deque雙端隊列，等會再來講解。

再來回憶一下隊列，它是先進先出，一端入數據一端出數據，我們就拿頭部出數據，尾部入數據，簡單實現如下：

#include<deque>
#include<iostream>
using namespace std;
namespace refrain
{template<class T, class Container = std:: deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}T& front(){return _con.front();}const T& front() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}void pop(){_con.pop_front();}size_t size() const{return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}

這里我們有個問題我們的vector不是沒有pop_front嗎，那我們是不是不能用vector來實現隊列呢？的確庫里面他就是用的pop_front，庫里面不想你使用vector來實現，因為vector頭部操作麻煩時間復雜度高，那我們能不能強制實現呢？我們可以使用erase來實現頭部刪除就可以用vector來實現queue了。

這是庫里實現的：

這樣就適用了，但我們一般用deque這個更優秀

接下來就簡單講講deque了：

先來對比一下list和vector的各自的優缺點：

而我們vector的優點就是list的缺點，vector的缺點就是list的優點。

優點:

缺點

vector

1.支持下標隨機訪問，

2.CPU高速緩存命中率高

1.頭部或中間位置的插入刪除操作效率低下，因為要挪動數據

2.擴容有一定的成本，存在一定的浪費。比如現在容量為100滿了擴成200只插入了120空間浪費了80空間。

list

1.容易位置的插入和刪除的時間復雜度都是O(1),不需要挪動數據。

2.不存在擴容，按需申請釋放，不浪費空間。

1.不支持下標隨機訪問

2.CPU高速緩存命中率低

這里補充一個知識CPU高速緩存命中率的知識：

cpu想要訪問內存的一個數據，要看這個數據是否在緩存，在就緩存命中，不在就不命中；不命中就先加載到緩存，然后再訪問緩存。

它加載到緩存不是只加載一個數據而是加載一個范圍的數據，因為vector創建的是連續的空間，cpu的高高速緩存就高，而list每次都得先加載到緩存然后再訪問緩存。

接下來就來簡單了解一下deque的底層實現了。?

我們用四個指針封裝deque的迭代器。

我們創建多個buff數組，用first指向buff的第一個位置，last指向最后一個位置。用cur指向當前位置。

再創建一個中控數組map，map里面存儲著指向buff數組的指針，也就是二級指針。

這樣設計有什么好處呢？

當我們迭代器++時

直接++cur,如果cur是最后一個的時候就移動node代碼如下：

庫里面是這樣實現的：?

邏輯是一樣的，但它的細節處理的更好。

減減也是相同的邏輯，就不實現了。

解引用操作就很簡單了

直接解引用cur。

push_back:

如果push_back時buff沒有慢，就直接cur++,last++。?

當buff已經滿了，我們就得創建一個buff了，讓node++,然后cur指向buff的第二個元素，last指向末尾，first指向第一個元素，如圖。

再來看看push_front

當buff滿了，就創buff，此時我們cur不是指向第一個元素，指向的是最后一個元素，要保持連續性，node--，last，first指向尾和頭。

再頭插一個:

j就直接cur--就行了。

總結一下:

優點:

?????????1.頭尾部插入刪除效率很高

? ? ? ? ?2.下標隨機訪問效率還可以，但不如vector。

缺點：

? ? ? ? ?1.中間位置插入和刪除效率一般。

? ? ? ? ?2.對比vector和list沒有那么極致。(不專一)

?適合做stack和queue的適配器

priority_queue

優先級隊列也不是隊列是堆，堆之前我們用c語言就實現過，我們看看stl庫里面怎樣實現的。

我們之前實現的堆，大家回憶一下，是不是用到了大量的下標訪問?，我們就可以使用vector來當容器適配器。

當我們插入一個數50的時候，這時候還是一個堆，就不進行操作

而當我們插入35的時候：我們要進行向上調整算法。?

那我們回憶一下怎么找父親節點呢？

parent = （child - 1）/ 2。

我們就寫一個向下調整算法

如果c語言實現的時候認真學習的應該沒有什么問題。

同樣的刪除堆頂時我們交換堆頂和最后一個位置，然后尾刪，進行向下調整算法

我們找左右孩子怎么找到呢？

左孩子: child = parent * 2 + 1

右孩子：child = parent* 2 + 2

一樣實現的輕而易舉：

?我們就來實現一下堆吧：

template<class T, class Container = std::vector<T>>
class priority_queue
{
public:void push(const T& x){_con.push_back(x);adjustup(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);}const T& top() const{return _con[0];}bool empty(){return _con.empty();}//大堆void adjustup(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child]){child++;}if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}
private:Container _con;
};

這里的top就不能實現兩個版本了，因為棧頂的元素不支持修改。?

這里還缺少一個參數是什么呢，這里可以用仿函數來實現：

仿函數

我們可以通過重載( )括號運算符來實現仿函數：

我們可以利用這個特性來讓我們選擇能創的是大堆還是小堆，但我們這個有點坑，傳less創建的是小堆，我們只好按它的來哦。

#pragma once
#include<vector>
#include<iostream>namespace refrain
{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 = std::vector<T>, class Compare = less<T>>class priority_queue{public:Compare com;void push(const T& x){_con.push_back(x);adjustup(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);}const T& top() const{return _con[0];}bool empty(){return _con.empty();}//大堆void adjustup(int child){int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjustdown(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}private:Container _con;};}

?完了over！