队列(Queue)\双端队列(Deque)
2024-10-19 10:29:57
队列(Queue)\双端队列(Deque)
队列(Queue)
特点:
和栈不同,队列的最大特点是先进先出(FIFO),就好像按顺序排队一样。对于队列的数据,我们只允许在队尾查看和添加数据,在队头查看和删除数据。
实现:
可以借助双端队列来实现队列。双链表的头指针允许在队头查看和删除数据,而双链表的尾指针允许我们在队尾查看和添加数据。
应用场景:
当我们需要按照一定的顺序来处理数据,而该数据的数据量在不断变化的时候,则需要队列来帮助解题。在算法面试中,广度优先搜索是运用队列最多的地方。
双端队列(Deque)
特点:
双端队列和普通队列最大的不同在于,它允许我们在队列的头尾两端都能在O(1)的时间内进行数据的查看、添加和删除。
实现:
与队列相似,我们可以利用一个双链表实现双端队列。
应用场景:
双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间,而动态窗口这种数据结构在很多题目中都有运用。
算法应用
LeetCoded第239题题解–滑动窗口最大值
LeetCoded第933题题解–最近的请求次数
LeetCoded第621题题解–任务调度器
LeetCoded第642题题解–设计循环双端队列
最新文章
- MySQL查询分析器EXPLAIN或DESC
- ios中自定义cell 设置cell的分组结构
- javascript设计模式与开发实践阅读笔记(5)——策略模式
- BZOJ4383 : [POI2015]Pustynia
- asp.net连接SQL SERVER 2012的方法
- css 之优先策略
- 小数点输出精度控制问题 .xml
- [Papers]NSE, $\pi$, Lorentz space [Suzuki, NA, 2012]
- 具有 Button 风格的 Panel(覆盖TCustomPanel的Paint函数,用到了ThemeServices)
- AIX加入能telnet远程连接方法的帐户
- Socket层上的协议
- 【转载】十条jQuery代码片段助力Web开发效率提升
- Webpack的配置与使用
- SpringCloud使用Sofa-lookout监控(基于Eureka)
- python数据结构-如何快速找到多个字典中的公共键
- D - C Looooops POJ - 2115 欧几里德拓展
- 深入浅出 - vue变化侦测原理
- position实现分层和遮罩层功能
- js获取当月最后一天
- Android 消息分发机制