深入理解C++系列（11）——stack、queue和priority

文章目录

- 上期回顾
stack和queue的使用和相关接口
- 1.1. stack 的本质
- 1.2. stack 的常用接口
- 1.3，stack相关算法题
- - 最小栈⭐⭐
  - - 题目链接
    - 题目描述
    - 解题思路
    - 解题代码
    - 大神解题代码
  - 栈的压入、弹出序列⭐⭐
  - - 题目链接
    - 题目描述
    - 解题思路
    - 解题代码
    - 大神解题代码
  - 逆波兰表达式求值⭐⭐
  - - 题目链接
    - 题目描述
    - 解题思路
    - 解题代码
    - 大神解题代码
- 2.1. queue 的本质
- 2.2. queue 的常用接口
- 2.3，相关经典算法题
- - 二叉树的层序遍历⭐⭐⭐
  - - 题目链接
    - 题目描述
    - 解题思路
    - 解题代码
    - 大神解题代码
stack和queue的底层实现
- 容器适配器
- vector 和 list 优缺点总结
- - vector
  - list
- deque 双端队列（了解即可，但必须要了解）
- - 1 deque的原理介绍
  - 2， deque的迭代器设计
  - - 1、deque 迭代器包含四部分
  - 3,deque的缺陷——不适合遍历
  - 4，为什么选择deque作为stack和queue的底层默认容器
priority_queue优先级队列
- 1，介绍+使用
- - 1，接口
  - 2，堆相关算法（就是不用，了解即可）
- 2，优先级队列的底层实现
- 仿函数
- - 写法
- 什么时候要自己写仿函数呢？
总结与复习
三、总结与回顾
- 一、容器适配器
- 二、为什么默认底层容器不同？
- 三、deque 为什么适合作为 stack 和 queue 的底层？
- 四、priority_queue 本质
- 五、仿函数（重点）
- 六、什么时候需要自己写仿函数？
- 下期预告
- 模版进阶
- 结语

◆ 博主： @此生决int

分享编程知识！深挖底层原理！持续原创更新！

热门专栏：深入理解 C++系列|算法系列快速复习系列 |Java 速通系列

📌 本系列知识点前后关联较强，建议按照专栏顺序阅读哦

本系列主要面向的阅读人群

1，学完 C 语言，准备系统学习 C++ 的同学

2，已经学习过 C++，希望重新梳理知识体系的同学

3，想深入理解 C++ 设计思想与底层原理，而不仅仅停留在语法层面的同学

—

上期回顾

list——链表

stack和queue的使用和相关接口

1.1. stack 的本质

stack 是一种：后进先出（LIFO）的线性结构。在这里插入图片描述

1.2. stack 的常用接口

接口作用

stack()	构造空栈
empty()	判断是否为空
size()	返回元素个数
top()	返回栈顶元素引用
push()	压栈
pop()	弹栈
因为我们之前在数据结构部分已经学习过了，所以，这里就不再赘述了！

1.3，stack相关算法题

最小栈⭐⭐

题目链接

最小栈

题目描述

设计一个支持 push、pop、top 操作，并能在 O(1) 时间内获取栈中最小元素的栈。在这里插入图片描述

解题思路

使用两个栈维护数据。一个栈正常存储所有元素，另一个栈专门维护当前最小值。当插入的新元素小于等于当前最小值时，将其压入最小栈；弹出元素时，如果弹出的正是当前最小值，则最小栈同步弹出即可。

解题代码

class MinStack {
public:
MinStack() {

}

void push(int value) {

// 当前元素不大于最小值时，同时进入最小栈
if (minst.empty() || value <= minst.top())
{
minst.push(value);
}

st.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; // 最小栈，维护当前最小值
};

没懂？看看大神的解题代码！！

大神解题代码

class MinStack {
public:
MinStack() {

}

void push(int val) {

st.push(val);

// minSt 的栈顶始终对应当前最小值
if (minSt.empty())
minSt.push(val);
else
minSt.push(min(val, minSt.top()));
}

void pop() {

st.pop();
minSt.pop();
}

int top() {

return st.top();
}

int getMin() {

return minSt.top();
}

private:
stack<int> st;
stack<int> minSt;
};

栈的压入、弹出序列⭐⭐

题目链接

栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，判断第二个序列是否可能是该栈的弹出顺序。假设压入栈的所有数字均不相等。在这里插入图片描述

解题思路

利用栈模拟整个压栈、出栈过程。依次将压栈序列入栈，每次入栈后，只要栈顶元素等于当前待弹出的元素，就不断弹栈。最后若弹出序列全部匹配，则说明该弹出序列合法。

解题代码

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param pushV int整型vector
* @param popV int整型vector
* @return bool布尔型
*/
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {

// 模拟压栈、出栈过程
int i = 0, j = 0;
stack<int> st;

while (i < pushV.size())
{
// 当前元素入栈
st.push(pushV[i]);

// 只要栈顶等于当前待弹出的元素，就持续出栈
while (!st.empty() && st.top() == popV[j])
{
st.pop();
j++;
}

i++;
}

// 所有元素都成功匹配，则说明弹出序列合法
return j == popV.size();
}
};

没懂？看看大神的解题代码！！

大神解题代码

class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {

stack<int> st;
int j = 0;

for (int x : pushV)
{
// 模拟入栈
st.push(x);

// 能出栈就一直出栈
while (!st.empty() && st.top() == popV[j])
{
st.pop();
j++;
}
}

// 栈为空说明所有元素都已正确匹配
return st.empty();
}
};

逆波兰表达式求值⭐⭐

题目链接

逆波兰表达式求值

题目描述

根据逆波兰表达式（后缀表达式）计算表达式的值。运算符仅包含 +、-、*、/，保证表达式合法。

在这里插入图片描述

解题思路

利用栈模拟计算过程。遇到数字直接入栈，遇到运算符则弹出栈顶两个元素进行运算，再将结果压回栈中，最终栈顶元素就是答案。

解题代码

class Solution {
public:
int evalRPN(vector<string>& tokens) {

stack<int> st;

for (auto& it : tokens)
{
// ：&& 优先级高于 ||，应加括号保证整体判断正确
if (st.size() >= 2 &&
(it == "+" || it == "-" || it == "*" || it == "/"))
{
// 注意先弹出的是第二个操作数
int b = st.top();
st.pop();

int a = st.top();
st.pop();

int ret = 0;
char ch = it[0];

switch (ch)
{
case '+':
ret = a + b;
break;
case '-':
ret = a – b;
break;
case '*':
ret = a * b;
break;
case '/':
ret = a / b;
break;
}

st.push(ret);
}
else
{
// 数字直接入栈
st.push(stoi(it));
}
}

return st.top();
}
};

没懂？看看大神的解题代码！！

大神解题代码

class Solution {
public:
int evalRPN(vector<string>& tokens) {

stack<int> st;

for (auto& s : tokens)
{
// 数字直接入栈
if (s != "+" && s != "-" && s != "*" && s != "/")
{
st.push(stoi(s));
}
else
{
// 注意出栈顺序：先右操作数，再左操作数
int b = st.top();
st.pop();

int a = st.top();
st.pop();

if (s == "+") st.push(a + b);
else if (s == "-") st.push(a – b);
else if (s == "*") st.push(a * b);
else st.push(a / b);
}
}

return st.top();
}
};

2.1. queue 的本质

queue 是一种：先进先出（FIFO）的线性结构。

在这里插入图片描述

2.2. queue 的常用接口

接口作用

queue()	构造空队列
empty()	判断是否为空
size()	返回元素个数
front()	返回队头元素引用
back()	返回队尾元素引用
push()	在队尾入队
pop()	在队头出队

2.3，相关经典算法题

二叉树的层序遍历⭐⭐⭐

题目链接

二叉树的层序遍历

题目描述

给你二叉树的根节点 root，返回其节点值的层序遍历结果，即逐层从左到右访问所有节点。

在这里插入图片描述

解题思路

利用队列实现 BFS。每次记录当前队列中的节点个数，这些节点正好是一层，依次取出并将其左右孩子加入队列，同时保存下一层节点的值，直到队列为空。

解题代码

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right)
* : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 一层不是一个父节点的孩子，而是队列中当前所有节点的孩子。
vector<vector<int>> levelOrder(TreeNode* root) {

if (root == nullptr)
return {};

vector<vector<int>> ret;
queue<TreeNode*> q;

q.push(root);

// 第一层只有根节点
ret.push_back({root->val});

while (!q.empty())
{
vector<int> a;

// 当前队列中的所有节点就是同一层
size_t _size = q.size();

while (_size—)
{
TreeNode* tmp = q.front();

// 下一层左孩子
if (tmp->left)
{
q.push(tmp->left);
a.push_back(tmp->left->val);
}

// 下一层右孩子
if (tmp->right)
{
q.push(tmp->right);
a.push_back(tmp->right->val);
}

q.pop();
}

// 下一层存在节点才加入答案
if (!a.empty())
ret.push_back(a);
}

return ret;
}
};

没懂？看看大神的解题代码！！

大神解题代码

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {

if (root == nullptr)
return {};

vector<vector<int>> ret;
queue<TreeNode*> q;
q.push(root);

while (!q.empty())
{
int sz = q.size();
vector<int> level;

// 一次处理一整层
while (sz—)
{
TreeNode* cur = q.front();
q.pop();

// 当前层节点加入答案
level.push_back(cur->val);

// 左右孩子进入下一层
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}

ret.push_back(level);
}

return ret;
}
};

stack和queue的底层实现

容器适配器

由于stack和queue的特性，我们其实只需要对像vector和list等容器规定只能尾插尾删就可以实现stack，我们数据结构里面也是这么做的，所以，我们想到可以直接这样来实现栈

template<class T>
class stack
{
public:
void push(const T& x)
{
v.push_back(x);
}
void pop()
{
v.pop_back();
}
......
private:
vector v;
};

这里的vector呢也可以换成list等等，进而，我们可以加入模版

template<class T, class Container >
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top() const
{
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};

同理，我们也可以实现队列

template<class T, class Container >
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}

void pop()
{
_con.pop_front();
}

const T& front() const
{
return _con.front();
}

const T& back() const
{
return _con.back();
}

size_t size() const
{
return _con.size();
}

bool empty() const
{
return _con.empty();
}

private:
Container _con;
};

我们可以在这里给上缺省参数：

template<class T, class Container=vector<T>>

这里， vector和list都可以，但是你会发现库里面给的是 template<class T, class Container =deque<T>> deque双端队列！！vector和list的缝合怪好，再了解deque之前，我们先来总结一下vector和list他们各自的优缺点！

vector 和 list 优缺点总结

vector

由于vector是连续存储，空间连续

优点缺点

✅ 支持随机访问（O(1)）	❌ 中间或头部插入、删除效率低（O(n)）
✅ 尾插、尾删效率高（均摊 O(1)）	❌ 扩容需要重新申请空间，导致迭代器失效
✅ CPU 缓存命中率高，遍历速度快	–

list

优点缺点

✅ 任意位置插入、删除效率高（已知位置为 O(1)）	❌ 不支持随机访问，只能顺序遍历（O(n)）
✅ 不需要连续空间，不会整体扩容	❌ 每个节点额外存储两个指针，空间开销大
✅ 插入、删除不会导致其他节点迭代器失效（被删除节点除外）	❌ 缓存命中率低，遍历速度慢

那么，我们可不可以把他们的优缺点都结合起来形成一个新的结构呢？可以——deque双端队列！

deque 双端队列（了解即可，但必须要了解）

1 deque的原理介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。在这里插入图片描述

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：在这里插入图片描述

2， deque的迭代器设计

在这里插入图片描述

1、deque 迭代器包含四部分

由上图可以看出：STL 中 deque 的迭代器一般包含四个成员：

成员含义

first	当前 Buffer 的起始位置
last	当前 Buffer 的结束位置（尾后位置）
cur	当前元素位置
node	当前 Buffer 在中控数组中的位置

那deque是如何借助其迭代器维护其假想连续的结构呢？在这里插入图片描述总之，数据一般存在中控数组的中间，如果头插，就在中控数组的左边（前面）新增一个数组，尾插就是直接在中控数组的右边（后面）新增一个数组，每次都是新增一个buff数组，不需要频繁的扩容！注意：deque的尾插尾删，头插头删都非常厉害，[]的效率略低于vector，但是，他的insert和erase非常非常慢！但一般也不会用！

3,deque的缺陷——不适合遍历

deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。但是，他作为stack和queue的底层数据结构刚刚好，十分合适！！！

4，为什么选择deque作为stack和queue的底层默认容器

stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高
stack只需要尾插尾删，queue只需要尾插头删，都不需要遍历

priority_queue优先级队列

1，介绍+使用

优先级队列就是我们学习过的——堆，默认是大堆！堆——完全二叉树，底层是数组！他和stack和queue一样，是容器适配器！标准容器类vector和deque满足这些需求。但是vector的【】的效率更高，所以，默认是vector、

1，接口

函数声明接口说明

priority_queue() / priority_queue(first, last)	构造一个空的优先级队列，或使用区间 [first, last) 中的元素构造优先级队列
empty()	检测优先级队列是否为空
top()	返回堆顶元素
push(x)	插入元素 x
pop()	删除堆顶元素
同时，库里面还提供了一些与堆相关的算法：

2，堆相关算法（就是不用，了解即可）

在这里插入图片描述

堆算法接口说明

make_heap(first, last)	将区间 [first, last) 中的元素构造成一个堆（默认大堆）
push_heap(first, last)	将区间最后一个元素插入到堆中，并重新调整为堆结构
pop_heap(first, last)	将堆顶元素移动到区间末尾，并重新调整剩余元素为堆结构（注意：不会真正删除元素）
sort_heap(first, last)	对堆进行排序，最终得到升序序列（默认大堆）
is_heap(first, last)	判断指定区间是否满足堆结构，满足返回 true，否则返回 false
is_heap_until(first, last)	返回区间中第一个不满足堆性质的位置，若整个区间都是堆，则返回 last

注意：

push_heap()、pop_heap()、sort_heap() 都要求区间已经是一个合法的堆。
pop_heap() 不会删除元素，只是把堆顶交换到末尾，真正删除需要再调用容器的 pop_back()。
默认使用 < 比较，即构造大根堆；传入比较器（如 greater）即可构造小根堆。

2，优先级队列的底层实现

按照我们刚刚学习stack和queue的一样；我们也可以这样实现优先级队列

template<class T, class Container = std::vector<T> >
class priority_queue
{
public:
//默认大的权重大，默认是大堆，
void AdjustUp(int child)
{
}
void AdjustDown(int parent)
{

}

void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() – 1);
}
void pop()
{
swap(_con[0], _con[_con.size() – 1]);
_con.pop_back();
AdjustDown(0);
}
T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
//size_t _size=0;
};

但是，我们会发现，如果这样实现的话就是堆是大堆还是小堆就固定了，非常不好。所以，C++提供了仿函数来解决这类问题，那么，什么是仿函数呢？

可以稍微润色一下，保持你一直以来简洁、偏教程的风格：

仿函数

仿函数（Functor）：本质上是一个类，只要该类重载了 operator()，那么它的对象就可以像函数一样被调用，因此称为函数对象（Function Object）。

写法

一个经典的仿函数如下：

template<class T>
class Lesser
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};

使用时与普通函数几乎没有区别：

Lesser<int> less;
cout << less(1, 2) << endl; // 输出 1（true）

STL 中大量使用仿函数作为比较规则，例如 sort、set、map、priority_queue 等容器和算法都支持传入自定义仿函数。

那加入了仿函数之后，我们的AdjustUp和AdjustDown函数就可以写成

void AdjustUp(int child)
{
int paret = (child–1) / 2;
//没有写仿函数的版本：while (child >= 0 && _con[child] > _con[parent])
//while (child >= 0 && _con[parent] < _con[child] )
while (child >= 0 && com(_con[parent] , _con[child]))//因为默认是lesser，所以， com(_con[parent] , _con[child])返回真就是_con[parent] < _con[child]
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child – 1) / 2;
}
}
//前提是左右子树都是大根堆堆
void AdjustDown(int parent)//默认是从堆顶开始调整，调整到堆底，
{
int child = parent * 2 + 1;
while (child < _con.size())
{//没有写仿函数的时候：
//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//同理，因为默认是lesser仿函数这里要放小于号魔所以，要换一下位置，
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && com(_con[child] < _con[child + 1]))
{
child++;
}
if (com(_con[parent] ，_con[child]))//同理
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else break;
}
}

什么时候要自己写仿函数呢？

1、类类型不支持比较大小，即类没有重载 <、> 等运算符 2、支持比较大小，但是比较的逻辑不是你想要的例如，下面的 Date 类已经重载了 < 和 >，默认按照年月日进行比较：

class Date
{
public:
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);
}

private:
int _year;
int _month;
int _day;
};

但是当我

bit::priority_queue<Date*> q;

默认情况下，比较的是指针地址：

p1 < p2

而不是 Date 对象本身的大小。

显然，我们真正想比较的是日期，因此需要自己编写仿函数：

class DateLess
{
public:
bool operator()(Date* p1, Date* p2)
{
return *p1 < *p2;
}
};

使用时只需要将仿函数作为第三个模板参数传入即可：

bit::priority_queue<Date*, vector<Date*>, DateLess> q;

总结与复习

三、总结与回顾

一、容器适配器

✅ stack、queue、priority_queue 都属于容器适配器（Container Adapter）。

它们本身并不负责存储数据，而是在已有容器的基础上，限制接口，形成新的数据结构。

例如：

stack：只能尾插、尾删（LIFO）
queue：只能尾插、头删（FIFO）
priority_queue：底层采用堆实现，每次访问堆顶元素

二、为什么默认底层容器不同？

容器默认底层

stack	deque
queue	deque
priority_queue	vector

原因：

deque 支持高效头尾插删，非常适合 stack 和 queue。
priority_queue 底层采用堆实现，而堆本身就是建立在数组上的，因此默认选择 vector。

三、deque 为什么适合作为 stack 和 queue 的底层？

相比 vector：

不需要频繁整体扩容
头插、头删效率高

相比 list：

支持随机访问
空间利用率更高

但是：

deque 并不适合频繁遍历，因此 STL 几乎只把它作为 stack 和 queue 的默认底层容器。

四、priority_queue 本质

priority_queue 本质就是堆。

常用接口：

push()
pop()
top()
empty()

五、仿函数（重点）

仿函数就是：

重载了 operator() 的类，其对象可以像函数一样使用。

STL 中大量使用仿函数作为比较规则。

例如：

less<T> // 大根堆（默认）
greater<T> // 小根堆

也可以自己编写仿函数，实现自己的比较规则。

六、什么时候需要自己写仿函数？

一般有两种情况：

类类型没有重载比较运算符。

默认比较规则不能满足需求。

下期预告

模版进阶

结语

本文到此结束，感谢大家的阅读！如果觉得本文对你有所帮助，欢迎点赞、收藏、关注，也欢迎在评论区一起交流讨论。也欢迎订阅我的深入理解 C++系列：从语法入门到底层原理，系统掌握现代 C++ 算法系列：从入门到精通，蓝桥杯、ACM、LeetCode 与面试算法全路线快速复习系列：知识梳理、查漏补缺，考前冲刺必备 Java 速通系列：已学 C 语言，快速上手 Java，轻松备战期末考试

愿每一次敲下键盘，都比昨天更进一步！

愿每一行代码落下，都让未来多一种可能！

文章目录

上期回顾

stack和queue的使用和相关接口

1.1. stack 的本质

1.2. stack 的常用接口

1.3，stack相关算法题

最小栈⭐⭐

题目链接

题目描述

解题思路

解题代码

大神解题代码

栈的压入、弹出序列⭐⭐

题目链接

题目描述

解题思路

解题代码

大神解题代码

逆波兰表达式求值⭐⭐

题目链接

题目描述

解题思路

解题代码

大神解题代码

2.1. queue 的本质

2.2. queue 的常用接口

2.3，相关经典算法题

二叉树的层序遍历⭐⭐⭐

题目链接

题目描述

解题思路

解题代码

大神解题代码

stack和queue的底层实现

容器适配器

vector 和 list 优缺点总结

vector

list

deque 双端队列（了解即可，但必须要了解）

1 deque的原理介绍

2， deque的迭代器设计

1、deque 迭代器包含四部分

3,deque的缺陷——不适合遍历

4，为什么选择deque作为stack和queue的底层默认容器

priority_queue优先级队列

1，介绍+使用

1，接口

2，堆相关算法（就是不用，了解即可）

2，优先级队列的底层实现

仿函数

写法

什么时候要自己写仿函数呢？

总结与复习

三、总结与回顾

一、容器适配器

二、为什么默认底层容器不同？

三、deque 为什么适合作为 stack 和 queue 的底层？

四、priority_queue 本质

五、仿函数（重点）

六、什么时候需要自己写仿函数？

下期预告

模版进阶

结语

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发