目录
前言：
1 stack的介绍和使用
1.1 stack的介绍
编辑1.2stack的使用
2 queue的介绍和使用
2.1 queue的介绍
2.2 queue的使用编辑
3 priority_queue的介绍和使用
3.1 priority_queue的介绍
3.2 priority_queue的使用
4 容器的适配器
4.1 什么是适配器
4.2 STL标准库中stack和queue的底层结构
4.3 deque的简单介绍
4.3.1 deque的原理介绍
4.3.2 deque的缺点
4.4 为什么选择deque作为stack和queue的底层默认容器
4.5 stack的模拟实现
代码如下：
注意：按需实例化
4.6 queue的模拟实现
代码如下：
4.7 priority_queue的模拟实现(没有虚函数，基础部分)
push
向上调整的代码如下：
push代码如下:
pop
向下调整的代码如下：
pop代码如下：
top
size
empty
仿函数
仿函数改良的priority_queue代码如下
练习：
结语：
前言：
在 C++ STL 中，stack、queue、priority_queue都属于容器适配器。适配器本身不存储真实数据，它不直接实现容器底层内存，而是对已有容器（deque、vector、list 等）进行封装，对外提供一套全新的接口，改变原有容器的行为语义。
stack遵循LIFO 后进先出，只允许在容器同一端完成插入与删除； queue遵循FIFO 先进先出，从尾部入队、头部出队； priority_queue为优先级队列，内部对元素做堆排序，每次取出优先级最高的元素。
本篇文档将分别讲解三种适配器的接口使用、底层实现、底层容器要求，同时模拟实现简易版stack、queue，加深对容器适配器的理解。
1 stack的介绍和使用
1.1 stack的介绍
stack是一个适配器，后进先出，结构如下图：
1.2stack的使用
重点易错点：
2 queue的介绍和使用
2.1 queue的介绍
queue也是一个适配器，先进先出，结构如下图：
2.2 queue的使用
3 priority_queue的介绍和使用
3.1 priority_queue的介绍
priority是优先的意思，priority_queue的意思是优先队列。
它的接口与stack的接口类似，
3.2 priority_queue的使用
push就是正常压入进去，这里最需要注意的是pop和top，它要选择优先级高的进行pop和top（priority_queue默认情况下是大的优先级高 默认是大堆），如果想控制小的优先级高就得用到一个叫仿函数的东西。
priority_queue的底层就是我们之前的堆，堆的底层就是数组（用来表示完全二叉树），所以priority_queue的默认适配容器是vector。
4 容器的适配器
4.1 什么是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
相当于一个转接的接口。
4.2 STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：
下图的Container是容器的意思，目的是使用这个容器来完成我需要的接口。
4.3 deque的简单介绍
deque虽然叫双端队列，但其实deque跟queue没有关系，队列要求先进先出，deque不要求先进先出，我们可以把deque当成vector和list的缝合怪。
4.3.1 deque的原理介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
因为vector与list的优缺点过于明显，这是为什么产生deque的原因。
从上图可以看出deque使用的是随机迭代器， 我们从这就可以看出deque是个缝合怪，既支持下标访问，又支持头插头删，相当于list与vector的结合体。
我们先回顾一下list与vector的结构，vector是一段连续的空间，list是一个一个节点作为空间，也就是很多小空间，然后通过指针连接在一起。
deque为了解决vector频繁扩容的问题，采取的操作是开辟一块连续空间，如果连续空间满了，就开辟下一块同样大小的空间，不扩容，直接开辟新空间，也就是这样。
这些空间连接deque是运用中控数组来实现，就是deque有一个中控数组，中控数组里面存的是指针，指向的就是对应空间，然后一开始的空间都会尽量往中控数组的中间位置靠，如下图：
头插与尾插如下图：
当然，这个也会要扩容，只是不会像vector一样拷贝的那么多，如果中控数组满了，就会扩容出一个更大的中控数组，然后把指针拷贝过去。
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
deque的迭代器里面有四个成员，first，last指向buf空间的开始和结束，cur指向的是想要访问的数据，node 指向的是中控数组当前指向该buf空间的指针的位置，用图表示的话就是如下图：
4.3.2 deque的缺点
与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
4.4 为什么选择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的优点，而完美的避开了其缺
陷
template<class T, class Container = deque<T>>
class stack
{
public :
stack() {}
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;
};
4.5 stack的模拟实现
stack非常简单，接口一样简单，如下图：
代码如下：
#pragma once
namespace wxd
{
template<class T, class container=vector<T>>
class my_stack
{
public:
void push(const T& value)
{
_con.push_back(value);
}
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;
};
}
但我们学完适配器后其实完全不用这么写，因为stack这个东西完全可以用vector来进行封装转换，因为栈主要支持的就三个东西，一个入栈，一个出栈，一个查询栈顶元素，那入栈不就对应vector的尾插，出栈不就对应vector的尾删，查询栈顶元素不就是查询vector内部最后一个元素
注意：按需实例化
请观看下面的代码
#pragma once
namespace wxd
{
template<class T, class container=vector<T>>
class my_stack
{
public:
void push(const T& value)
{
_con.push_back(value);
}
void pop()
{
_con.pop_front();
}
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;
};
}
#include<iostream>
#include<vector>
#include<list>
using namespace std;
#include"stack.h"
#include"PriorityQueue.h"
#include"queue.h"
#include"my_stack.h"
int main()
{
//w::stack<int, vector<int>> st;
wxd::my_stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
cout << st.size() << endl;
return 0;
}
我使用的pop是pop_front，这个接口在vector中是不存在的，但是编译器没有报错，这是为什么？
因为我们没有调用pop这个接口，没调用的函数，编译器不会实例化，只会检查大体有没有问题。
所以有的时候，模板实现一直没问题，突然有一次调用出问题了，很可能就是这个接口之前一直没有使用过，然后这个接口内部有点问题，所以写完代码与接口时需要及时检查与调用。
4.6 queue的模拟实现
queue的实现是非常简单的，与stack类似，它的接口是非常简单的，如下：
代码如下：
#pragma once
#include<deque>
namespace wxd
{
template<class T,class container =deque<T>>
class my_queue
{
public:
void push(const T& value)
{
_con.push_back(value);
}
void pop()
{
_con.pop_front();
}
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
const T& back()const
{
return _con.back();
}
const T& front()const
{
return _con.front();
}
size_t size()const
{
return _con.size();
}
bool empty()const
{
return _con.empty();
}
private:
container _con;
};
}
需要注意的是，队列而言就不能用vector了，因为队列是一端进一端出，如果用vector，出队列的时间复杂度是O（N）了。
我们如果用vector来作为Container，一开始不会报错，直到我们调用pop才会报错，因为vector是没有pop_front这个操作的，这也体现了 前面我们所讲的按需实例化问题。
4.7 priority_queue的模拟实现(没有虚函数，基础部分)
在模拟实现前，我们应该回顾一下二叉树，了解一下parent与child的关系，关系如下：
parent=(child-1)/2;
left_child=parent*2+1;
right_child=parent*2+2;
我们在使用priority_queue的时候，将其看作一个完全二叉树，然后进行操作。
push
如上图，我们将数据插入进去，需要对这个完全二叉树进行向上调整，不然无法实现priority_queue的接口，它的接口会产生错误。
向上调整的代码如下：
//建堆 向上调整
void AdjustUp(int child)
{
size_t parent = (child – 1) / 2;
while (child > 0)
{
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child-1)/2;
}
else
{
break;
}
}
}
如果这个二叉树中没有元素，上面代码也相当于建堆。
我们进行push完就要调用上面的AdjustUp进行建堆或者向上调整，不然调用top接口或者调用pop接口会出现错误的值。
push代码如下:
void push(const T& x)
{
_con.push_back(x);
return AdjustUp(_con.size() – 1);
}
pop
删除必须要把堆顶元素和最后一个元素交换，然后对vector——pop_back，随后再对堆顶元素向下调整，重新调整为堆结构 ，如果直接将顶部元素删除，二叉树的parent与child的关系会发生大变化，兄弟变父子，叔侄变兄弟。
向下调整的代码如下：
//向下调整
void AdjustDown(int parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child + 1] > _con[child])child++;
if (_con[child] > _con[parent])
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
pop代码如下：
void pop()
{
//防止关系混乱，所以需要删除的数与尾部的数交换
swap(_con[0], _con[_con.size() – 1]);
_con.pop_back();
AdjustDown(0);
}
top
const T& top()
{
return _con[0];
}
size
size_t size()const
{
return _con.size();
}
empty
bool empty()const
{
return _con.empty();
}
仿函数
首先，仿函数是一个类，这个类里面有()运算符重载（函数调用运算符重载），为什么叫仿函数，因为它使用起来像函数，长得与函数很像。
如下图，这是一个基础的仿函数：
#include <iostream>
// 仿函数类
struct Add {
int operator()(int a, int b) {
return a + b;
}
};
int main() {
Add f;
// f是对象，但像函数一样调用，这就是仿函数
std::cout << f(3,5); //输出8
return 0;
}
类内如果没有成员变量的时候，类的大小为1，仿函数就普遍是这种情况，因为一般仿函数对应的类的内部基本就是只有一个operator()的重载。
仿函数改良的priority_queue代码如下
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 bit
{
// 默认是大堆
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
void AdjustUp(int child)
{
Compare com;
int parent = (child – 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if(com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child – 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() – 1);
}
void AdjustDown(int parent)
{
// 先假设左孩子小
size_t child = parent * 2 + 1;
Compare com;
while (child < _con.size()) // child >= n说明孩子不存在，调整到叶子了
{
// 找出小的那个孩子
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
++child;
}
//if (_con[parent] < _con[child])
if (com(_con[parent],_con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con[_con.size() – 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()
{
return _con[0];
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
练习：
102. 二叉树的层序遍历 – 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector <vector <int>> ret;
if (!root) {
return ret;
}
queue <TreeNode*> q;
q.push(root);
while (!q.empty()) {
int currentLevelSize = q.size();
ret.push_back(vector <int> ());
for (int i = 1; i <= currentLevelSize; ++i) {
auto node = q.front(); q.pop();
ret.back().push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ret;
}
};
作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/241885/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
155. 最小栈 – 力扣（LeetCode）
class MinStack {
public:
void push(int value) {
_st.push(value);
if(minst.empty()||value<=minst.top())minst.push(value);
}
void pop() {
if(_st.top()==minst.top()){
minst.pop();
}
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return minst.top();
}
private:
stack<int> _st;
stack<int> minst;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(value);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
栈的压入、弹出序列_牛客题霸_牛客网
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型vector
* @param popV int整型vector
* @return bool布尔型
*/
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
// write code here
stack<int>_st;
size_t i=0;
for (auto& e : pushV) {
_st.push(e);
while(!_st.empty()&&_st.top()==popV[i]){
_st.pop();
i++;
}
}
return _st.empty();
}
};
结语：
谢谢你的观看，希望可以给你提供帮助！！！
