09--解密棧與隊列：數據結構核心原理

1. 棧

1.1. 棧的簡介

棧是一種 特殊的線性表，具有數據 先進后出 特點。

注意：

stack本身 不支持迭代器操作
主要原因是因為stack不支持數據的隨機訪問，必須保證數據先進后出的特點。
stack在CPP庫中實現為一種 容器適配器
所謂容器適配器，是為了適應不同的數據存儲而修改底層的數據結構從而達到優化效率的目的。
參考：C++ STL容器適配器（詳解）

1.2. 棧為什么沒有提供迭代器？？？

棧為什么沒有提供迭代器？？？

我們看CPP::stack的文檔，發現stack并沒有提供迭代器，這是因為stack要保證其自身特性是先進后出，后進先出的特性，如果提供了迭代器，就能夠打破這一規則，棧也不再是棧。

1.3. 棧簡化模擬實現

棧簡化模擬實現

C版簡化模擬棧：【數據結構】棧
CPP版簡化模擬棧：

#pragma once
#include<vector>
#include<iostream>using namespace std;
namespace szg
{template<class T, class Container = vector<T>>class stack{private:Container _st;public:void push_back(const T& num){_st.push_back(num);}void pop_back(){_st.pop_back();}bool empty(){return _st.empty();}size_t size(){return _st.size();}const T& top(){return _st.back();}};
}

實際上，stack在庫中給的容器缺省值是deque，是一個 順序表與鏈表的結合體。
deque參考文檔：stl_deque
deque底層邏輯簡介：【CPP】雙端隊列簡介(deque)

1.4. 適配器

適配器

在上面我們模擬實現的棧中，用到了Container，這個適配器。

什么是適配器？所謂適配器就是服務于我們所寫的類能夠支持其快速底層轉換的一種方式。

適配器模式主要應用于，當接口里定義的方法無法滿足客戶的需求，或者說接口里定義的方法的名稱或者方法界面與客戶需求有沖突的情況。

兩類模式：

對象適配器模式 - 在這種適配器模式中，適配器容納一個它我包裹的類的實例。在這種情況下，適配器調用被包裹對象的物理實體。

類適配器模式 - 這種適配器模式下，適配器繼承自已實現的類（一般多重繼承）。

適配器不具備數據速率轉換功能。

說到這里，我來簡單介紹一種新的容器，專門用來做適配器的容器——deque

2. deque雙端隊列

deque是一個融合了list和vector相關特性的“混合容器”，既有list的快速插入刪除特性，也有vector[]隨機訪問功能，算是“文武雙全”的容器。

應用：作為容器適配器使用。

2.1. deque的特性

容器	vector	list	deque
優點	支持下標隨機訪問，[]效率高	任意位置插入刪除效率高	頭插、尾插效率高
缺點	頭部/中間插入刪除效率低，擴容消耗大	不支持[]隨機訪問	中間插入刪除效率一般且[]效率不夠極致

2.2. deque的內部構造

deque的內部控制是依靠迭代器實現的。

cur是指向當前的訪問元素
first是指向當前buff的開始元素
end是指向當前buff的末尾元素的下一個地址
node是指向當前buff在中控數組中存放的位置

2.3. deque的插入刪除遍歷邏輯

deque的插入和刪除：

deque的頭插尾插效率是挺高的。這是因為尾插一個元素后，迭代器會看看中控數組最后一個buff是否還有空間，如果有則尾插到最后一個buff，如果沒有就新開一個buff插入。頭插一個元素，他會現在中控數組的頭部開一個buff，因為默認是從中控數組中間開始新增的，所以可以支持常數時間開空間，之后同尾插同理。

中間插入插入元素處理比較麻煩

如果中間插入元素后面所有元素都往后挪動一位，效率比較低

如果中間插入元素改變buff的大小，那么上面[]訪問規則就不適用，會很麻煩。

deque的元素[]訪問計算規則，且[]訪問效率一般

一般情況下，buff每個都是相同大小并且沒有頭插新元素時候，下標訪問可以采用

先找是第幾個buff，n/buff.size()
在確定是這個buff中的第幾個元素，n%buff.size()

但是如果有頭插元素，首先應該減去第一個buff元素的個數，然后在進行上面步驟。

n-=buff1.size()

void test_op1()
{srand(time(0));const int N = 1000000;deque<int> dq;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand() + i;v.push_back(e);dq.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();sort(dq.begin(), dq.end());int end2 = clock();printf("vector:%d\n", end1 - begin1);printf("deque:%d\n", end2 - begin2);
}
//vector:259
//deque:1263void test_op2()
{srand(time(0));const int N = 1000000;deque<int> dq1;deque<int> dq2;for (int i = 0; i < N; ++i){auto e = rand() + i;dq1.push_back(e);dq2.push_back(e);}int begin1 = clock();sort(dq1.begin(), dq1.end());int end1 = clock();int begin2 = clock();// 拷貝到vectorvector<int> v(dq2.begin(), dq2.end());sort(v.begin(), v.end());dq2.assign(v.begin(), v.end());int end2 = clock();printf("deque sort:%d\n", end1 - begin1);printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}
//deque sort : 1345
//deque copy vector sort, copy back deque : 358

2.4. deque作為stack/queue適配器的優先性？

為什么CPP庫中選擇deque作為stack/queue的適配器呢？

因為stack和queue都只會用到頭插尾插頭刪尾刪，恰好deque頭尾插刪效率都很好。也可以說，deque就是專門為stack/queue適配專門設計的一個容器。

3. 隊列queue

queue是隊列的含義，其特點是保證了數據先進先出，后進后出的特點，底層可以用vector、list或deque進行適配。

3.1. 隊列的簡單模擬實現

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

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
#include<iostream>int main()
{szg::queue<int> q;for (int i = 0; i < 100; i++){q.push(i);}while (!q.empty()){std::cout << q.front() << " ";q.pop();}std::cout << std::endl;//0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99return 0;
}

3.2. 隊列與棧的異同？

隊列與棧的差異重點在于相同序列進入容器，出數據會有所不同。

容器	數據變化
棧	棧的出數據序列會變化，這取決于棧的push,pop順序
隊列	隊列的出數據序列不會變化，是恒定的

4. priority_queue優先級隊列 -> 堆

4.1. 簡單介紹

優先級隊列不是隊列，是一種容器適配器，底層是大堆。

在優先級隊列提供了一些接口允許公開調用：

4.2. 簡單使用

// 優先級隊列，默認底層是大堆。
priority_queue<int> ps;
ps.push(2);
ps.push(3);
ps.push(4);
ps.push(1);while (!ps.empty())
{cout << ps.top() << " ";ps.pop();
}//4 3 2 1

我們發現，優先級隊列默認是大堆。

大堆小堆升序降序

優先級隊列默認是大堆

小于是大堆
大于是小堆

CPP中STL::sort()

小于是升序
大于是降序

這里區分兩個概念：取出結果是有序 與 真正排序 的區別。

在上面優先級隊列中，我們發現while+top取出的數據是有序的，這是因為我們每次取得都是堆頂元素。至于怎么弄的，可以參考C數據結構鐘堆刪除數據時候得操作，首尾交換，然后size--，我覺得應該是相同的操作。

顯然上面不是真正的有序，因為優先級隊列中是堆。我們可以用sort這個算法函數來進行區分。

我們發現兩個greater一個帶括號一個不帶，這是什么情況呢？

priority_queue<int, vector<int>, greater<int>> pq;
sort(v.begin(), v.end(), greater<int>());

模板參數與函數參數的需要

要注意優先級隊列是一種模板，需要的是類型進行實例化，而sort是函數模板實例化出來的一種函數，需要迭代器區間和具體的比較仿函數對象，而不是僅僅一個仿函數類型就行。

4.3. 仿函數

既然上面用到了仿函數，這里來介紹一下。

仿函數：也稱函數對象，仿函數是一種特殊的對象！他的對象可以像函數一樣去使用。

下面進行舉例：

//仿函數類
struct Less
{
public:bool operator()(const int& x, const int& y){return x < y;}
};void Test()
{Less lessfunc;cout << lessfunc(5,6) << endl; // 結果：1
}

這里需要注意哈，上面的數字5和6作為參數傳遞給operator()，如果要用引用來接收，必須前面加上const，因為這是引用常量值。

//仿函數類
struct Less
{
public:bool operator()(const int& x, const int& y){return x < y;}
};void Test()
{Less lessfunc;cout << lessfunc(5,6) << endl;//1vector<int> v = { 1,3,4,2 };vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}//1 3 4 2cout << endl;sort(v.begin(), v.end(), lessfunc);it = v.begin();while (it != v.end()){cout << *it << " ";it++;}//1 2 3 4
}

然后上面的仿函數類可以加上模板的語法，就跟我們用的greater<int>差不多了。

//仿函數類
template<typename T>
struct Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};void Test()
{vector<int> v = { 1,3,4,2 };vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;sort(v.begin(), v.end(), Less<int>());it = v.begin();while (it != v.end()){cout << *it << " ";it++;}
}

4.4. 優先級隊列模擬實現

#pragma once
#include<vector>
#include<iostream>
using namespace std;template<typename T>
struct Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<typename T>
struct Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};template<class T, class Container = vector<T>, class Compare = Greater<T>>
class periority_queue
{
private:Container _con;public:void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child + 1], _con[child])){child = child + 1;}if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con[0];}
};

// 指針模板
template<class T>
struct GreaterPDate
{bool operator()(const T& d1, const T& d2){return *d1 > *d2;}
};void test_priority_queue2()
{priority_queue<Date*, vector<Date*>, GreaterPDate<Date*>> pqptr;Date d1(2024, 4, 14);Date d2(2024, 4, 11);Date d3(2024, 5, 15);pqptr.push(&d1);pqptr.push(&d2);pqptr.push(&d3);while (!pqptr.empty()){cout << *(pqptr.top()) << " ";pqptr.pop();}cout << endl;
}

5. 反向迭代器

反向迭代器，顧名思義，反向迭代器的操作與正向迭代器恰好相反(方向)。

5.1. 簡單介紹

下面我用庫函數來進行一個簡單演示。

std::list<int> l = { 1,2,3,4,5,6 };
std::list<int>::reverse_iterator rit = l.rbegin();
while (rit != l.rend())
{std::cout << *rit << " ";++rit;
}//6 5 4 3 2 1
std::cout << std::endl;

5.2. 反向迭代器的設計思路

思路1：我們可以像前面實現const迭代器一樣寫一個類，顯然，這樣我們即使寫模板也需要針對不同的容器進行寫不同的反向迭代器。
思路2：封裝iterator，然后重載其部分運算符。

下面來重點介紹第二種思路的實現方式：

這樣的好處是，我們只需要設計一個反向迭代器類，就可以根據不同的正向迭代器自由變換其反向迭代器。

5.3. 反向迭代器的模擬實現

#define _CRT_SECURE_NO_WARNINGS 1namespace szg
{template<class Tterator, class Ref, class Ptr>class ReverseIterator{private:Tterator _it;public:typedef ReverseIterator<Tterator, Ref, Ptr> Self;//構造函數ReverseIterator(Tterator it):_it(it){}//解引用Ref operator*(){Tterator temp = _it;temp--;return *temp;}//->函數Ptr operator->(){return &(this->operator*());}//前置++Self& operator++(){--_it;return *this;}//前置--Self& operator--(){++_it;return *this;}//!=函數重載bool operator!=(const Self& s){return _it != s._it;}};
}

#include"List.h"
#include<list>void test()
{szg::list<int> l = { 1, 2, 3, 4, 5, 6 };/*l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);l.push_back(6);*/szg::list<int>::reverse_iterator rit = l.rbegin();while (rit != l.rend()){std::cout << *rit << " ";++rit;}//6 5 4 3 2 1std::cout << std::endl;
}int main()
{//std::list<int> l = { 1,2,3,4,5,6 };//std::list<int>::reverse_iterator rit = l.rbegin();//while (rit != l.rend())//{//	std::cout << *rit << " ";//	++rit;//}//6 5 4 3 2 1//std::cout << std::endl;test();return 0;
}