数据结构——双端队列

数据结构——双端队列

  • 什么是双端队列
  • 双端队列的实现
  • 双端队列的使用场景

我们今天来看队列的变形——双端队列：

什么是双端队列

双端队列（Double-Ended Queue, 简称deque）是一种特殊的数据结构，它结合了队列（Queue）和栈（Stack）的特性，允许在两端进行插入（enqueue）和删除（dequeue）操作。双端队列可以在前端（front）进行入队（push）和出队（pop），也可以在后端（rear）进行入队和出队。这种灵活性使得双端队列在很多应用场景中非常实用，特别是在需要高效地处理双向数据流或需要快速访问两端元素的场合。

基本特征：

  1. 两端操作： 双端队列允许在队列的头部（front）和尾部（rear）同时进行插入和删除操作。这意味着您可以从队列的开始或结束处添加或移除元素。
  2. 先进先出（FIFO）与后进先出（LIFO）共存： 根据操作端的不同，双端队列可以表现出队列（FIFO）或栈（LIFO）的行为。在前端出队遵循FIFO原则（最先加入的元素最先离开），在后端出队则遵循LIFO原则（最后加入的元素最先离开）。
  3. 动态大小： 双端队列的大小通常不是固定的，可以根据需要动态增长或缩小。当元素被添加到队列中时，队列会自动扩容以容纳新元素；当元素被移除时，队列空间会被释放，以保持高效的空间利用率。
  4. 多用途： 双端队列在许多算法和应用程序中都有广泛应用，如实现回溯、滑动窗口、缓存、双向链表等。它既可用于常规的队列操作，如任务调度、消息队列等，也可用于需要栈功能的场景，如撤销/重做操作记录、深度优先搜索的回溯等。

常见操作：

  • push_front: 在队列前端插入元素。
  • push_rear: 在队列后端插入元素。
  • pop_front: 从队列前端移除并返回元素。
  • pop_rear: 从队列后端移除并返回元素。
  • peek_front: 查看但不移除队列前端的元素。
  • peek_rear: 查看但不移除队队后端的元素。
  • is_empty: 判断双端队列是否为空。
  • size: 返回双端队列中元素的数量。

实现双端队列的数据结构可以是数组、链表或更复杂的数据结构。使用数组实现时，可能需要进行动态扩容或移动元素以维持高效的插入和删除操作。链表实现则更为灵活，无需考虑连续内存空间的限制，但访问性能可能略逊于数组实现。现代编程语言中通常有内置的双端队列数据结构或第三方库提供高效实现。

总之，双端队列是一种提供两端插入和删除能力的数据结构，它结合了队列和栈的优点，适用于需要高效处理双向数据流或频繁操作两端元素的场景。

在C++中，双向队列，在头文件deque中：
在这里插入图片描述
我们可以使用一下它的接口：
在这里插入图片描述

#include <iostream>
#include<deque>void PrintDque(const std::deque<int>& dq)
{std::deque<int>::const_iterator it = dq.cbegin();while( it != dq.cend()){std::cout << *it++ << ' ';}std::cout<<std::endl;}int main()
{std::deque<int> dq;dq.push_back(12);dq.push_back(13);dq.push_back(14);dq.push_back(15);PrintDque(dq);dq.push_front(16);dq.push_front(17);dq.push_front(18);dq.push_front(19);PrintDque(dq);dq.pop_back();dq.pop_back();dq.pop_back();dq.pop_back();PrintDque(dq);dq.pop_front();dq.pop_front();dq.pop_front();dq.pop_front();PrintDque(dq);if(dq.empty()){std::cout << "dque is empty" << std::endl;}return 0;
}

在这里插入图片描述

双端队列的实现

为了节省时间，我们这里使用vector来作为deque的底层结构：

#include<iostream>
#include<vector>// 定义一个名为 Deque（双端队列）的类
class Deque{
public:// 默认构造函数，创建一个空的双端队列Deque() = default;// 返回一个布尔值，表示当前双端队列是否为空bool is_empty() const{return items.empty();}// 在双端队列的前端添加一个整数元素（item）void add_front(int item){items.insert(items.begin(), item); // 使用 insert 函数将新元素插入到 vector 开头}// 在双端队列的后端添加一个整数元素（item）void add_rear(int item){items.push_back(item); // 使用 push_back 函数将新元素添加到 vector 末尾}// 从双端队列的前端移除并返回一个整数元素int remove_front(){if (is_empty()) // 检查队列是否为空{return -1; // 若为空，返回 -1 表示操作失败}int front_item = items.front(); // 获取队列前端元素的值items.erase(items.begin()); // 使用 erase 函数移除 vector 开头的元素return front_item; // 返回移除的元素值}// 从双端队列的后端移除并返回一个整数元素int remove_rear(){if (is_empty()) // 检查队列是否为空{return -1; // 若为空，返回 -1 表示操作失败}int rear_item = items.back(); // 获取队列后端元素的值items.pop_back(); // 使用 pop_back 函数移除 vector 末尾的元素return rear_item; // 返回移除的元素值}private:// 使用 std::vector 存储双端队列中的整数元素std::vector<int> items;
};

int main()
{Deque deque;deque.add_front(1);deque.add_front(2);deque.add_rear(3);deque.add_rear(4);std::cout << "Deque front: " << deque.remove_front()<< std::endl;std::cout << "Deque rear: " << deque.remove_rear()<< std::endl;return 0;
}

在这里插入图片描述

双端队列的使用场景

双端队列作为一种特殊的数据结构，具有在两端同时进行插入和删除操作的能力，这使得它适用于多种需要灵活增删元素的场景。以下是双端队列的一些典型使用场景：

  1. 滑动窗口算法：
    双端队列常被用于实现滑动窗口相关的问题，如计算数据流中一定时间段内的统计信息（如平均值、最大值、最小值等）。当新的数据进入窗口时，旧的数据会从另一端移出，双端队列能很好地模拟这种动态窗口的更新过程。
  2. 队列管理：
    在生产者-消费者模型中，双端队列可以用来高效地管理和同步任务。生产者在队列一端（通常是后端）添加任务，消费者则从另一端（通常是前端）取出并执行任务。双端队列支持高效并发操作，有利于提高系统吞吐量。
  3. 回溯算法：
    在解决某些需要进行路径搜索或状态回溯的问题（如深度优先搜索、迷宫求解等）时，双端队列可以作为“待探索节点”列表。新发现的节点可以快速地加入队列尾部，而回溯时则可以从队列头部移除已探索节点，实现高效的节点管理。
  4. 图形/网页布局：
    在处理图形用户界面（GUI）或网页布局时，双端队列可用于维护待布局元素的列表。新添加或修改的元素可以快速插入队列尾部，而布局引擎可以从队列前端开始处理元素，同时移除已布局完成的元素。
  5. 文字处理软件的撤销/重做功能：
    双端队列可以用来存储编辑历史记录，撤销操作相当于从队首移除并恢复之前的状态，而重做操作则是从队尾添加最近撤销的更改重新应用。这样可以方便地实现多次撤销和重做的功能。
  6. 事件处理：
    在事件驱动编程中，双端队列可以作为一个事件缓冲区，新发生的事件被添加到队尾，事件处理器则从队首取出并处理事件。这种结构有助于保证事件处理的顺序性和避免事件丢失。
  7. 缓存管理：
    双端队列可以作为缓存结构的一部分，用于实现最近最少使用（LRU）缓存淘汰策略。新访问的项加入队尾，当缓存满时，最近最少使用的项（即队首的项）会被移除。
  8. 排序算法辅助：
    在某些排序算法（如归并排序、拓扑排序等）中，双端队列可以作为中间数据结构，用于暂存待合并的子序列或待处理的节点，支持在序列两端进行快速的插入和提取操作。
  9. 任务调度：
    在实时系统或操作系统中，双端队列可用于实现优先级调度。高优先级任务可以快速地插入队首，低优先级任务则在队尾等待。调度器按照优先级从队首取出任务执行。
  10. 数据流处理：
    在处理数据流或流式计算时，双端队列可以作为缓冲区存储短暂的历史数据，便于进行窗口内计算或根据最近数据做出决策。

总之，双端队列因其独特的双端操作特性，适用于任何需要在数据结构两端高效插入和删除元素的场景，特别是在处理动态数据流、历史记录管理、任务调度和搜索算法中表现出色。

下面是双端队列的使用场景：

  1. 滑动窗口最大值：给定一个数组 nums, 有一个大小为 k 的滑动窗口从数组的最左侧移动至数组的右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。这个问题可以使用双端队列来高效地找到每个窗口的最大值。
  2. 接雨水问题：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。这个问题的一个解法是使用两个双端队列，分别处理左右两侧的柱子，通过维护单调递减的队列来快速计算每个柱子上方能接到的雨水量。
  3. 队列实现栈：使用两个双端队列来实现一个栈，使得栈的 push、pop 操作的时间复杂度都是 O(1)。
  4. 回文判断：给定一个字符串，判断它是否为回文字符串。可以使用双端队列来存储字符串的前半部分，然后依次弹出队列中的字符与字符串的后半部分进行比较。
  5. 合并区间：给出一个区间的集合，请合并所有重叠的区间。可以使用双端队列来存储区间，并按照区间的起始点进行排序，然后合并相邻的区间。
  6. 最大子序和（Kadane算法）：虽然这个问题通常使用动态规划解决，但也可以使用双端队列来优化求解过程，尤其是在需要多次查询最大子序和的情况下。
  7. 股票交易：模拟股票交易过程，包括买入、卖出和强制平仓等操作。双端队列可以用来维护一个买卖订单簿，快速匹配买卖订单。

这些算法题目中，双端队列可以帮助我们高效地管理数据，尤其是在需要快速访问序列的两端或者维护一个有序序列的时候。

比如说力扣上的滑动窗口的最大值：
在这里插入图片描述用C++的话，可以这样写：

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {std::deque<int> dq;std::vector<int> result;for (int i = 0; i < nums.size(); ++i) {// 移除队列中不在滑动窗口范围内的元素if (!dq.empty() && dq.front() == i - k) {dq.pop_front();}// 从队列尾部移除小于当前元素的元素while (!dq.empty() && nums[dq.back()] < nums[i]) {dq.pop_back();}// 将当前元素的索引插入队列dq.push_back(i);// 当滑动窗口完全在数组范围内时，将队列头部的最大值添加到结果数组中if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;}
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/2981583.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

算法刷题day46

算法刷题day46

目录 引言一、树的重心二、毕业旅行问题三、高精度乘法 引言 今天复习了一下高精度的所有模板&#xff0c;包括加法、减法、乘法、除法&#xff0c;因为自己当时在蓝桥杯的时候没有看出来那个题使用高精度&#xff0c;因为对于一个数的大小和一个数的长度&#xff0c;自己有时…
阅读更多...
flutter笔记-万物皆是widget

flutter笔记-万物皆是widget

文章目录 helloFlluter自定义Widget优化 这篇文章后就不见写了&#xff0c;学flutter主要是为了更好的使用 flutter-webrtc&#xff0c;所以到这里基本就了解了大部分的知识&#xff0c;后续边用边查&#xff1b; 在flutter中所有的view都叫widget&#xff0c;类似文本组件Tex…
阅读更多...
女生学习PLC专业，好就业吗？

女生学习PLC专业，好就业吗？

好就业&#xff0c;plc找工作容易 但不建议女生做PLC相关工作&#xff0c; plc的工作会涉及现场安装调试&#xff0c;难免体力或者登高爬梯&#xff0c;对女生来说有点辛苦。还都会长期出差&#xff0c;身体辛苦之外&#xff0c;心理是煎熬&#xff0c;初入行时出差或许是乐事…
阅读更多...
qt5-入门-自定义委托-可编辑的TableModel与信号接收

qt5-入门-自定义委托-可编辑的TableModel与信号接收

参考&#xff1a; C GUI Programming with Qt 4, Second Edition 本地环境&#xff1a; win10专业版&#xff0c;64位&#xff0c;Qt5.12 上一篇&#xff1a; qt5-入门-自定义委托-简单例子_qt 委托-CSDN博客 https://blog.csdn.net/pxy7896/article/details/137234839 本篇重…
阅读更多...
编写你的第一个java 程序

编写你的第一个java 程序

1.安装 jdk 网址&#xff1a; Java Downloads | Oracle 一般我们安装jdk 17 就行了 自己练习 自己学习 真正的开发中我们使用jdk 8 这个是最适合开发java 应用程序的 当然你也可以选择你的 系统 来安装这个java 在文件资源管理器打开JDK的安装目录的bin目录&#xff0c;会发…
阅读更多...
通义千问(Qwen)AI大模型-系列_2

通义千问(Qwen)AI大模型-系列_2

一、通义千问系列模型 1、CodeQwen1.5-7B-Chat CodeQwen1.5是Qwen1.5的代码特定版本。它是一种基于变换器的纯解码器语言模型&#xff0c;在大量代码数据上进行预训练。 强大的代码生成能力和在一系列基准测试中具有竞争力的性能;支持长上下文理解和生成&#xff0c;上下文长度…
阅读更多...
【FX110网】股市、汇市一年有多少个交易日？

【FX110网】股市、汇市一年有多少个交易日？

事实上&#xff0c;作为交易者&#xff0c;重要的是要了解并非每天都是交易日。虽然金融市场在大多数工作日开放交易&#xff0c;但在某些特定情况下无法进行交易。这些非交易日可能因各种原因而发生&#xff0c;包括节假日、周末和市场休市。 通过随时了解假期、交易时间表和市…
阅读更多...
逆数对（树状数组的方法）

逆数对（树状数组的方法）

本题链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 题目&#xff1a; 样例&#xff1a; 输入 5 4 5 1 3 2 输出 7 思路&#xff1a; 根据题意&#xff0c;求逆序对总数。 逆序对含义&#xff1a;如果数组中的两个不同位置&#xff0c;前面的数字比后面的数字严格大&…
阅读更多...
混沌工程理论建设和项目实践

混沌工程理论建设和项目实践

混沌工程理论建设和项目实践 1. 背景说明2. 为什么要做混沌工程2.1 混沌目标2.2 演习对象2.3 影响可用性的主要因素及应对2.4 可行性论证和控制爆炸半径 3. 如何落地3.1 安全、有效的实验3.2 安全&#xff1a;不影响线上业务3.2.1 爆炸半径3.2.2 特殊限制与审批 3.3 有效&#…
阅读更多...
使用BibTeX导入参考文献到Overleaf项目（常用方法）

使用BibTeX导入参考文献到Overleaf项目（常用方法）

使用bib为overleaf导入参考文献的好处 整洁的管理&#xff1a; 使用 .bib 文件可以使你的参考文献管理更加整洁和有条理。你可以将所有的参考文献集中存储在一个文件中&#xff0c;而不是在文档中直接引用或复制粘贴。 易于维护和更新&#xff1a; 当你需要添加、删除或修改参考…
阅读更多...
WEB攻防-ASP中间件IIS文件上传解析安全漏洞

WEB攻防-ASP中间件IIS文件上传解析安全漏洞

漏洞原理&#xff1a; 基于文件 IIS6.0默认不解析;号后面的内容&#xff0c;例如1.asp;.jpg会当成1.asp解析&#xff0c;相当于分号截断。 基于文件夹 IIS6.0会将/*.asp/文件夹下的文件当成asp解析。 案例&#xff1a; 写一个木马文件&#xff0c;并改为jpg后缀 GIF89agif8…
阅读更多...
报名 | Qt汽车及工业行业解决方案及实战训练 深圳站（5月15日 星期三）

报名 | Qt汽车及工业行业解决方案及实战训练 深圳站（5月15日 星期三）

加入我们的Qt技术培训&#xff0c;探索跨平台应用开发的无限可能&#xff01;本次培训将深入Qt框架&#xff0c;涵盖从基础概念到高级功能的全方位知识&#xff0c;无论您是刚入门的新手还是希望提升技能的资深开发者&#xff0c;都能在此找到适合自己的学习路径。通过实践案例…
阅读更多...
python学习笔记（集合）

python学习笔记（集合）

知识点思维导图 # 直接使用{}进行创建 s{10,20,30,40} print(s)# 使用内置函数set()创建 sset() print(s)# 创建一个空的{}默认是字典类型 s{} print(s,type(s))sset(helloworld) print(s) sset([10,20,30]) print(s) s1set(range(1,10)) print(s1)print(max:,max(s1)) print(m…
阅读更多...
OceanBase 开发者大会 - 见闻与洞察

OceanBase 开发者大会 - 见闻与洞察

文章目录 前言主论坛见闻技术专场见闻产品技术专场技术生态专场 同行论道启发互动展区写在最后 前言 4 月 20 日&#xff0c;我有幸受邀参加了第二届 OceanBase 开发者大会。 50 余位业界知名数据库大咖和数据库爱好者&#xff0c;与来自全国近 600 名开发者相聚。共同探讨一体…
阅读更多...
【01-机器学习入门：理解Scikit-learn与Python的关系】

【01-机器学习入门：理解Scikit-learn与Python的关系】

文章目录 前言Python与机器学习Scikit-learn简介Scikit-learn与Python的关系使用Scikit-learn进行机器学习结语前言 在当今的数据科学和人工智能领域，机器学习已经成为了一个不可或缺的组成部分。而对于那些刚刚踏入这一领域的新手来说，理解机器学习的基本概念和找到合适的工…
阅读更多...
Security初探(二)

Security初探(二)

SpringSecurity初探(一)-CSDN博客 上面介绍了用了在SpringBoot里配置UserDetailsService和PasswordEncoder两个Bean 下面介绍一种替换掉上面两个Bean的方式 看下效果实际是和创建UserDetailsService和PassswordEncoder两个Bean的效果是一样的 还有一种方式混合搭配 当然不推…
阅读更多...
【C语言__指针01__复习篇11】

【C语言__指针01__复习篇11】

目录 前言 一、什么是指针 二、计算机中常见的单位 三、CPU是怎样找到一块内存空间的 四、如何得到变量的地址 五、指针变量 六、解引用指针变量的作用 七、指针变量的大小 八、指针变量类型的意义 8.1 指针的解引用 8.2 指针-整数 九、void*指针 十、const修饰变…
阅读更多...
【算法学习】线段树基础版

【算法学习】线段树基础版

一 线段树 1.概念 线段树可以理解为一个二叉树&#xff0c;如果是利用线段树求区间的和&#xff0c;那么每个结点的权值维护的是结点所维护区间的和&#xff0c;再将该区间一分为二&#xff0c;分别交由左右儿子维护。 拿区间1 - 4的和来举例子&#xff0c; 根结点维护的是区…
阅读更多...
开发简易复用 SDK（项目加分项）

开发简易复用 SDK（项目加分项）

文章目录 开发 SDK新建项目修改pom文件删除启动类创建配置类复制之前的客户端新建spring.factories打包 开发 SDK 为什么要开发SDK。 减少代码的冗余提高代码的复用 如果实际项目中需要使用到该SDK&#xff0c;在pom.xml中注入就可以了。 类似于maven一样&#xff0c;把需要…
阅读更多...
ctfshow——XSS

ctfshow——XSS

文章目录 XSS介绍什么是xss&#xff1f;XSS危害XSS的分类常用XSSpayload web316——反射型XSSweb317——过滤<script> web318——过滤script、imgweb319——不止过滤script、imgweb320——过滤空格web321——不止过滤空格web322——不止过滤空格web323web324web 325web32…
阅读更多...
最新文章

Copyright @ 2022~2023