本文是小編鞏固自身而作，如有錯誤，歡迎指出！

本次我們介紹STL中的stack和queue和其相關的一些容器和仿函數

一.stack and queue

1.適配器

stack和queue其實不是真正意義上的容器，而是容器適配器，而容器適配器又是什么呢？

在C++中，容器適配器（Container Adapters）是一種特殊的容器，它們不提供獨立的底層數據存儲結構，而是基于其他基礎容器（如 vector、deque、list）來實現特定的功能和接口。

簡單來說就是之前我們學習的時要了解stack和queue的底層是什么，是數組還是隊列，同理在c++就考慮他的底層是vector還是list等等

而在官方給的底層是deque

?而deque又是什么呢？

2.deque

全稱為“double-ended queue”，即雙端隊列，是 C++ 標準模板庫（STL）中的一種容器。

簡單來說deque就是vector和list的縫合產物

通過前面的學習我們都知道，vector的尾插時間復雜度比頭插小，而list痛點在于不能隨機訪問，但deque就解決了這個問題

deque 是一種序列容器，它允許在容器的兩端快速插入和刪除元素，時間復雜度為 O(1)。與 vector 相比，deque 可以在頭部和尾部高效地進行元素的插入和刪除操作；與 list 相比，deque 支持隨機訪問元素。

deque的原理類似下圖?

?deque本質其實就是劃分一個個個小數組融合成為大數組，其由一個中控數組map操作，而map中儲存的就是每個小數組的地址，及其頭尾指針等等。

下面是用vector實現的棧和用list實現的隊列

#include<vector>
namespace bite
{template<class T>class stack{public:stack() {}void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_back();}T& top() {return _c.back();}const T& top()const {return _c.back();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:std::vector<T> _c;};
}

#include <list>
namespace bite
{template<class T>class queue{public:queue() {}void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_front();}T& back() {return _c.back();}const T& back()const {return _c.back();}T& front() {return _c.front();}const T& front()const {return _c.front();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}private:std::list<T> _c;};
}

?

二.priority_queue

1.priority_queue簡介

在 C++ 中，priority_queue（優先隊列） 是一種特殊的容器適配器，它基于堆（Heap）數據結構實現，提供常數時間訪問最大/最小元素的能力（默認最大堆）。

我們看下以下用例

#include<iostream>
#include<queue>
using namespace std;
int main()
{priority_queue<int> pq;pq.push(3);pq.push(5);pq.push(6);pq.push(1);pq.push(9);while (!pq.empty()){cout << pq.top();pq.pop();}return 0;}

?我們看出來這是系統默認的情況（最大堆），那么如果我們自己實現要自己模擬實現想要最小堆建怎么辦呢？

我們先看看模擬實現是什么樣的

#pragma once
#include<vector>
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;}
};
namespace yiming
{template<class T,class Container=std::vector<T>,class Compare=Less<T>>class priority_queue{public:priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last):con(first,last){//向下調整建堆for (int i = (con.size() - 1 - 1) / 2;i >= 0;i--){adjust_down(i);}}void push(const T& x){con.push_back(x);adjust_up(con.size() - 1);}void pop(){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:void adjust_up(int child)//向上調整{Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(con[parent], con[child])){swap(con[child], con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int 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++child;if (com(con[parent], con[child])){swap(con[parent], con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}private:Container con;};
}

其中我們看到了主要決定這個模擬實現的類型就行這樣一個模版

   template<class T,class Container=std::vector<T>,class Compare=Less<T>>

?我們看到通過這個模版的Compare就可以實現建大堆小堆，這里就涉及到一個概念，仿函數

2.仿函數

仿函數（Functor）是C++中一種行為類似函數的對象，通過重載operator()實現。它可以是普通函數指針、類成員函數指針或定義了operator()的類對象。

其實簡單來說就是把一個類包裝成函數的樣子

如上述代碼中的

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;}
};

這樣就可以通過模版來實現改變建大堆小堆了

三.測試代碼

int main()
{
priority_queue <int>pq;pq.push(4);pq.push(5);pq.push(2);pq.push(5);pq.push(6);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;stack<int> st;st.push(1);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;queue<int>q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front()<<" ";q.pop();}return 0;
}

本次分享就到這里結束了，后續會繼續更新，感謝閱讀!