?个人主页：落叶
?当前专栏: C++专栏
目录
stack的介绍和使用
stack的介绍
stack的使用
【stack】构造空的栈
【empty】检测stack栈是否为空
【size】返回stack栈中元素的个数
【top】返回栈顶元素的引用
【push】将元素val压入stack中
【pop】将stack中尾部的元素弹出
栈的OJ题目
最小栈
栈的压入、弹出序列
逆波兰表达式求值
用2个栈实现队列
stack的模拟实现
stack.h
test.cpp
queue的介绍和使用
queue的介绍
queue的使用
【queue()】构造空队列
【empty()】检测队列是否为空，是返回true，否则返回false
用队列实现栈
queue的模拟实现
queue.h
test.cpp
priority_queue的介绍和使用
priority_queue的介绍
priority_queue的使用
构造一个空的优先级队列
【empty】检测优先级队列是否为空，是返回true，否 则返回false
【top】返回优先级队列中最大(最小元素)，即堆顶元 素
【push】在优先级队列中插入元素x
【pop】删除优先级队列中最大(最小)元素，即堆顶元 素
priority_queue在OJ中的使用
priority_queue的模拟实现
priority_queue.h
test.cpp
容器适配器
什么是适配器
STL标准库中stack和queue的底层结构
deque的简单介绍(了解)
deque的原理介绍
deque的缺陷
为什么选择deque作为stack和queue的底层默认容器
STL标准库中对于stack和queue的模拟实现
stack的模拟实现
queue的模拟实现
stack的介绍和使用
stack的介绍
stack底层就是一个栈
stack的使用
| 函数说明 | 接口说明 |
| stack() | 构造空的栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
【stack】构造空的栈
stack<int> s1;【empty】检测stack栈是否为空
下面，栈为空，返回的就是true就是1，如果有元素入栈，那就是不为空，返回false就是0.
【size】返回stack栈中元素的个数
下面，入栈了1~4，元素个数就是4.
【top】返回栈顶元素的引用
返回的是引用，最好用引用来接收。
下面，栈顶是4。
【push】将元素val压入stack中
下面，把1~4都压入栈了
【pop】将stack中尾部的元素弹出
1~4压入栈中。
判断栈不为空进循环。
打印完栈顶，然后出栈。
栈的OJ题目
最小栈
需要一个栈和一个辅助栈。
把小的元素，往辅助栈入。
构造用默认的进行了
1.辅助栈为空，主栈入栈，辅助栈也要入栈。
2.辅助栈不为空，val的数值小于辅助栈的栈顶，辅助栈入栈。
出栈st和mak的栈顶相同，就一起出栈
取栈顶这个就取主栈的。
getMin这个就是返回最小值，取辅助栈的栈顶。
class MinStack {public: MinStack() { } void push(int val) { //插入到st栈 st.push(val); //mak空栈 || val 小于 mak栈顶 if(mak.empty() || val <= mak.top()) { //插入到mak栈 mak.push(val); } } void pop() { //st和mak栈顶相同---一起出栈 if(st.top() == mak.top()) { mak.pop(); } st.pop(); } int top() { return st.top(); } int getMin() { //mak栈顶就是最小的数值了 return mak.top(); }private: stack<int> st; stack<int> mak;};栈的压入、弹出序列
class Solution {public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型 */ bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { // write code here size_t pushi = 0,popi = 0; //栈用来存放pushV的数据 stack<int> st; while(pushi < pushV.size()) { //把pushV入栈 st.push(pushV[pushi++]); //st不能为空 && st栈顶等于popV[popi] while(!st.empty() && st.top() == popV[popi]) { popi++; //等于就出栈 st.pop(); } } //栈里没有数据了，就说明所有数字都相等，返回true return st.empty(); }};逆波兰表达式求值
class Solution {public: int evalRPN(vector<string>& tokens) { stack<int> s1; for(auto& e:tokens) { if("+" == e || "-"== e||"*"== e|| "/"== e) { //操作符 //取栈顶的2个元素 int right = s1.top(); s1.pop(); int left = s1.top(); s1.pop(); //进行运算 switch(e[0]) { case '+': s1.push(left + right); break; case '-'://必须用后面的运算结果-去前面的数值 s1.push(left - right); break; case '*': s1.push(left * right); break; case '/': s1.push(left / right); break; } } else { //不是操作符入栈 s1.push(stoi(e)); } } return s1.top(); }};用2个栈实现队列
class MyQueue {public: MyQueue() { }// 入队操作：将元素 x 添加到队列尾部 void push(int x) { // 将元素 x 压入栈 st 中 // 由于栈是后进先出（LIFO），所以新元素会位于栈顶 st.push(x); } // 出队操作：移除并返回队列头部的元素 int pop() { // 如果 mak 栈为空，需要将 st 中的元素全部转移到 mak 中 if (mak.empty()) { add(); // 调用辅助函数将 st 中的元素转移到 mak 中 } // 现在 mak 的栈顶元素就是队列头部的元素 int x = mak.top(); // 获取队列头部的元素 mak.pop(); // 移除 mak 栈顶元素，相当于移除队列头部元素 return x; // 返回队列头部的元素 } // 查看队列头部的元素（不移除） int peek() { // 如果 mak 栈为空，需要将 st 中的元素全部转移到 mak 中 if (mak.empty()) { add(); // 调用辅助函数将 st 中的元素转移到 mak 中 } // 返回 mak 栈顶元素，即队列头部的元素 return mak.top(); } // 检查队列是否为空 bool empty() { // 队列为空当且仅当两个栈都为空 return st.empty() && mak.empty(); }private: // 辅助函数：将 st 中的所有元素转移到 mak 中 void add() { // 当 st 不为空时，持续将 st 的栈顶元素压入 mak 中 while (!st.empty()) { mak.push(st.top()); // 将 st 的栈顶元素压入 mak 中 st.pop(); // 移除 st 的栈顶元素 } } stack<int> st; stack<int> mak;};stack的模拟实现
从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。
stack.h
#pragma once#include<iostream>#include<vector>//模拟实现栈using namespace std;namespace bit{template<class T, class container = vector<T>>class stack{public://尾插void push(const T& x){//直接调用vectit的尾插就行了_con.push_back(x);}//出栈-直接调用vectit的尾删void pop(){_con.pop_back();}//取栈顶-直接调用通用的接口 bakcT& top(){return _con.back();}const T& top()const{return _con.back();}//有效个数size_t size(){return _con.size();}//判断是否为空bool empty(){return _con.empty();}private://vectit-listcontainer _con;};}test.cpp
#include<iostream>#include"stack.h"int main(){//bit::queue<int> st;bit::stack<int, list<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);cout << "size:" << st.size() << endl;while (!st.empty()){cout << st.top() << endl;st.pop();}}queue的介绍和使用
queue的介绍
1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元 素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供 一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少 支持以下操作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器 类，则使用标准容器deque。
queue的使用
| 函数声明 | 接口说明 |
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空，是返回true，否则返回false |
| push() | 在队尾将元素val入队列 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| size() | 返回队列中有效元素的个数 |
| pop() | 将队头元素出队列 |
【queue()】构造空队列
queue<int> q1;【empty()】检测队列是否为空，是返回true，否则返回false
是空返回true就是1，不是空返回false就是0
【push】在队尾将元素val入队列
下面将1~4都入队列了。
【front】返回队头元素的引用
下面，我们可以看到队头是1
【pop】将队头元素出队列
1~4入队列，不为空进循环，打印队头数值，然后出队列，出队列就是从队头的位置出。
【back】返回队尾元素的引用
如果想获取队尾的数据可以使用back
【size】返回队列中有效元素的个数
我们可以看到，有效元素就是4
用队列实现栈
class MyStack {public:// 两个队列： // queue1 用于存储栈的元素 // queue2 作为辅助队列，在 push 操作中用于重新排列元素 queue<int> queue1; queue<int> queue2; /** Initialize your data structure here. */ MyStack() { } // 入栈操作：将元素 x 压入栈顶 void push(int x) { // 将新元素 x 压入辅助队列 queue2 中 queue2.push(x); // 将 queue1 中的所有元素依次出队并压入 queue2 中 // 这样，queue2 中的元素顺序将被反转，模拟栈的 LIFO 特性 while (!queue1.empty()) { queue2.push(queue1.front()); // 将 queue1 的队首元素压入 queue2 queue1.pop(); // 移除 queue1 的队首元素 } // 交换 queue1 和 queue2，使得 queue1 始终存储栈的元素 swap(queue1, queue2); } // 出栈操作：移除并返回栈顶的元素 int pop() { // 检查 queue1 是否为空 if (queue1.empty()) { // 如果 queue1 为空，说明栈中没有元素，抛出异常或处理错误 throw std::out_of_range("Stack is empty"); } // 获取 queue1 的队首元素，即栈顶元素 int r = queue1.front(); queue1.pop(); // 移除 queue1 的队首元素，相当于移除栈顶元素 return r; // 返回栈顶元素 } // 获取栈顶元素 int top() { // 检查 queue1 是否为空 if (queue1.empty()) { // 如果 queue1 为空，说明栈中没有元素，抛出异常或处理错误 throw std::out_of_range("Stack is empty"); } // 返回 queue1 的队首元素，即栈顶元素 return queue1.front(); } // 检查栈是否为空 bool empty() { // 栈为空当且仅当 queue1 为空 return queue1.empty(); }};queue的模拟实现
因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实 现queue，具体如下：
queue.h
#pragma once#include<iostream>#include<list>#include<vector>using namespace std;namespace bit{ // 使用命名空间 bit 封装自定义队列类 // 泛型队列类模板 // T: 队列中元素的类型 // container: 用于存储队列元素的容器类型，默认为 std::list<T> template<class T, class container = std::list<T>> class queue { public: // 构造函数 queue() { // 默认构造函数，不需要初始化，因为容器默认构造 } // 入队列操作：将元素 x 添加到队列尾部 void push(const T& x) { _con.push_back(x); // 使用容器的 push_back 方法将元素添加到尾部 } // 出队列操作：移除队列头部的元素 void pop() { _con.pop_front(); // 使用容器的 pop_front 方法移除头部元素 } // 获取队列尾部的元素（引用） T& back() { return _con.back(); // 使用容器的 back 方法获取尾部元素 } // 获取队列尾部的元素（常量引用） const T& back() const { return _con.back(); // 常量版本，用于常量对象 } // 获取队列头部的元素（引用） T& front() { return _con.front(); // 使用容器的 front 方法获取头部元素 } // 获取队列头部的元素（常量引用） const T& front() const { return _con.front(); // 常量版本，用于常量对象 } // 获取队列中有效元素的个数 size_t size() { return _con.size(); // 使用容器的 size 方法获取元素个数 } // 检查队列是否为空 bool empty() { return _con.empty(); // 使用容器的 empty 方法检查是否为空 } private: // 私有成员变量：用于存储队列元素的容器 container _con; };}test.cpp
#include <iostream> #include "queue.h" int main() { // 创建一个 bit::queue<int> 类型的队列对象 st，用于存储整数类型的元素 bit::queue<int> st; // 入队操作：将整数 1, 2, 3, 4 依次压入队列 st 中 st.push(1); st.push(2); st.push(3); st.push(4); // 输出队列的大小，即当前队列中元素的数量 std::cout << "size:" << st.size() << std::endl; // 输出: size:4 // 循环遍历队列，直到队列为空 while (!st.empty()) { // 输出队列头部的元素（最先进入队列的元素） std::cout << st.front() << std::endl; // 依次输出: 1, 2, 3, 4 // 出队操作：移除队列头部的元素 st.pop(); } return 0; }priority_queue的介绍和使用
priority_queue的介绍
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素 中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶 部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的 顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过 随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue 类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用 算法函数make_heap、push_heap和pop_heap来自动完成此操作。
priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中 元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下priority_queue是大堆。
| 函数声明 | 接口说明 |
| priority_queue()/priority_queue(first, last) | 构造一个空的优先级队列 |
| empty( ) | 检测优先级队列是否为空，是返回true，否 则返回false |
| top( ) | 返回优先级队列中最大(最小元素)，即堆顶元 素 |
| push(x) | 在优先级队列中插入元素x |
| pop() | 删除优先级队列中最大(最小)元素，即堆顶元 素 |
构造一个空的优先级队列
【empty】检测优先级队列是否为空，是返回true，否 则返回false
优先级队列是空返回true就是1，不是空返回false就是0；
【top】返回优先级队列中最大(最小元素)，即堆顶元 素
priority_queue默认是大堆，使用我们取队顶就是5.
如果想要priority_queue变成大堆就要在priority_queue第三个参数传个greater<int>，
greater<int>是仿函数是一个大于的比较，less<int>是一个小于的比较，默认的就是这个。
//小于比较的仿函数template<class T>class less{public:bool operator(){return x < y;}};//大于比较的仿函数template<class T>class greater{public:bool operator(){return x > y;}};这样我们取到的堆顶就是1了。
【push】在优先级队列中插入元素x
这个就是将1~5插入优先级队列中。
【pop】删除优先级队列中最大(最小)元素，即堆顶元 素
插入1~5的元素，通过循环打印堆顶，删除堆顶元素。
小堆
【注意】
1. 默认情况下，priority_queue是大堆。
#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; }2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重 载。
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){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}private:int _year;int _month;int _day;};void TestPriorityQueue(){// 大堆，需要用户在自定义类型中提供<的重载priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;// 如果要创建小堆，需要用户提供>的重载priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout << q2.top() << endl;}priority_queue在OJ中的使用
class Solution {public: int findKthLargest(vector<int>& nums, int k) { // 将数组中的元素先放入优先级队列中 priority_queue<int> p(nums.begin(),nums.end()); // 将优先级队列中前k-1个元素删除掉 while(--k) { p.pop(); } return p.top(); }};priority_queue的模拟实现
通过对priority_queue的底层结构就是堆，因此此处只需对对进行通用的封装即可。
priority_queue.h
#pragma once#include<iostream>#include<queue>using namespace std;namespace bit{//仿函数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){return x > y;}};template<class T, class container = vector<T>,class compare = greater<T>>class priority_queue{public://强制生成默认构造priority_queue() = default;//迭代器区间template<class InputIterator>priority_queue(InputIterator a1, InputIterator a2):_con(a1,a2){for (int i = (_con.size()-1-1)/2; i >= 0 ; i--){ //向上调整upwards(i);}}//向上调整算法void upwards(int node){//计算出父亲节点int sz = (node - 1) / 2;while (node > 0){compare com;//比较，孩子节点大于父亲节点if (com(_con[node] , _con[sz])){//交换swap(_con[node], _con[sz]);//父亲节点给nodenode = sz;//找出新的父亲节点sz = (sz - 1) / 2;}else{break;}}}//入堆void push(const T& x){_con.push_back(x);//向上调整算法upwards(_con.size() - 1);}//向下调整算法void downwards(int node){compare com;//计算出左孩子节点int sz = (node * 2) + 1;while (sz < _con.size()){//判断左孩子和右孩子那个大if (sz+1 < _con.size() && com(_con[sz + 1] ,_con[sz])){sz++;}if (com(_con[sz] , _con[node])){//交换swap(_con[sz], _con[node]);//孩子节点给nodenode = sz;//计算下一个左孩子节点sz = (node * 2) + 1;}else{break;}}}//删除堆顶数据void pop(){//堆顶和堆的最后一个元素交换swap(_con[0], _con[_con.size() - 1]);//删除堆的最后一个元素_con.pop_back();//向下调整算法downwards(0);}size_t size(){return _con.size();}const T& top()//取堆顶数据{return _con[0];}bool empty()//判空{return _con.empty();}private:container _con;};}test.cpp
#include"priority_queue.h"int main(){//bit::priority_queue<int> pq;bit::priority_queue<int, vector<int>, greater<int>> pq;pq.push(1);pq.push(2);pq.push(3);pq.push(4);pq.push(5);while (!pq.empty()){cout << pq.top() << endl;pq.pop();}return 0;}容器适配器
什么是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设 计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为 容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认 使用deque，比如：
deque的简单介绍(了解)
deque的原理介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端 进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个 动态的二维数组，其底层结构如下图所示：
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问 的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
那deque是如何借助其迭代器维护其假想连续的结构呢？
deque的缺陷
与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩 容时，也不需要搬移大量的元素，因此其效率是必比vector高的。 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。 但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实 际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看 到的一个应用就是，STL用其作为stack和queue的底层数据结构。
为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性 结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据 结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如 list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进 行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的 元素增长时，deque不仅效率高，而且内存使用率高。
结合了deque的优点，而完美的避开了其缺陷。
STL标准库中对于stack和queue的模拟实现
stack的模拟实现
#include<deque>namespace bite{template<class T, class Con = deque<T>>//template<class T, class Con = vector<T>>//template<class T, class Con = list<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:Con _c;};}queue的模拟实现
#include<deque>#include <list>namespace bite{template<class T, class Con = deque<T>>//template<class T, class Con = list<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:Con _c;};}