代码随想录笔记|C++数据结构与算法学习笔记-栈和队列(〇)|stack、queue、单调队列和优先级队列(priority_queue)、大顶堆和小顶堆

本文主要是介绍代码随想录笔记|C++数据结构与算法学习笔记-栈和队列(〇)|stack、queue、单调队列和优先级队列(priority_queue)、大顶堆和小顶堆,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • stack容器
    • stack 基本概念
    • 常用接口
      • 构造函数
      • 赋值操作
      • 数据存取
      • 大小操作
  • queue容器
    • queue常用接口
      • 构造函数:
      • 赋值操作
      • 数据存取
      • 大小操作
  • 单调队列
    • 定义
    • 实现
      • 代码实现
    • 基本应用一:滑动窗口
      • 思路与算法
  • 优先级队列
    • 定义
      • 大顶堆(最大堆)、小顶堆(最小堆)
    • 实现
    • 基本操作
      • `push`和`emplace`
    • 基本应用一:滑动窗口
      • 思路与算法

stack容器

stack 基本概念

在这里插入图片描述
栈中只有顶端的元素才可以被外界使用,因此栈不允许有遍历行为。
栈中进入数据称为 — 入栈 push

栈中弹出数据称为 — 出栈 pop

常用接口

构造函数

  • stack<T> stk; //stack采用模板类实现, stack对象的默认构造形式
  • stack(const stack &stk); //拷贝构造函数

赋值操作

  • stack& operator=(const stack &stk); //重载等号操作符

数据存取

  • push(elem) //向栈顶添加元素
  • pop(); //从栈顶移除元素
  • top(); //返回栈顶元素

大小操作

  • empty; //返回堆栈是否为空
  • size(); //返回栈的大小

queue容器

在这里插入图片描述
队列容器允许从一端新增元素,从另一端移除元素

队列中只有队头和队尾才可以被外界使用,因此队列不允许有遍历行为

队列中进数据称为 — 入队 push

队列中出数据称为 — 出队 pop

queue常用接口

构造函数:

  • queue<T> que; //queue采用模板类实现,queue对象的默认构造形式
  • queue(const queue &que); //拷贝构造函数

赋值操作

  • queue& operator=(const queue &que); //重载等号操作符

数据存取

  • push(elem); //往队尾添加元素
  • pop(); //从队头移除第一个元素
  • back(); //返回最后一个元素
  • front(); //返回第一个元素

大小操作

  • empty(); //判断堆栈是否为空
  • size(); //返回栈的大小

单调队列

定义

单调队列也是一种常用的数据结构,但是在C++中并没有这类数据结构的实现。

单调队列的单调在于其内部的元素始终按照一定的单调性(递增或递减)排列。

始终按照是什么意思呢?即在每次加入或者删除元素时都保持序列里的元素有序,即队首元素始终是最小值或者最大值,这个功能非常重要,单调队列我们就是使用的这个功能
这种数据结构通常用于解决滑动窗口类型的问题,可以在 O(1) 时间复杂度内给出当前窗口的最大值或最小值。

实现

在实现时,需要保证队列的单调性:对于一个单调递增的队列,新进入队列的元素如果小于队尾的元素,那么队尾的元素将会被移除,直到队列单调或者队列为空。这样,队头元素始终是当前窗口的最小值。单调递减队列则相反
例子如下所示:

1: 5
2: 8
3: 8 2
4: 8 4
5: 8 4 1

详细过程如下:

1.首先队列里面没有元素,5加进去。
2.第二个元素8大于队尾的元素,所以5要弹出去,8加进去。保持队首最大
3.第三个元素2小于队尾元素8,可以加进去,变为8 2
4.4大于队尾元素2,2弹出,4小于8,8不弹出,4加进去
5.1小于队尾元素4,1加进去,最后队列为8 4 1

代码实现

单调队列的实现通常使用双端队列(deque),它允许在队列的前端和后端都可以进行元素的添加和删除操作

#include <deque>
#include <vector>template<typename T>
class MonotonicQueue {
private:std::deque<T> data;public:// Push an element on the queue. Remove elements smaller than the incoming one// to maintain the monotonic property.void push(T val) {while (!data.empty() && data.back() < val) {data.pop_back();}data.push_back(val);}// Return the maximum elementT max() const {return data.front();}// Pop an element from the queuevoid pop(T val) {if (!data.empty() && data.front() == val) {data.pop_front();}}
};

基本应用一:滑动窗口

文章链接
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

思路与算法

由于我们需要求出的是滑动窗口的最大值,如果当前的滑动窗口中有两个下标 ij,其中 i j 的左侧(i<j),并且 i 对应的元素不大于 j 对应的元素(nums[i]≤nums[j]),那么会发生什么呢?

当滑动窗口向右移动时,只要i还在窗口中,那么 j 一定也还在窗口中,这是 ij左侧所保证的。因此,由于 nums[j]的存在,nums[i] 一定不会是滑动窗口中的最大值了,我们可以将 nums[i]永久地移除

因此我们可以使用单调队列存储所有还没有被移除的下标。在单调队列中,这些下标按照从小到大的顺序被存储,并且它们在数组nums中对应的值是严格单调递减的。因为如果队列中有两个相邻的下标,它们对应的值相等或者递增,那么令前者为i,后者为 j,就对应了上面所说的情况,即 nums[i]会被移除,这就产生了矛盾。

当滑动窗口向右移动时,我们需要把一个新的元素放入队列中。为了保持队列的性质,我们会不断地将新的元素与队尾的元素相比较,如果前者大于等于后者,那么队尾的元素就可以被永久地移除,我们将其弹出队列。我们需要不断地进行此项操作,直到队列为空或者新的元素小于队尾的元素。

由于队列中下标对应的元素是严格单调递减的,因此此时队首下标对应的元素就是滑动窗口中的最大值。不过此时的最大值可能在滑动窗口左边界的左侧,并且随着窗口向右移动,它永远不可能出现在滑动窗口中了。因此我们还需要不断从队首弹出元素,直到队首元素在窗口中为止

链接:力扣官方题解

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();deque<int> q;for (int i = 0; i < k; ++i) {while (!q.empty() && nums[i] >= nums[q.back()]) {q.pop_back();}q.push_back(i);}vector<int> ans = {nums[q.front()]};for (int i = k; i < n; ++i) {while (!q.empty() && nums[i] >= nums[q.back()]) {q.pop_back();}q.push_back(i);while (q.front() <= i - k) {q.pop_front();}ans.push_back(nums[q.front()]);}return ans;}
};

优先级队列

定义

优先级队列是一种抽象数据类型,它支持普通队列的基本操作,如入队和出队。不过,在优先级队列中,每个元素都有一定的“优先级”,出队操作会移除具有最高优先级的元素,而不是最先进入队列的元素。这种队列通常用于任务调度、带优先级的待办事项管理等场合。

在 C++ 中,优先级队列通常通过使用二叉堆(特别是大顶堆或小顶堆)来实现,而且标准库 <queue> 中已经提供了模板类 std::priority_queue

std::priority_queue 是一个容器适配器,它提供了某种特定服务策略(默认为最大堆)排序的队列

std::priority_queue 默认情况下使用一个 std::vector 作为底层容器,并使用 std::less 作为比较函数,这意味着元素是按照严格弱序(默认为大顶堆,即最大的元素总是在队列前端)排序的。

#include <iostream>
#include <queue>// 默认情况下,C++使用最大堆实现优先级队列
std::priority_queue<int> max_heap;// 使用最小堆实现优先级队列
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

那么问题来了,大顶堆和小顶堆又是什么呢?

大顶堆(最大堆)、小顶堆(最小堆)

堆的概念:堆具有结构性,也就是它是采用数组表示的完全二叉树。堆还具有有序性,也就是根节点大于子节点(或者小于子节点)

通过根节点大于子节点(或小于子节点),又可以将堆分为大顶堆和小顶堆

大顶堆:又称为最大堆,也就是树中所有父节点都要大于或等于子节点

小顶堆:又称为最小堆,也就是树中所有父节点都要小于或等于子节点

原文链接

实现

#include <iostream>
#include <queue>// 默认情况下,C++使用最大堆实现优先级队列
std::priority_queue<int> max_heap;// 使用最小堆实现优先级队列
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

基本操作

  • top:返回优先队列中具有最高优先级的元素。对于最大堆实现的优先队列,这将是最大的元素;对于最小堆实现,则是最小的元素。
  • push:向优先队列中添加一个元素。新元素的位置将根据其优先级与其他元素的比较结果来确定。
  • pop: 移除具有最高优先级的元素。在最大堆优先队列中,这通常是最大元素;在最小堆中,是最小元素。
  • empty: 检查优先队列是否为空。如果队列为空,返回 true;否则返回 false
  • size: 返回优先队列中元素的个数。
  • emplace:这个方法可以用来直接在优先队列的底层容器中就地构造一个新元素,这样可以避免额外的拷贝或移动操作。

pushemplace

push 方法相比,emplace 方法可以更高效地添加元素,特别是当队列中的对象较大或拥有非平凡的构造函数时。emplace 方法接受与元素构造函数相同的参数,并且在队列的适当位置直接构造对象。

#include <iostream>
#include <queue>
#include <string>int main() {std::priority_queue<std::string> pq;// 直接在优先队列中构造元素pq.emplace("orange");pq.emplace("strawberry");pq.emplace("apple");std::cout << "The top element is " << pq.top() << '\n';return 0;
}

在这个例子中,emplace 用于直接在优先队列中构造 std::string 对象。这避免了创建临时 std::string 对象并将它们推入队列的需要。这样不仅提高了效率,而且也使代码更加简洁。

基本应用一:滑动窗口

文章链接
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

思路与算法

对于「最大值」,我们可以想到一种非常合适的数据结构,那就是优先队列(堆),其中的大根堆可以帮助我们实时维护一系列元素中的最大值

初始时,我们将数组 nums的前 k 个元素放入优先队列中。每当我们向右移动窗口时,我们就可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中,在这种情况下,这个值在数组 nums中的位置出现在滑动窗口左边界的左侧。因此,当我们后续继续向右移动窗口时,这个值就永远不可能出现在滑动窗口中了,我们可以将其永久地从优先队列中移除

我们不断地移除堆顶的元素,直到其确实出现在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系,我们可以在优先队列中存储二元组 (num,index),表示元素 num在数组中的下标为 index

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();priority_queue<pair<int, int>> q;	//pair<int, int>将数组的值和对应的索引捆绑在一起for (int i = 0; i < k; ++i) {q.emplace(nums[i], i);}vector<int> ans = {q.top().first};for (int i = k; i < n; ++i) {q.emplace(nums[i], i);	//每次迭代将新元素和其索引加入优先级队列中。while (q.top().second <= i - k) {//在这个循环中,移除所有不再属于当前滑动窗口的元素//q.top().second 是队列顶部元素的索引,//如果它小于或等于 i - k,那么这个元素就不在窗口 [i - k + 1, i] 范围内,//因此需要将其从队列中弹出。q.pop();}ans.push_back(q.top().first);}return ans;}
};

链接:力扣官方题解

这篇关于代码随想录笔记|C++数据结构与算法学习笔记-栈和队列(〇)|stack、queue、单调队列和优先级队列(priority_queue)、大顶堆和小顶堆的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/859165

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a