容器適配器

容器適配器（Container Adapter）是C++標準模板庫（STL）中的一種設計模式，專門用于提供一種經(jīng)過簡化和限制的接口，使得不同的容器類型可以表現(xiàn)出類似的行為。容器適配器不會創(chuàng)建新的容器，而是基于已有的容器（如 deque、vector 等）進行包裝，以改變或限制其接口，從而提供不同的行為和使用方式。

STL 中常見的容器適配器有以下三種：

1. 棧（Stack）

• 使用 std::stack 類實現(xiàn)。

• 默認底層容器為 std::deque，也可以用 std::vector 或 std::list 替換。

• 棧是“后進先出” (LIFO) 數(shù)據(jù)結構，適配器屏蔽了底層容器的大部分接口，提供 push、pop 和 top 操作。

2. 隊列（Queue）

• 使用 std::queue 類實現(xiàn)。

• 默認底層容器為 std::deque，也可以使用其他序列容器（如 std::list）。

• 隊列是“先進先出” (FIFO) 數(shù)據(jù)結構，適配器僅保留 push、pop 和 front、back 等接口。

3. 優(yōu)先級隊列（Priority Queue）

• 使用 std::priority_queue 類實現(xiàn)。

• 默認底層容器為 std::vector，底層使用堆結構進行元素排序。

• 優(yōu)先級隊列允許快速訪問和移除最高優(yōu)先級的元素。適配器提供 push、pop 和 top 操作，自動按照優(yōu)先級排序。

容器適配器的特點

• 簡化接口：容器適配器通過隱藏底層容器的復雜接口，使用戶能夠更專注于特定的數(shù)據(jù)結構（如棧或隊列）的特性。

• 靈活底層容器：容器適配器可以基于不同的底層容器構建，但需滿足特定的要求。例如，?？梢杂?deque 或 vector 作為底層容器。

• 與容器解耦：通過使用適配器，用戶不需要關心底層容器的實現(xiàn)細節(jié)，只需專注于適配器提供的接口。

總體而言，容器適配器是一種設計模式，通過包裝現(xiàn)有容器來提供定制化的數(shù)據(jù)結構接口，使程序設計更加簡單和靈活。

---

棧和隊列的模擬實現(xiàn)

我們通過適配器就能將棧和隊列進行模擬實現(xiàn)了

stack.h

#pragma once
#include<vector>
#include<list>
#include<deque>
//template<class T>
//class stack
//{
//private:
//	T* a;
//	size_t _top;
//	size_t _capacity;
//};//  T（棧中存儲的數(shù)據(jù)類型）和 Container（底層容器類型）
/*
當你在實例化這個模板類時，例如 stack<int, std::vector<int>> myStack;，編譯器就會根據(jù)傳入的模板參數(shù) int 和 std::vector<int> 來推導出具體的 T 和 Container 類型。
模板實例化：在編譯階段，編譯器會用傳遞的模板參數(shù)類型 T 和 Container 來實例化這個模板類 stack，并生成相應的類定義。例如，如果你傳入的是 stack<int, std::vector<int>>，
編譯器會生成一個 stack<int, std::vector<int>> 的具體實例，并將代碼中所有的 T 替換為 int，Container 替換為 std::vector<int>。
模板函數(shù)的調用：在使用這個棧的成員函數(shù)時，編譯器也會根據(jù)實例化后的具體類型來判斷類型。例如 _con.push_back(x); 調用時，
編譯器會檢查 _con 是什么容器類型（在這種情況下是 std::vector<int>），從而驗證 push_back 是否可以接受 int 類型的參數(shù) x。
*///T是元素的類型，這個Container是容器的類型，我們通過容器進行函數(shù)的調用操作
namespace kai
{//函數(shù)參數(shù)能加缺省值，那么我們的模版參數(shù)也是可以加缺省值的//如果我們沒傳的話就用的是缺省值，傳了的話那么就用我們傳的值//我們這里默認用的是一個deque的容器template<class T, class Container=deque<T>>//Container就是容器的意思,存的是底層的數(shù)據(jù)類型class stack{public:void push(const T& x){_con.push_back(x);}void pop()//不需要加參數(shù) {_con.pop_back();//將尾部的數(shù)據(jù)pop掉}const T& top() const//返回棧頂位置數(shù)據(jù){return _con.back();//直接返回尾部的數(shù)據(jù)，通用接口}size_t size() const{return  _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

queue.h

#pragma once
#include<vector>
#include<list>
#include<deque>namespace kai
{//deque既可以做棧也可以做隊列的適配容器template<class T, class Container = deque<T>>//Container就是容器的意思,存的是底層的數(shù)據(jù)類型class queue//隊尾入數(shù)據(jù)，隊頭出數(shù)據(jù){//vector不能適配隊列，這里不能頭刪public:void push(const T& x)//入隊列--尾{_con.push_back(x);}void pop()//   出隊列---頭刪{_con.pop_front();//將頭部的數(shù)據(jù)pop掉}const T&front() const{return _con.front(); //直接返回頭部的數(shù)據(jù)，通用接口}const T& back() const//返回棧頂位置數(shù)據(jù){return _con.back();//直接返回尾部的數(shù)據(jù)，通用接口}size_t size() const{return  _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}

test.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<queue>#include"stack.h"
#include"Queue.h"
using namespace std;
int main()
{kai::stack<int,list<int>>st;//前面是數(shù)據(jù)的類型。后面是容器的類型st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty())//不斷取值直到棧為空{cout << st.top() << " ";st.pop();//頭刪替換下個數(shù)據(jù)}cout << endl;//這里的vector是會報錯的，因為vector是不支持這里的pop的kai::queue<int, list<int>>q;//前面是數(shù)據(jù)的類型。后面是容器的類型q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty())//不斷取值直到棧為空{cout << q.front() << " ";q.pop();//頭刪替換下個數(shù)據(jù)}cout << endl;return 0;
}

當你在實例化這個模板類時，例如 stack<int, std::vector> myStack;，編譯器就會根據(jù)傳入的模板參數(shù) int 和 std::vector 來推導出具體的 T 和 Container 類型。
模板實例化：在編譯階段，編譯器會用傳遞的模板參數(shù)類型 T 和 Container 來實例化這個模板類 stack，并生成相應的類定義。例如，如果你傳入的是 stack<int, std::vector>，
編譯器會生成一個 stack<int, std::vector> 的具體實例，并將代碼中所有的 T 替換為 int，Container 替換為 std::vector。
模板函數(shù)的調用：在使用這個棧的成員函數(shù)時，編譯器也會根據(jù)實例化后的具體類型來判斷類型。例如 _con.push_back(x); 調用時，
編譯器會檢查 _con 是什么容器類型（在這種情況下是 std::vector），從而驗證 push_back 是否可以接受 int 類型的參數(shù) x。

---

deque的介紹

deque叫做雙端隊列，兩端都可以進行插入刪除的操作

頭尾都可以支持插入刪除數(shù)據(jù)的

deque的技能樹點的比較滿，啥都會

那么就說明deque就可以將list和vector的技能都帶上

vector是一塊連續(xù)的空間，list是一個個小塊的空間通過指針進行連接起來的

deque的缺陷在哪里呢？

insert和erase

1.挪動后面所有數(shù)據(jù)，效率低

2.只挪動當前buffer的數(shù)據(jù)，每個buffer大小就不一樣了，insert 、 erase的效率不錯，但是[]的效率直線下降

deque的頭尾插入刪除的效率還是不錯的

適當?shù)南聵嗽L問可以使用deque

但是得大量的下標訪問就不適合用deque了

所以棧和隊列的適配容器是deque

deque的核心結構是迭代器進行支撐的

deque里面只有兩個迭代器，start和finish

在 C++ 中，deque 是一種雙端隊列容器，允許在兩端高效地插入和刪除元素。盡管 deque 在某些方面具有優(yōu)勢，但在特定使用場景下仍然存在一些缺陷或限制：

1. 內(nèi)存開銷較高

• deque 的內(nèi)存布局并不像 vector 一樣是連續(xù)的內(nèi)存塊，而是分段的。這使得 deque 會有額外的內(nèi)存管理開銷，因此其內(nèi)存利用率通常比 vector 低。

• 對于需要大量小型數(shù)據(jù)結構的應用，deque 的內(nèi)存分塊可能帶來一定的開銷。

2.隨機訪問性能略低于 vector

• 雖然 deque 支持隨機訪問（允許使用 operator[] 和 at），但由于 deque 是分塊存儲的，因此在訪問元素時，尤其是訪問中間位置的元素時，性能會略低于 vector，因為它需要定位具體的分塊位置。

3. 與指針或迭代器的兼容性r

• deque 的指針或迭代器在插入和刪除操作后可能會失效，尤其是在中間插入或刪除元素時。

• 雖然 deque 的頭尾插入操作不會像 vector 一樣導致整個容器重新分配，但在擴展容量時，它可能會重新配置分塊，這會導致指針和迭代器失效。

4. 不適合用于需要頻繁中間插入和刪除的場景

• deque 在頭尾的插入和刪除操作效率很高，但在中間位置插入或刪除元素時會導致較多的數(shù)據(jù)移動，從而影響性能。因此，如果需要頻繁在中間位置進行插入或刪除操作，deque 不是最佳選擇，list 或 std::vector（如果可以接受一定的重新分配開銷）可能會更合適。

5. 在特定平臺上的實現(xiàn)不一致

• 不同的編譯器和標準庫實現(xiàn)可能會對 deque 采用不同的分塊策略。這可能導致在不同平臺上的性能和內(nèi)存使用情況有所不同，從而帶來一些不可預測的行為。

6. 缺乏shrink_to_fit支持

• C++ 標準中沒有要求 deque 支持 shrink_to_fit，即使進行了刪除操作，deque 可能不會自動釋放不再使用的內(nèi)存，導致可能的內(nèi)存浪費。

總結

deque 在需要高效的雙端插入和刪除操作時非常有用，但在需要頻繁的中間操作或更高的隨機訪問性能時，它的效率可能不如 vector。選擇容器時應根據(jù)具體需求進行權衡，以最大限度地發(fā)揮各容器的優(yōu)勢。

題目

215. 數(shù)組中的第K個最大元素

class Solution {
public:int findKthLargest(vector<int>& nums, int k){//將數(shù)組中的元素先放入到優(yōu)先級隊列中,默認是大堆priority_queue<int> p(nums.begin(),nums.end());//我們刪除k-1次，那么循環(huán)結束的時候的堆頂?shù)臄?shù)據(jù)就是當前最大了的，我們直接返回堆頂數(shù)據(jù)就行了while(--k)//--k是走k-1次,k--是走k次{p.pop();}return p.top();}
};

---

priority_queue 優(yōu)先級隊列

默認是大的優(yōu)先級最高

priority_queue 是一種基于優(yōu)先級的隊列數(shù)據(jù)結構，通常實現(xiàn)為一個堆（heap），可以支持快速插入和刪除優(yōu)先級最高的元素。在 priority_queue 中，元素的順序不是按插入順序排列的，而是根據(jù)優(yōu)先級排序。通常有兩種類型的優(yōu)先隊列：

1. 最大優(yōu)先隊列：優(yōu)先級最高的元素位于隊列頂部（即最大值在最前面）。

2. 最小優(yōu)先隊列：優(yōu)先級最低的元素位于隊列頂部（即最小值在最前面）。

以下是一些關于 priority_queue 的關鍵操作：

• 插入元素：將新元素插入到隊列中，優(yōu)先級隊列會自動調整元素的位置。

• 訪問隊首元素：訪問優(yōu)先級最高的元素（在最大優(yōu)先隊列中為最大值，在最小優(yōu)先隊列中為最小值）。

• 刪除隊首元素：刪除優(yōu)先級最高的元素。

• 判斷隊列是否為空：檢查隊列中是否有元素。

在 C++ 標準模板庫（STL）中，priority_queue 的使用非常常見，以下是一個簡單的代碼示例：

#include <iostream>
#include <queue>int main() {std::priority_queue<int> maxQueue;  // 默認是最大優(yōu)先隊列// 插入元素maxQueue.push(10);maxQueue.push(30);maxQueue.push(20);maxQueue.push(5);// 輸出并刪除最大元素while (!maxQueue.empty()) {std::cout << maxQueue.top() << " ";maxQueue.pop();}return 0;
}

使用最小優(yōu)先隊列

在 C++ 中，要創(chuàng)建最小優(yōu)先隊列，可以使用以下方式：

std::priority_queue<int, std::vector<int>, std::greater<int>> minQueue;

使用場景

• 任務調度：例如操作系統(tǒng)中的任務調度器，根據(jù)任務的優(yōu)先級調度執(zhí)行任務。

• 路徑查找：如 Dijkstra 算法使用優(yōu)先隊列來找到最短路徑。

• 事件驅動模擬：在模擬系統(tǒng)中用來根據(jù)事件的優(yōu)先級處理事件。

priority_queue 是一種非常高效的數(shù)據(jù)結構，適合需要頻繁處理優(yōu)先級數(shù)據(jù)的場景。

int main()
{//優(yōu)先級隊列//優(yōu)先級默認是大的優(yōu)先級高//priority_queue<int> pq;//下面的就是小的優(yōu)先級高了priority_queue<int,vector<int>,greater<int>> pq;//前面是數(shù)據(jù)的類型。后面是容器的類型pq.push(3);pq.push(2);pq.push(1);pq.push(4);while (!pq.empty())//不斷取值直到棧為空{cout << pq.top() << " ";pq.pop();//頭刪替換下個數(shù)據(jù)}return 0;
} 

priority_queue的模擬實現(xiàn)

#pragma once
#include<vector>//默認是vector進行適配的
//堆是將數(shù)組看成完全二叉樹的
//假設p是父親，那么2*p+1是左孩子，2*p+2是右孩子
//所以對于子節(jié)點的話，-1然后/2就能算到父親節(jié)點的下標了
namespace kai
{//仿函數(shù)
//對象可以像函數(shù)一樣進行使用，因為他重載了operator()template <class T>struct less{bool operator() (const T& x, const T& y)const{return x < y;}};template <class T>struct greater//大堆，大于的比較{bool operator() (const T& x, const T& y)const{return x > y;}};//Compare是類型，我們這里默認值是小堆template<class T ,class Container=vector<T>,class Compare=less<T>>//優(yōu)先級隊列class priority_queue{public:priority_queue() = default;//default是強制生成//我們不寫默認構造的話那么就會調用對應類型的默認構造函數(shù)了template<class InputIterator>//構造函數(shù)priority_queue(InputIterator first, InputIterator last)//這里傳的是迭代區(qū)間:_con(first,last)//直接用這個迭代區(qū)間進行初始化的操作{//進行建堆的操作/*在構建堆（特別是最大堆或最小堆）的過程中，我們之所以從倒數(shù)第一個非葉子節(jié)點開始，是因為葉子節(jié)點本身已經(jīng)是一個有效的堆。下面是具體原因和背后的邏輯：1. **葉子節(jié)點天然滿足堆性質**：堆的性質要求每個節(jié)點的值滿足特定條件，比如最大堆要求每個節(jié)點的值大于或等于其子節(jié)點的值，最小堆要求每個節(jié)點的值小于或等于其子節(jié)點的值。葉子節(jié)點沒有子節(jié)點，自然滿足堆的定義。所以我們無需對葉子節(jié)點進行任何調整。2. **從倒數(shù)第一個非葉子節(jié)點開始可以逐層調整堆**：如果我們從倒數(shù)第一個非葉子節(jié)點開始進行“下沉”操作（即調整該節(jié)點與其子節(jié)點的關系以滿足堆的性質），則可以逐步調整每一層節(jié)點，從而最終得到一個完整的堆結構。這個過程叫做“自底向上”建堆，從倒數(shù)的非葉子節(jié)點開始，避免重復調整上層節(jié)點，提高了構建效率。3. **提高構建效率**：構建堆的時間復雜度是 \(O(n)\)，而不是 \(O(n \log n)\)，因為從倒數(shù)第一個非葉子節(jié)點開始向上調整，比從根節(jié)點開始構建效率高得多。倒數(shù)的非葉子節(jié)點數(shù)量較少，而且每個節(jié)點的調整次數(shù)隨深度的增加而減少，這種方式在平均情況下只需執(zhí)行有限的調整操作。4. **構建過程的穩(wěn)定性**：自底向上從非葉子節(jié)點開始構建可以保證堆的結構穩(wěn)定，不會因為上層節(jié)點的調整而打亂下層已經(jīng)滿足堆性質的節(jié)點。這保證了最終得到的是一個合法的堆。因此，從倒數(shù)第一個非葉子節(jié)點開始建堆是一種高效、合理的方式。*/for (int i = (_con.size()-1-1)/2; i >=0; i--){//這里的第一個-1是最后一個數(shù)的下標，第二個-1配合外面的/2可以找到我們的父親節(jié)點，這個節(jié)點就是倒數(shù)第一個非葉子節(jié)點了，我們從這個開始進行建堆的操作//我們從這個位置開始進行調整，不斷的調整到根節(jié)點//向下調整算法要求左右子樹都是大堆的，不然是無效的AdjustDown(i);}//我們從倒數(shù)第一個非葉子節(jié)點進行建堆的操作可以保證堆的結構正確}//向上調整算法void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;//算出父親節(jié)點的下標位置while (child > 0){//if (_con[parent]<_con[child]  )//父親小于孩子，實現(xiàn)大堆if (com(  _con[parent],_con[child]))//利用com對象進行比較大小，我們這里的默認傳的是greater{//直接利用C++中的swap函數(shù)進行交換就行了swap(_con[child], _con[parent]);//將父親節(jié)點和子節(jié)點的值進行交換的操作child = parent;//然后我們的孩子節(jié)點就跑到了父親節(jié)點的位置了parent = (parent - 1) / 2;//然后父親節(jié)點的位置就跑到了當前父親節(jié)點的父親節(jié)點那里了}else{//如果調整的過程中孩子節(jié)點的值比父親節(jié)點的值大了，我們就直接跳出循環(huán)就行了，不進行操作了break;}    }}void push(const T& x)//在堆中繼續(xù)數(shù)據(jù)的插入的操作{//先插入x_con.push_back(x);//進行向上調整（小堆）AdjustUp(_con.size() - 1);//size-1就是最后一個數(shù)據(jù)的位置的下標，然后我們利用向上調整算法進行調整的操作}void AdjustDown(int parent){Compare com;size_t child = parent * 2 + 1;//通過給的父親的位置算出左孩子的位置while (child<_con.size()){//我們這里是小堆//假設，選出左右孩子中小的那個孩子//if (child + 1 < _con.size() && _con[child]<_con[child + 1]  )//如果右孩子存在的話，并且右孩子大于左孩子的話if (child + 1 < _con.size() && com(_con[child],_con[child + 1]  ))//如果右孩子存在的話，并且右孩子大于左孩子的話{++child;//那么我們就將我們的孩子節(jié)點定位到右孩子的位置那里}if (com(_con[parent],_con[child]  ))//如果當前孩子節(jié)點小于父親節(jié)點的話{//我們就將小的節(jié)點往上面進行交換swap(_con[child], _con[parent]);parent = child;//然后我們父親節(jié)點就定位到當前的孩子節(jié)點了child = parent * 2 + 1;//算出當前孩子節(jié)點的孩子節(jié)點}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);//交換堆頂數(shù)據(jù)和最后一個數(shù)據(jù)_con.pop_back();//然后將最后一個數(shù)據(jù)進行時刪除的操作就行了//進行向下調整的操作，從根位置開始向下進行調整的操作AdjustDown(0);}bool empty()//判空函數(shù){return _con.empty();}const T& top()//返回堆頂?shù)臄?shù)據(jù){return _con[0];//就是返回根位置的數(shù)據(jù)就行了}size_t size(){return _con.size();}private:Container _con;//存放數(shù)據(jù)的容器};
}

仿函數(shù)的介紹

//仿函數(shù)
//對象可以像函數(shù)一樣進行使用，因為他重載了operator()
template <class T>
struct Less
{bool operator() (const T& x, const T& y)const{return x < y;}
};template <class T>
struct Greater
{bool operator() (const T& x, const T& y)const{return x > y;}
};int main()
{Less<int> lessFunc;cout << lessFunc(1, 2) << endl;cout << lessFunc.operator()(1, 2) << endl;return 0;
}

仿函數(shù)（Functor）是一種在C++和其他編程語言中使用的技術，它使得對象可以像函數(shù)一樣被調用。仿函數(shù)通常通過重載 operator() 操作符來實現(xiàn)，使得一個對象可以像函數(shù)那樣接受參數(shù)并返回結果。仿函數(shù)的主要優(yōu)勢在于它將函數(shù)的功能和狀態(tài)封裝到對象中，使得函數(shù)調用更加靈活、模塊化和可擴展。

仿函數(shù)的基本概念

在C++中，可以通過重載 operator() 操作符來定義一個仿函數(shù)，使得一個對象可以像普通函數(shù)一樣被調用。仿函數(shù)通常定義為一個類的成員函數(shù)，允許該類的對象具備類似函數(shù)的行為。

仿函數(shù)的基本用法

下面是一個簡單的仿函數(shù)示例，通過重載 operator() 來實現(xiàn)一個加法仿函數(shù)：

#include <iostream>class Adder {
public:int operator()(int a, int b) const {return a + b;}
};int main() {Adder add;int result = add(3, 4); // 對象像函數(shù)一樣被調用std::cout << "Result: " << result << std::endl; // 輸出 Result: 7return 0;
}

在這個例子中，Adder 類重載了 operator() 操作符，使得其對象 add 可以像一個函數(shù)一樣通過 add(3, 4) 的形式來調用，返回結果 7。

仿函數(shù)的優(yōu)點

1. 靈活性：仿函數(shù)可以攜帶狀態(tài)，可以存儲數(shù)據(jù)和維護狀態(tài)，適合需要保存計算狀態(tài)的場景。

2. 性能優(yōu)化：由于仿函數(shù)是類的一部分，它們可以通過內(nèi)聯(lián)函數(shù)進行優(yōu)化，從而獲得比普通函數(shù)指針更好的性能。

3. 可定制性：可以根據(jù)需求重載多個 operator()，使得對象可以接收不同類型和數(shù)量的參數(shù)。

4. 更符合面向對象設計：仿函數(shù)可以使用類的其他成員和方法，因此可以實現(xiàn)更復雜的操作和邏輯。

常見的仿函數(shù)應用

5. STL 算法配合使用：標準庫中的許多算法，如 std::sort、std::for_each 等都可以接受仿函數(shù)作為參數(shù)。

6. Lambda表達式的替代：在沒有Lambda表達式的C++版本中，仿函數(shù)被廣泛用于類似的場景。

7. 策略模式：在設計模式中，仿函數(shù)常用于實現(xiàn)策略模式，用于傳遞可定制的算法。

示例：在STL中使用仿函數(shù)

#include <iostream>
#include <vector>
#include <algorithm>class MultiplyBy {int factor;
public:MultiplyBy(int f) : factor(f) {}int operator()(int value) const {return value * factor;}
};int main() {std::vector<int> values = {1, 2, 3, 4, 5};std::transform(values.begin(), values.end(), values.begin(), MultiplyBy(3));for (int value : values) {std::cout << value << " "; // 輸出 3 6 9 12 15}return 0;
}

在這個例子中，我們定義了一個 MultiplyBy 仿函數(shù)類，用于將每個元素乘以一個特定因子。然后使用 std::transform 將 MultiplyBy(3) 仿函數(shù)應用于容器中的每個元素。

總結

仿函數(shù)通過重載 operator() 來賦予對象函數(shù)的能力，使得它們能夠和函數(shù)指針、Lambda表達式等互相替代并發(fā)揮作用。在C++編程中，仿函數(shù)廣泛應用于STL算法和其他需要靈活函數(shù)調用的場景。

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;
};
//聲明和定義分離
ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}struct DateLess
{bool operator() (const Date* d1, const Date* d2)//傳過來的是兩個指針，我們希望的是兩個指針指向的值進行比較{//我們直接進行解引用進行比較的操作return *d1 < *d2;}
};int main()
{// 大堆，需要用戶在自定義類型中提供<的重載kai::priority_queue<Date*,vector<Date*>,DateLess> q1;//優(yōu)先級隊列q1.push(new Date{2024,10,23});q1.push(new Date{2024,5,27});q1.push(new Date{2024,11,7});while (!q1.empty())//不斷取值直到棧為空{cout << *q1.top() << " ";q1.pop();//頭刪替換下個數(shù)據(jù)}cout << endl;return 0;return 0;
}

題目

155.最小棧

題目

class MinStack
{
public:MinStack(){}void push(int val){_st.push(val);//我們的st這個棧正常插入數(shù)據(jù)if(_minst.empty()||val<=_minst.top())//如果_minst這個棧為空的話或者傳過來的val小于等于_minst棧頂?shù)脑氐脑?#xff0c;我們就將數(shù)據(jù)插入到minst中{//如果這個minst這個棧是空的話，我們就進行數(shù)據(jù)的同步插入，如果這個插入數(shù)據(jù)小于我們的minst棧頂?shù)臄?shù)據(jù)的話我們就進行最小元素的更新操作，如果我們插入的元素等于我們的minst棧頂?shù)脑氐脑?#xff0c;就是等于我們當前minst這個棧棧頂?shù)淖钚≡氐脑?#xff0c;我們也是需要進行插入，_minst.push(val);}}void pop(){if(_st.top()==_minst.top()){//如果st這個棧和minst這個棧的棧頂元素都相等的話，那么我們都需要進行刪除操作的_minst.pop();}_st.pop();//st這個棧正常進行刪除操作，我們需要對minst這個棧進行一個判斷操作，如果當前兩個棧的棧頂元素相同的話，那么我們就進行minst這個棧的棧頂元素的刪除操作}int top(){return _st.top();//返回我們的st這個棧的棧頂元素就行了}int getMin(){//獲取最小值的話我們就將minst這個棧的棧頂元素進行返回就行了，因為這個棧是進行插入元素中最小的元素的更新的return _minst.top();}
private:
//通過兩個棧我們實現(xiàn)了找到最小元素的功能了
/*
如果我們的st存入5的話，然后我們的minst記錄當前的最小值存放棧中，就是存放5
然后存入4，那么st存入4，minst也存入4，更新最小值
然后我們st存放6，那么我們的minst更新最小值還是4
然后我們放入1的話，minst更新最小值，那么就存入1了
如果我們要pop我們的st棧頂元素的話，那么我們的minst同樣更新最小值，那么最小值就變成上一個最小值4了這個MinStack這個類我們是不需要寫默認構造的，編譯器默認生成一個無參的構造
這里我們的自定義類型st和minst會自動調用自己的構造函數(shù)的，我們是不需要顯示寫的
*/stack<int> _st;stack<int> _minst;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

通過兩個棧我們實現(xiàn)了找到最小元素的功能了

如果我們的st存入5的話，然后我們的minst記錄當前的最小值存放棧中，就是存放5

然后存入4，那么st存入4，minst也存入4，更新最小值

然后我們st存放6，那么我們的minst更新最小值還是4

然后我們放入1的話，minst更新最小值，那么就存入1了

如果我們要pop我們的st棧頂元素的話，那么我們的minst同樣更新最小值，那么最小值就變成上一個最小值4了

在我們的st這個棧在插入的時候我們的minst不斷進行最小元素的更新操作

但是如果我們想：如果在st中插入的好幾個數(shù)據(jù)都是重復的話那么我們的minst這個棧就顯得很麻煩了

那么我們就可以將我們的minst這個棧改造下

我們可以在minst中對存入的數(shù)據(jù)進行最小值更新的同時并且進行計數(shù)的操作

JZ31 棧的壓入、彈出序列

題目

• 1.先入棧pushi位置的數(shù)據(jù)

• 2.棧頂數(shù)據(jù)跟出棧popi序列位置數(shù)據(jù)比較，如果匹配則出棧，那么popi++，如果不匹配的話，那么我們繼續(xù)重復第一個操作

結束條件就是直到我們的棧是空的，匹配完了

class Solution {
public:/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布爾型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV){size_t pushi=0,popi=0;stack<int>st;while(pushi<pushV.size()){//我們先往st這個棧中插入pushv中pushi指向的元素，然后pushi進行加加操作st.push(pushV[pushi++]);//這個是我們?nèi)氲臄?shù)據(jù)//入完數(shù)據(jù)之后我們進行一個比較的操作while(!st.empty()&&popV[popi]==st.top()){//如果這個st這個棧不是空的并且我們的popv這個數(shù)組中i指向的元素和st中的元素是相等的話，那么我們就進行出棧操作，進了st之后又出就是這個意思popi++;//換下一個數(shù)據(jù)進行比較st.pop();//刪除當前棧的棧頂數(shù)據(jù)}}return st.empty();}
};
/*
兩個數(shù)組
1 2 3 4 5   pushi
4 3 5 1 2   popi
我們先將1進行入棧，然后與popi指向的元素進行比較，不匹配，我們繼續(xù)進行入棧
入棧了2 3 4
到了4這里，我們的pushi和篇popi指向的數(shù)據(jù)進行了匹配了
然后我們刪除了當前的這個4這個元素，我們將popi++，那么就指向了3
然后我們還是處于循環(huán)中，我們判斷的pushi和popi指向的數(shù)據(jù)是否匹配，然后此時的棧頂元素是3，匹配上了，到了然后將3刪除了
然后我們此時的棧頂元素是2，但是我們的popi指向了5，那么我們就出了循環(huán)，繼續(xù)進行入棧的操作了，將最后的5入棧了。然后我們匹配上了，將5進行刪除了
然后我們在循環(huán)之中繼續(xù)進行判斷是否匹配，我們的此時棧頂元素是2，但是我們的popi指向的元素是1，然后我們又出循環(huán)了，然后我們進行入棧操作，但是我們的pushi已經(jīng)越界了，那么就出了外循環(huán)了，然后我們的循環(huán)就終止了，然后我們判斷我們的棧是不是空的，如果是空的話那么我們就返回了true,如果不是空的話那么就返回false
*/

如果是匹配的話，那么最后棧的空間里面肯定是空的，如果不匹配的話那么肯定是不匹配的

150. 逆波蘭表達式求值

題目

class Solution {
public:int evalRPN(vector<string>& tokens){stack <int>s;for(auto &str:tokens){//如果是操作符的話if("+"==str||"-"==str||"*"==str||"/"==str){//如果遇到操作符的話我們就從棧里面拿出兩個數(shù)字進行操作符的運算操作//我們先拿出來的是右操作符，然后是左操作符int right=s.top();//拿完一個元素之后我們刪除這個棧頂元素換新的元素當棧頂元素s.pop();int left=s.top();s.pop();switch(str[0]){case '+':s.push(left+right);break;case '-':s.push(left-right);break;case '*':s.push(left*right);break;case '/':s.push(left/right);break;}}else//如果是操作數(shù)的話{s.push(stoi(str));//stoi的作用是將字符串轉換為整型，然后放到棧里面去}}return s.top();//最后保存的就是我們的結果}
};

232. 用棧實現(xiàn)隊列

題目

class MyQueue
{
private:stack<int> stackIn;stack<int> stackOut;//輔助函數(shù)，將所有元素從stackIn移動到stackOutvoid move(){while(!stackIn.empty())//In這個棧不是空的那么就進行循環(huán)操作{stackOut.push(stackIn.top());stackIn.pop();}}public:MyQueue()//構造函數(shù)不寫{}//將元素x推入隊列的末尾 ,這里我們的新元素入棧到in棧里面void push(int x){stackIn.push(x);}//移除隊列的開頭元素并返回隊列開頭元素int pop(){if(stackOut.empty())//如果out這個棧為看空的話，那么我們就將in棧的元素全部移動到out的棧里面{move();//直接利用我們上面寫的輔助函數(shù)進行操作就行了}int result=stackOut.top();stackOut.pop();return result;//返回out棧的棧頂元素}//返回隊列開頭的元素int peek(){if(stackOut.empty())//如果out棧是空的話，那么我們將in的元素全部移動到out的棧{move();}return stackOut.top();}//如果隊列是空的，返回true；否則返回falsebool empty()//兩個棧都是空的話那么這個隊列就是空的{return stackIn.empty()&&stackOut.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

225. 用隊列實現(xiàn)棧

題目

class MyStack
{
private:queue<int> queue1;queue<int> queue2;public:MyStack(){}//壓入元素到棧頂，后入先出void push(int x){queue2.push(x);//先將元素插入到隊列2中while(!queue1.empty())//只要隊列1中有數(shù)據(jù)就進行循環(huán)操作{queue2.push(queue1.front());queue1.pop();}//將兩個隊列進行交換的操作swap(queue1,queue2);}// 移除棧頂元素,棧頂元素在 queue1 的隊首，因此直接 pop 并返回該元素。int pop(){int topment=queue1.front();queue1.pop();return topment;}int top(){return queue1.front();}bool empty(){return queue1.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/