stack & queue & priority_queue
- 1 stack
- 1.1 stack 介紹
- 1.2 stack 使用
- 1.3 stack 模擬實作
- 1.4 deque 的簡單介紹
- 2 queue
- 2.1 queue 介紹
- 2.2 queue 使用
- 2.3 queue 模擬實作
- 3 priority_queue
- 3.1 priority_queue 介紹
- 3.2 priority_queue 使用
- 3.3 仿函式的引入
- 3.4 priority_queue 模擬實作
- 4 容器配接器模式
1 stack
1.1 stack 介紹
- stack是一種容器配接器，專門用在具有后進先出操作的背景關系環境中，其洗掉只能從容器的一端進行元素的插入與提取操作，
- stack是作為容器配接器被實作的，容器配接器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函式來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即堆疊頂)被壓入和彈出，
- stack的底層容器可以是任何標準的容器類模板或者一些其他特定的容器類，這些容器類應該支持以下操作：empty：判空操作、back：獲取尾部元素操作、push_back：尾部插入元素操作、pop_back：尾部洗掉元素操作
- 標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器，默認情況下使用deque，
1.2 stack 使用
介面說明
1.3 stack 模擬實作
namespace czh
{
template<class T, class Container = deque<T>>
// template<class T, class Container = list<T>>
// template<class T, class Container = vector<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
const T& top() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
1.4 deque 的簡單介紹
原理
1、deque(雙端佇列)：是一種雙開口的"連續"空間的資料結構，注意和 queue 沒有關系雙開口的含義是：可以在頭尾兩端進行插入和洗掉操作，且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高，
2、deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個動態的二維陣列
3、雙端佇列底層是一段假象的連續空間，實際是分段連續的，為了維護其“整體連續”以及隨機訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設計就比較復雜，如下圖所示：
缺陷
- 與vector比較，deque的優勢是：頭部插入和洗掉時，不需要搬移元素，效率特別高，而且在擴容時，也不需要搬移大量的元素，因此其效率是比 vector 高的，
- 與list比較，其底層是連續空間，空間利用率比較高，不需要存盤額外欄位，
- 但是，deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下，而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層資料結構，
為何作為stack 和 queue的 默認 實作
- stack是一種后進先出的特殊線性資料結構，因此只要具有push_back()和pop_back()操作的線性結構，都可以作為stack的底層容器，比如vector和list都可以；queue是先進先出的特殊線性資料結構，只要具有push_back和pop_front操作的線性結構，都可以作為queue的底層容器，比如list，
但是STL中對stack和queue默認選擇deque作為其底層容器，主要是因為：
- stack 和 queue 不需要遍歷（因此stack 和 queue沒有迭代器），只需要在固定的一段或者兩端進行操作，
- 在 stack 中元素增長時，deque 比 vector 的效率高（擴容時候不需要搬移大量資料）；queue 中的元素增長時，deque 不僅效率高，而且記憶體使用率也高，
所以結合了deque的優點，完美遞避開了其缺陷
2 queue
2.1 queue 介紹
- 佇列是一種容器配接器，專門用于在FIFO背景關系(先進先出)中操作，其中從容器一端插入元素，另一端提取元素，
- 佇列作為容器配接器實作，容器配接器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函式來訪問其元素，元素從隊尾入佇列，從隊頭出佇列，
- 底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類，該底層容器應至少支持以下操作: empty：檢測佇列是否為空、size：回傳佇列中有效元素的個數、front：回傳隊頭元素的參考、back：回傳隊尾元素的參考、push_back：在佇列尾部入佇列、pop_front：在佇列頭部出佇列
- 標準容器類deque和list滿足了這些要求，默認情況下，如果沒有為queue實體化指定容器類，則使用標準容器deque，
2.2 queue 使用
介面介紹
2.3 queue 模擬實作
因為queue的介面中存在頭刪和尾插，因此使用vector來封裝效率太低，故可以借助list 和 deque 來模擬實作queue
namespace czh
{
// 設計模式 -- 配接器模式(配接器)
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
T& front()
{
return _con.front();
}
const T& front() const
{
return _con.front();
}
T& back()
{
return _con.back();
}
const T& back() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
3 priority_queue
3.1 priority_queue 介紹
- 優先級佇列是一種容器配接器，根據嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的那一個，
- 內部實作其實是堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素（優先級佇列中位于頂部的元素），
- 底層容器可以是任何標準容器類模板，也可以是其他特定設計的容器類，容器應該可以通過隨機訪問迭代器訪問，并支持以下操作：empty()：檢測容器是否為空、size()：回傳容器中有效元素個數、front()：回傳容器中第一個元素的參考、push_back()：在容器尾部插入元素、pop_back()：洗掉容器尾部元素
- 標準容器類vector和deque滿足這些需求，默認情況下，如果沒有為特定的priority_queue類實體化指定容器類，則使用vector，
- 需要支持隨機訪問迭代器，以便始終在內部保持堆結構，容器配接器通過在需要時自動呼叫演算法函式，make_heap、push_heap和pop_heap來自動完成此操作，
3.2 priority_queue 使用
優先級佇列默認使用 vector 作為其底層存盤資料的容器，在 vector 上又使用了堆演算法將 vector 中元素構成堆的結構，因此 priority_queue 就是堆，所以所有需要用到堆的位置，都可以考慮使用priority_queue，注意：默認priority_queue 是大堆，通過仿函式可以改變其為小堆，
#include <iostream>
#include <vector>
#include <queue>
#include <functional> // greater演算法的頭檔案
void TestPriorityQueue()
{
// 默認情況下，創建的是大堆，其底層按照小于號比較
vector<int> v{3,2,7,6,0,4,1,9,8,5};
priority_queue<int> q1;
for (auto& e : v)
q1.push(e);
cout << q1.top() << endl;
// 如果要創建小堆，將第三個模板引數換成greater比較方式
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
}
3.3 仿函式的引入
仿函式準確來說是一個類，這個類多載了operator()，這個類的物件呼叫 operator()，可以像函式一樣去使用，在優先級佇列中的使用可以控制創建的優先級佇列中是大堆還是小堆使其可以像水龍頭的開關一樣可以去控制熱水還是涼水，在 STL庫中中的兩個仿函式的實作如下：
STL 中的優先級佇列
舉例說明仿函式的應用
比如我們想買個手機，在京東上搜索手機，可以按照價格、銷量等標簽排序，那么我們可以利用仿函式簡單實作，寫一個商品類代表手機我們用排序演算法 sort 對其排序，但是我們不可以在類的內部多載 > < 運算子，因為我們并不知道如何排序，按照什么標準排序，為了更好說明問題，來盤代碼，
#include <iostream>
#include "priority_queue.h"
#include <algorithm>
#include <vector>
using namespace std;
//仿函式的應用
struct Phone{
int saleNum;
int price;
//.....
};
struct LessPhonePrice{
bool operator()(const Phone& p1, const Phone& p2)
{
return p1.price < p2.price;
}
};
struct LessPhoneSaleNum{
bool operator()(const Phone& p1, const Phone& p2)
{
return p1.saleNum < p2.saleNum;
}
};
void TestSort()
{
vector <Phone> gv = { { 1, 3 }, { 5, 2 }, { 2, 10 } };
sort(gv.begin(), gv.end(),LessPhoneSaleNum());//匿名物件會在STL中呼叫我自己寫的比較方法
sort(gv.begin(), gv.end(), LessPhonePrice());
}
int main()
{
TestSort();
return 0;
}
3.4 priority_queue 模擬實作
因為優先級佇列的底層結構就是堆所以對 vector 進行適當封裝就可以了，如果不知道堆的知識請參考我的另外一篇文章 https://blog.csdn.net/CZHLNN/article/details/112481962
#pragma once
//仿函式
template<class T>
class Less{
public:
bool operator()(const T& t1, const T& t2) const
{
return t1 < t2;
}
};
template<class T>
class Greater{
public:
bool operator()(const T& t1, const T& t2) const
{
return t1 > t2;
}
};
namespace czh{
template<class T, class Container = vector<T>, class Compare = Greater<T>>
class priority_queue {
public:
priority_queue() = default;
/*priority_queue()
{}*/
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first, last)
{
//利用向下調整演算法，從下到上建堆
/*for (int i = (_con.size() - 2) / 2; i >= 0; i--)
{
AdjustDown(i);
}*/
利用向上調整演算法，從上到下調整
for (size_t i = 1; i < _con.size(); i++)
{
AdjustUp(i);
}
}
void push(const T& data)
{
_con.push_back(data);
// 向上調整
AdjustUp(_con.size() - 1);
}
void pop()
{
if (empty()) return;
swap(_con.front(),_con.back());
_con.pop_back();
AdjustDown(0);
}
size_t size() const
{
return _con.size();
}
const T& top() const
{
return _con.front();
}
bool empty() const
{
return _con.empty();
}
private:
//向上調整演算法
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) >> 1;
while (child > 0)
{
/*if (_con[child] > _con[parent])*/
if (com(_con[child], _con[parent]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) >> 1;
}
else
{
break;
}
}
}
void AdjustDown(int parent)
{
Compare com;
size_t child = 2 * parent + 1;
while (child < _con.size())
{
/*if (child + 1 < _con.size() && _con[child + 1] < _con[child])*/
if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
{
child++;
}
/*if (_con[child] > _con[parent])*/
if (com(_con[child], _con[parent]))
{
swap(_con[child], _con[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//向下調整演算法
Container _con;
};
}
4 容器配接器模式
配接器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總結)，該種模式是將一個類的介面轉換成客戶希望的另外一個介面，
上面介紹的3種資料結構都是容器配接器（container adapter），
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/277385.html
標籤：其他
上一篇：網路 TCP協議(C++代碼|通過tcp協議實作客戶端與服務端之間的通信)
下一篇：C語言初階零基礎學習（一）