🔥 本文專欄：c++
🌸作者主頁：努力努力再努力wz

💪 今日博客勵志語錄： 石頭能被水滴穿，不是因為水有多強，而是因為它從未停過。

★★★ 本文前置知識：

模版

---

棧

那么棧這個數據結構相比大家已經十分熟悉，那么棧是一個后進先出的數據結構，那么在c語言期間，我們實現在棧這個數據結構采取的方式就是用數組的方式來實現，因為數組中有效數據的末尾就可以作為棧頂，那么數組的尾插以及尾刪不需要挪動元素，時間復雜度是O(1)，所以數組就天然適配棧這個數據結構的底層實現，那么我們再定義一個結構體其中封裝三個成員變量，分別是一個指針指向該動態數組的首元素的地址以及一個棧頂指針追蹤棧頂位置和記錄當前數組最大容量的變量以便擴容，然后再定義棧的初始化以及壓棧和入棧的函數，所以知道在c語言期間棧的實現之后，那么我們c++可以同樣模擬c語言的實現方式，底層維護一個數組，然后定義三個成員變量，也就是三個迭代器本質就是三個原生指針，指向該數組的首元素以及有效數據末尾和數組的末尾，來維護一個動態數組，然后再定義相關的構造函數以及入棧push以及出棧pop成員函數，但是我們其實在仔細思考觀察一下我們剛才的實現方式，我們發現按照剛才的實現方式，定義三個迭代器維護一個動態數組，然后再定義相關比如empty和size和push函數，那么這些成員變量和成員函數其實和我們之前學過的vector的功能是高度重合，不能說完全相等只能說一模一樣

那么自從我們學習完c++的模版之后，那么此時我們用c++編程的其中一個核心思想就是能不用自己造輪子就盡量不造，那么編譯器有了模版可以根據類型不管是自定義類型還是內置類型，只有你提供了相關的定義，那么編譯器都能來實例化出相應的類或者函數，所以這里我們我們就可以采取一個容器適配器模式來實現我們的棧

---

那么所謂的容器適配器的思想就是我們除了定義一個代表容器中存儲數據類型的模版參數，還定義另一個模版參數，那么該模版參數就是容器的類型，因為到時候我們可以在棧的模版類中定義一個自定義類型的成員變量，那么該自定義類型就對應某個容器類型因為容器本質上就是一個自定義類型，例如vector< T >或者list< T >

所以我們先可以這樣實現：

template<typename T,typename container>class stack{private:container _con;};

那么接下來便是棧的成員函數：

成員函數

那么第一個想到的成員函數一定是構造函數，那么棧這里是否需要我們顯示定義構造函數了，那么構造函數就是初始化成員變量，那么我們知道這里采取了容器適配器模式，所以我們采取的容器本身就有對應的默認構造函數，那么這里就無需我們自己手動編寫構造函數

拷貝構造函數

那么棧有拷貝構造函數，那么拷貝構造函數就是接受一個已經初始化的棧對象來初始化還未初始化的棧對象，

那么這里的實現原理就是就是這里我們直接將初始化的棧對象賦值給該還未初始化的棧對象，那么由于對應的容器本身一定有對應的賦值運算符重載函數，那么其中一定實現了深拷貝，所以我們直接賦值即可，不用擔心淺拷貝問題

stack(const stack<T,container>& l1)
{_con = l1._con;
}

top函數

那么這里的top函數就是返回棧頂元素，那么我們棧頂元素就是位于容器的首部，那么這個時候就體現出stl的規范化的好處了，那么stl對其中的所有容器的成員函數的命名以及種類進行了規定與統一，那么這些容器都能夠支持size函數以及empty函數等，這也為我們為什么能夠采取容器適配器做了一個鋪墊，也就是我們直接可以進行函數的復用，那么這里我們直接復用容器的front函數，得到首元素的值，然后返回

const T& top()
{return _con.front();
}

push函數

那么push函數就是在棧尾部插入元素，那么這里我們就只需要調用容器內自帶的push_back函數了，那么list以及vector以及包括我們之后講的deque都有push_back函數的實現，那么這里deque先埋下一個伏筆

void push(const T& val)
{_con.push_back(val);
}

pop函數

那么pop函數就是彈出棧頂元素，那么我們就復用容器的pop_back函數即可

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

empty函數

empty函數同樣是復用容器內的empty函數

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

size函數

那么size函數復用容器提供的size函數

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

swap函數

那么swap函數就是我們調用庫里面的為我們提供的swap函數，交換對象的成員變量即可

void swap( stack<T, container>& l1)
{std::swap(_con,l1._con);
}

---

那么這就是棧的全部實現包含成員函數以及成員變量，那么我們其實發現，棧的實現跟前面我們實現的list和vector相比，那簡直要簡單不少，簡直就是獎勵關，那么之所以容易實現該容器，還是感謝c++的模版能夠讓我們不用再自己造輪子

源碼

#pragma once
#include<algorithm>
namespace wz
{template<typename T,typename container>class stack{private:container _con;public:stack():_con(){}stack(const stack<T,container>& l1){_con = l1._con;}const T& top(){return _con.front();}void push(const T& val){_con.push_back(val);}size_t size(){return _con.size();}void pop(){_con.pop_back();}bool empty() {return _con.empty();}void swap( stack<T, container>& l1){std::swap(_con,l1._con);}};
}

#include"stack.h"
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
int main()
{wz::stack<int, std::vector<int>> l1;l1.push(1);l1.push(2);l1.push(100);l1.push(400);l1.pop();cout << l1.top() << endl;l1.pop();cout << "size: " << l1.size() << endl;l1.pop();wz::stack<int, std::vector<int>> l2;l2.swap(l1);l2.pop();if (l2.empty()){cout << "stack is empty" << endl;}return 0;
}

運行截圖：

---

那么在了解完以及模擬實現了棧之后，那么其實大家普遍會采取vector作為棧的默認容器，但是c++的stl的設計者卻選擇了另一個容器，那么其便是deque，那么選擇使用deque一定有它的原因，那么在講解c++的stl的設計者為什么選擇deque之前，那么我們先來認識一下什么是deque

deque

那么接下來我們就來認識一下我們的deque，那么看看我們的deque相比與我們的list和vector有什么特別之處

那么deque也被稱之為雙端隊列，那么之所以被稱之為雙端隊列，那么我們也能從deque為我們提供的接口能夠看出它為什么取這個名字，那么deque既為我們提供了push_front和pop_front成員函數，同時也有尾插和尾刪的成員函數，那么相比于vector，那么vector就沒有提供頭插與頭刪的接口，雖然vector能夠做到頭插與頭刪，但是我們知道對于數組來說，頭插與頭刪要移動大量的元素，那么效率不高，所以這也就是為什么vector沒有提供頭插與頭刪的原因，那么如果有頭插和頭刪的需求，那么明顯list是更好的選擇，因為list的頭插與頭刪的時間復雜度都是o(1)級別，那么就是因為list只需要修改節點之間的鏈接關系，同理對于尾插以及尾刪也是一樣，所以list提供了頭插和頭刪以及尾插和尾刪的成員函數

那么這里deque和list同樣也提供了頭插頭刪和尾插尾刪，那么只能說明，對于deque來說，那么其頭插和頭刪以及尾插和尾刪的效率一樣優秀，所以才可以提供，那么就意味著deque和list的結構是相似但是肯定是不完全相同的

而事實上deque的底層結構確實類似于鏈表，那么deque存儲的數據是分布在一個一個物理內存不連續的節點中的，但是與鏈表不同的是，那么鏈表的每一個節點只能存儲一個元素，并且節點內部還存儲了前驅以及后繼節點的指針，但是對于deque來說，那么deque中的每一個節點是一個數據塊或者更為準確的來說，是一個動態數組，那么該數組存儲的不只有一個元素而是有多個元素，但是它卻沒有額外存儲其前驅數據塊以及后繼數據塊的指針，而這些一個個動態數組在物理內存中又并不連續，那么如何來定位訪問到這一個個的數據塊呢？

所以這里deque還準備了一個中控數組，那么所謂的中控數組，本質上就是一個指針數組，那么說到這里，想必各位讀者也一定大概知道或者猜到該數組的作用了，那么該指針數組中每一個元素是一個指針，其中指向的就是對應數據塊的首元素，那么定位這些數據塊就是通過中控數組來訪問到這些數據塊了

那么看到這里，想必讀者心里大概有一個疑問：

第一個疑問就是為什么它要這么設計，也就是每一個節點是一個數據塊也就是一個數組，為什么不只能是一個節點存儲一個元素？

第二個疑問是deque如何實現這個結構？

那么要解釋第一個問題，那么僅僅站在語言的角度是無法回答的，那么這個問題就得涉及到一點計算機組成原理的知識，那么我們知道CPU在運行我們的代碼，我們代碼中涉及到的各種數據，比如兩個int類型的數相加，那么這兩個int類型的數據都是存儲在內存當中的，那么CPU在進行這些算術運算的時候，首先要做的就是訪問內存，到內存中取出數據，那么CPU會通過地址線告訴內存我要的目標數據的地址，然后內存根據該地址定位到數據然后取走交給CPU

說到這里，我這里想問讀者一個問題，此時你認為內存取走該數據時，比如在該場景下，CPU給了內存我要的int類型的變量a在內存中的地址，那么此時你覺得內存的行為是什么，是只僅僅取走該int類型的a變量的數據即可還是說不僅僅只是單單取該目標數據數據

那么有些讀者如果認為只是單單取走該i目標數據也就是該int類型的a變量，那么說明對硬件還是不夠了解，那么這里會涉及到計組的知識，那么我們就可以簡單理解為訪問內存其實是有成本或者說代價的，那么假設存在這么一個場景，就是我們遍歷一個數組，寫了一個for循環，循環n次，讀取數組中的每一個元素，那么按照剛才的方式，那么意味著CPU要訪問n次內存，那么訪問內存是具有代價的，那么這樣就到導致效率低下，所以事實上內存的行為是不僅僅取走該目標數據，同時還會取走目標數據周圍相鄰的數據，總共64字節然后后上傳到CPU的緩存中，那么這樣做的目的根據剛才的場景我們就可以得知，那么假設我們CPU訪問完了一個數據，那么有可能下一個數據就在該數據的周圍，比如剛才場景中，遍歷訪問數組中的元素，而CPU的行為，它不會先訪問內存，而是優先訪問緩存，因為訪問緩存的速度是比內存要快很多的，如果緩存沒有再去內存中訪問，那么在剛才的場景下，如果遍歷一個數組，那么從內存中取出該數組的第一個元素后，那么內存還會取出該數據相鄰的元素，那么意味著可能直接把整個數組都從內存中取出放到緩存，那么接著CPU訪問了一次內存，那么下一次訪問的時候，先訪問緩存，發現緩存有，就直接讀取緩存中的數據，那么意味著遍歷該數組，實際上可能只需要一次內存的訪問。

所以這就引出了數組的好處，那么就是CPU的緩存命中率高，想必有的讀者一定聽過該名詞就是緩存命中率，所以假設我們訪問完deque的某個數據塊中的某個元素，那么該元素所在的整個數據塊會被加載進緩存中，那么如果下一次訪問的元素還在數據塊，那么CPU就可以直接去緩存快速定位，就不需要訪問內存，而如果沒有就大不了再訪問一次內存，如果在，那么對于CPU就是賺了，這就就是為什么deque選擇這么設計的原因，目的就是可以提高CPU的緩存命中率

---

那么關于第二個疑問，那么deque是如何實現的，那么deque內部首先會維護4個成員變量，分別是兩個迭代器以及一個指向該指針數組的首元素地址的二級指針和指針數組的當前的容量，而這兩個迭代器分別是start和end，那么這兩個迭代器會指向有效數據的起始位置和結束位置，那么deque迭代器的構造相比于之前學的vector和list來說，那么就較為復雜

template <class T>
class deque {
private:Iterator _start;       // 第一個有效元素所在數據塊的迭代器Iterator _finish;      // 最后一個有效元素的后繼位置迭代器T** _map;              // 中控數組（二級指針）size_t _map_size;      // 中控數組容量
};

那么對于deque來說，那么它的迭代器內部封裝了4個原生指針分別是first和end和cur和next，那么我們知道deque存儲數據的節點是一個動態數組，那么這里每一個數組的大小都是固定的，那么首先這里deque的first指針就是指向該數組的起始位置，而last則是指向該數組的最后一個位置的下一個位置，還有一個cur指針則是用來定位以及變量該數據塊的元素，而第四個node指針，則是保存當前數據塊的在指針數組中的地址

template <class T>
struct _deque_iterator {T* _first;    // 當前數據塊起始地址T* _last;     // 當前數據塊末尾的下一個地址（邊界）T* _cur;      // 當前指向的元素位置T** _node;    // 指向中控數組中當前塊的指針（用于跨塊跳轉）// 關鍵操作示例：operator++（后置）_deque_iterator& operator++() {++_cur;if (_cur == _last) {  // 到達當前塊末尾// 切換到下一數據塊++_node;          // _node移動到中控數組下一項_first = *_node;  // 更新新塊的起始地址_last = _first + _block_size; // 更新新塊邊界_cur = _first;    // 指向新塊首元素}return *this;}
};

那么在介紹完deque的迭代器的構造后，那么我們再來認識一下deque的各個相關操作的成員函數，那么首先就是構造函數，那么deque的構造函數，默認的構造函數就是將兩個迭代器給置為nullptr以及一個指向指針數組的指針置空也就是這是一個空的雙端隊列，那么帶參的構造函數則是支持初始化設置n個元素并且帶有初始值
默認：

deque() : _start(nullptr, nullptr, nullptr, nullptr), _finish(nullptr, nullptr, nullptr, nullptr),_map(nullptr),_map_size(0) {}

那么帶參數的構造函數的實現原理，就是先初始化指針數組，開辟一定的大小的指針數組，那么接下來的一個細節就很關鍵，那么就是deque的插入的第一個元素的位置，很多讀者會很自然的覺得插入的位置就在指針數組下標為0所指向的第一個數據塊的首元素，但是我們再看來審視一下這種方式，如果你的下一步操作是在前面再插入一個元素也就是頭插，那么必定就會涉及到擴容，因為前面沒有數據塊了，所以對于deque，它第一個插入的元素的位置是設置在指針數組中間位置的數據塊中的中間位置，那么仔細品味一下，那么之所以設置在這，那么就是為了便于頭插和尾插，減少擴容的次數

那么假設指針數組的長度為k，那么就在k/2位置處開辟一個固定大小假設為n長度的數據塊，在該數據塊的n/2位置處插入，然后初始化start和end指針，那么上文說過迭代器內部有4個指針，那么此時start迭代器中的這封裝的4個指針，其中的first會指向該k/2位置處指向的數據塊的起始位置，然后last會指向該k/2指向的數據塊的結束位置，然后cur則是指向當前該數據塊的n/2位置處，next則是保存當前數據塊的在指針數組中的地址，同理last初始化也是一樣，只不過其cur指針指向的是(n+1)/2位置處，因為start和end維護的右下數據的區間是左閉右開的[start,end],然后依次向后尾插，也就是調用push_back函數

deque(size_type n, const T& value = T()) {// 1. 初始化中控數組（預留對稱空間）_map_size = std::max(8, n * 2);    // 最小保證8個指針位_map = _alloc_map(_map_size);// 2. 計算中心位置（關鍵！）size_t map_mid = _map_size / 2;size_t block_mid = _block_size / 2;// 3. 創建首個數據塊并掛載到中心位置T* new_block = _alloc_block();_map[map_mid] = new_block;// 4. 設置迭代器（核心四指針初始化）_start._node = _map + map_mid;    // 指向中控數組成員的指針_start._first = new_block;_start._last = new_block + _block_size;_start._cur = new_block + block_mid;  // 首元素居中_finish = _start;// 5. 批量插入元素while (n--) {push_back(value);  // 尾插（或 push_front）}
}

那么對于deque的push_back函數來說，那么它會從last位置開始插入，那么首先會檢查該雙端隊列是否為空數組，也就是s指向指針數組的二級指針是否為nullptr，如果為空，那么會做與上文同樣的初始化工作其中包括開辟指針數組等，然后接著從last位置插入，然后last指針往后移動，那么last指針往后移動就是調用迭代器的自增運算符重載函數，那么迭代器的自增運算符重載函數所做的行為就是將cur指針往后移動，并在cur位置處設置元素值，如果cur到達了last位置處，那么此時會利用迭代器的next指針，那么獲取其下一個后繼的數據塊的地址，如果下一個數據塊還沒開辟，那么就開辟對應大小的動態數組然后設置好指針數組中對應的指針的值，然后重新設置這4個指針的值，讓first和last指向下一個數據塊的起始和結束位置，然后cur指針指向該數據塊起始位置，如果說此時數據塊已經到達結尾，也就是說沒有下一個數據塊了，那么就得涉及到指針數組的擴容

那么指針數組的擴容注意不是簡單的重新開辟一個更大的數組然后拷貝數據，因為由于deque其支持頭插和尾插，那么其新的指針數組的形態類似于在原數組的兩端分別再加了一節，所以并不是簡單的將原有的數據拷貝到新數組那么簡單

void push_back(const T& value) {if (_map == nullptr) {// 初始化中控數組（默認8個指針位）_map_size = 8;_map = _allocate_map(_map_size);// 創建首個數據塊T* new_block = _allocate_block();size_t mid_idx = _map_size / 2;_map[mid_idx] = new_block;  // 掛載到中央位置// 初始化首尾迭代器_start._node = _map + mid_idx;_start._first = new_block;_start._last = new_block + _block_size;_start._cur = new_block + (_block_size / 2); // 中心起始位_finish = _start;}// 繼續執行插入...
}

void push_back(const T& value) {if (_finish._cur != _finish._last - 1) {// 當前塊有空位 → 直接插入*_finish._cur = value;++_finish._cur;} else {// 當前塊已滿 → 準備新塊if (_finish._node == _map + _map_size - 1) {// 中控數組尾部空間不足 → 擴容_reserve_map_back();}// 創建新數據塊T* new_block = _allocate_block();*(_finish._node + 1) = new_block;  // 掛載到中控數組// 更新_finish迭代器_finish._node++;          // 指向中控數組新項_finish._first = new_block;_finish._last = new_block + _block_size;_finish._cur = new_block; // 指向新塊起始位置// 插入元素*_finish._cur = value;++_finish._cur;}
}

而對于push_front頭插來說，那么與尾插的原理類似，只不過是在start的前一個位置插入，就需要先移動start迭代器，然在start迭代器指向的位置處插入

那么我們發現deque也支持隨機訪問也就是重載了[]運算符，那么我們根據上文的構造函數以及頭插和尾插的原理，我們發現deque的數據主要是集中分布在指針數組中部位置處，意味著deque中的元素不一定填滿整個指針數組，也不一定填滿已經存在分配好的數據塊，但是幸好的就是有start和end來維護有效數據所在的區間，那么給你一個下標，那么首先你要做的就是判斷下標位置的合法性，而對于雙端隊列來說，那么它只有首個數據塊（start迭代器指向數據所在的數據塊）以及最后一個數據塊（end迭代器指向的數據所在的數據塊）可能存在填不滿數據，中間的數據塊的數據一定是滿的，至于為什么，這里讀者可以腦海中想象回憶一下頭插和尾插的過程，那么每一個數據塊的大小是固定的，那么這里我們就可以計算出有效元素的總數據量，那么判斷該下標是否合法，如果合法，接下來判斷是否在首數據塊中，不在那么就要再進行計算，假設下標為x，首數據塊元素個數為k，單個數據塊長度為n，

那么首先進行除運算：（x-k)/n=m 得到其在第m+2個數據塊處

然后取取模運算：(x-k)%n=q,得到其在第m+2個數據塊的第q位置處

這就是deque的隨機訪問原理

reference operator[](size_type index) {// 1. 計算首塊剩余有效元素size_type head_remaining = _start._last - _start._cur;if (index < head_remaining) {// 情況1：目標在首數據塊內return *(_start._cur + index);} else {// 2. 計算跨塊偏移size_type remaining_offset = index - head_remaining;// 3. 計算數據塊索引和塊內偏移size_type block_idx = remaining_offset / _block_size + 1;  // +1跳過首塊size_type elem_idx = remaining_offset % _block_size;// 4. 定位目標數據塊T* target_block = *(_start._node + block_idx);return target_block[elem_idx];}
}

---

那么介紹完deque的構造以及相關的實現之后，那么我們來評價deque這個結構，那么deque首先它支持隨機訪問，那么這一點vector也能做到，但是根據上文說的deque的原理我們不難發現，deque的隨機訪問要經過一系列運算，那么明顯不如vetcor直接通過原生指針的算術運算效率高，其次它支持頭尾插入刪除，那么其中根據原理我們也知道對于頭插與尾插的各種遍歷會涉及到數據塊的切換和中控指針數組的擴容，整個機制還是比較復雜的，那么相比于list的頭插和尾插，那么效率也是不如list的，所以deque結合了兩個容器的優點，但是它卻無法將這兩個優點發揮到極致，而vector和list則像一個專精選手，所以我們有比如隨機訪問的需求，我們不會考慮deque而是vector，同理如果有大量的頭尾插入刪除的需求，那么我們也不會考慮deque而是list，這也是為什么deque比較冷門，并且這里你也看我只是講解其原理，沒有自己也沒有建議讀者去模擬實現。所以客觀來說，這里選擇deque用作棧的默認容器，其實我覺得不如用vector好，因為這里涉及到尾插與尾刪，那么vector的效率其實更不錯一點

queue

那么queue就是我們熟知的隊列，那么這個數據結構我們已經非常熟悉了，那么它是一個先進先出的數據結構，那么在c語言期間實現我們是采取鏈表來實現我們的隊列的，因為隊列要從頭部插入和尾刪除，所以鏈表能夠更好的適應這個場景，所以我們會定義一個節點然后相關的初始化以及入隊和出隊的函數，那么有了上文的stack的實現的經驗，那么這里我們知道對于c++來實現queue來說，那么我們不用再需要我們自己去造輪子來實現鏈表了，直接利用list，所以這里的queue也采取了容器適配器模式

那么這里queue的第一個模版參數就是容器中存儲的數據類型，第二個參數就是容器的類型，那么和stack同樣，那么這里queue的成員變量就是一個自定義類型的成員變量，那么這個自定義類型就是對應我們的容器

template<typename T,typename container>class queue{private:container _con;}；

那么設計者給queue的第二個模版參數的默認參數是同樣是雙端隊列

成員函數

那么這里由于成員變量是自定義類型，所以queue的構造函數就可以調用其自定義類型的默認構造函數即可不需要我們自己顯示實現一個默認構造函數

push函數

那么push函數則是可以復用適配的容器本身實現的push_back函數

void push(const T& val)
{_con.push_back(val);
}

pop函數

那么pop函數則是復用適配的容器自己本身實現的pop_front函數

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

empty函數

那么empty函數同樣是復用容器本身實現的empty函數

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

size函數

復用容器本身實現的size函數

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

swap函數

調用標準庫提供的swap函數來交換成員變量

void swap(queue<T, container>& l1)
{std::swap(_con, l1.queue);
}

---

那么剩余的成員函數基本上也是簡單的一個復用，那么這里就不過的介紹了，這里stack和queue的核心思想就是一個容器適配器模式

源碼

queue.h:

#pragma once
#include<algorithm>
namespace wz
{template<typename T,typename container>class queue{private:container _con;public:queue():_con(){}queue(const queue<T,container>& l1){_con = l1._con;}void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}bool empty(){return _con.empty();}void swap(queue<T, container>& l1){std::swap(_con, l1._con);}size_t size(){return _con.size();}};
}

queue.cpp:

#include"queue.h"
#include<iostream>
#include<list>
using std::cout;
using std::endl;
int main()
{wz::queue<int, std::list<int>> l1;l1.push(1);l1.push(33);l1.push(44);l1.push(52);l1.push(11);l1.pop();wz::queue<int, std::list<int>> l2(l1);while (!l2.empty()){cout << l2.front() << " ";l2.pop();}cout << endl;l2.swap(l1);cout << l1.size() << endl;return 0;
}

運行截圖：

結語

那么這就是本文關于stack和deque和queue的全部講解了，那么也建議讀者下來自己去實現stack和queue，來加深自己的理解，那么下一期我會更新優先級隊列，那么如果本文對你有幫組的話，希望三連加關注哦，你的支持就是我創作最大的動力！