目錄

1.什么是queue

2.模擬實現

3.仿函數

模板參數Compare

仿函數

?4.什么是priority_queue

模擬實現

---

1.什么是queue

1.隊列是一種容器適配器，專門用于在FIFO上下文(先進先出)中操作，其中從容器一端插入元素，另一端提取元素。

2.隊列作為容器適配器實現，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從隊尾入隊列，從隊頭出隊列。

3.底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類。該底層容器應至少支持以下操作:

4.標準容器類deque和list滿足了這些要求。默認情況下，如果沒有為queue實例化指定容器類，則使用標準容器deque。

empty：檢測隊列是否為空
size：返回隊列中有效元素的個數
front：返回隊頭元素的引用
back：返回隊尾元素的引用
push_back：在隊列尾部入隊列
pop_front：在隊列頭部出隊列

用法跟stack一樣，可以看上一篇文章

2.模擬實現

queue.h

#include "string.h"
#include<iostream>
#include<stack>
#include<deque>using namespace std;namespace lty
{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();}T& back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void testqueue(){queue<int,deque<int>> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;}
}

queue.cpp

#include "queue.h"using namespace std;int main()
{lty::testqueue();
}

3.仿函數

模板參數Compare

#include <iostream>
#include <queue>int main() {std::priority_queue<int> maxHeap; // 默認大堆std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 小堆maxHeap.push(5);maxHeap.push(3);maxHeap.push(8);minHeap.push(5);minHeap.push(3);minHeap.push(8);std::cout << "Max Heap (Top element): " << maxHeap.top() << std::endl;std::cout << "Min Heap (Top element): " << minHeap.top() << std::endl;return 0;
}

?

仿函數

仿函數實際就是一個類，這里類實例化出來的對象叫做函數對象，下面命名空間wyn中的兩個仿函數就分別是兩個類，在使用時直接用類進行實例化對象，然后讓對象調用()的運算符重載，這樣我們看到的調用形式就非常像普通的函數調用，但實際上這里并不是函數調用，而是仿函數實例化出來的對象調用了自己的operator()重載成員函數。

?

namespace lty
{template <class T>class less{public:bool operator()(const T& x, const T& y)const{return x < y;}};template <class T>class greater{public://將仿函數放成public，要不然class默認是私有的bool operator()(const T& x, const T& y)const{return x > y;}};
}
int main()
{lty::less<int> lessFunc;lty::greater<int> greaterFunc;lessFunc(1, 2);//你以為這里是函數調用，但他其實是仿函數對象lessFunc調用了他的成員運算符重載()函數。
}

?4.什么是priority_queue

優先級隊列的適配會更復雜一些些。它的適配容器用的是vector。

優先級隊列就不是什么先進先出了，它雖然叫隊列，但它不是真隊列。其實它的底層是堆，可以在任意時刻插入數據，默認是大堆，當然也可以通過仿函數去調整。

優先級隊列有一個反人類的設計：傳less仿函數，底層是大堆。傳greater仿函數，底層是小堆。

它的一些接口

priority_queue和queue以及stack一樣，他們都是由底層容器適配出來的適配器，之不過priority_queue采用的適配容器不再是deque而是vector，選擇vector的原因也非常簡單，在調用向上或向下調整算法時，需要大量頻繁的進行下標隨機訪問，這樣的情境下，vector就可以完美展現出自己結構的絕對優勢

模擬實現

#pragma oncenamespace lty
{// Compare進行比較的仿函數 less->大堆// Compare進行比較的仿函數 greater->小堆template<class T, class Container = vector<T>, class Compare = std::less<T>>class priority_queue{public:priority_queue(){}template <class InputIterator>         priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}for (int i = (_con.size()-1-1)/2; i >= 0; --i){adjust_down(i);}}void adjust_up(size_t child){Compare com;size_t 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 push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){Compare com;size_t 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;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}bool empty()  const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}

命名空間 xzq：
這段代碼位于命名空間 xzq 中，這是一個自定義的命名空間，用于將相關的類、函數等封裝在一起，以避免與其他代碼的命名沖突。

模板類 priority_queue：
這是一個模板類，它代表了一個優先隊列的實現。它接受三個模板參數：T（元素類型），Container（底層容器類型，默認為 std::vector<T>），和 Compare（用于比較元素的仿函數，默認為 std::less<T>）

Compare 是一個模板參數，用于進行元素的比較。它是一個仿函數，可以是 std::less<T>（默認）或 std::greater<T>，具體取決于用戶提供的優先隊列類型。Compare 仿函數用于確定在堆中的元素排序方式，從而決定了是最大堆還是最小堆。在 priority_queue 類的各個成員函數中，通過調用 Compare 仿函數來進行元素的比較，從而實現了插入和調整堆的操作。

構造函數 priority_queue()：
這是一個默認構造函數，不需要使用 Compare 仿函數進行比較。

構造函數模板 priority_queue(InputIterator first, InputIterator last)：
在構造函數內部，使用 Compare 仿函數來執行比較操作，以確定元素的順序。在添加元素后，通過調用 adjust_down 函數來構建堆。

成員函數 adjust_up(size_t child)：
在上浮操作中，使用 Compare 仿函數執行比較，以確定是否需要交換父子節點的位置，從而保持堆的性質。

成員函數 push(const T& x)：
在插入操作中，首先將新元素添加到底層容器 _con，然后通過調用 adjust_up 函數來執行上浮操作，保證新元素位于合適的位置。

成員函數 adjust_down(size_t parent)：
在下沉操作中，使用 Compare 仿函數執行比較，以確定是否需要交換父子節點的位置，從而保持堆的性質。

成員函數 pop()：
在刪除操作中，首先將頂部元素與底層容器的最后一個元素交換，然后通過調用 adjust_down 函數來執行下沉操作，保證堆的性質。

成員函數 const T& top()：
通過返回 _con[0]，獲取優先隊列的頂部元素。
?