必备技巧:深入理解 queue(队列)在算法中的经典应用场景
最编程
2024-07-19 21:20:07
...
一、前言
算法是计算机软件的基础,常见算法是软件开发的核心基本功,今年打算深入学习一些算法,记录一些算法理论以及最佳实践,希望可以坚持下去,关注我,我们一起学习,增强我们的基本功。
二、队列介绍与经典操作
我们应该很熟悉队列的特性,先进先出
,和我们生活中排队办事是一样的,先来先服务
。
队列底层可以通过数组或者链表来实现。
1、用队列实战栈
虽然队列特性和栈特性相反,上文分析了栈可以实现队列,其实队列也可以实现栈
。
我们有两种方案可以实现。
- 第一种,通过两个队列实现。
- 第二种,通过1个队列实现。
1个队列怎么实现栈呢? 我们每次把除队列尾的全部弹出,并且重新加入队列尾部后面。这样一个队列可以达到栈的目的。
2、优先级队列,解决topK问题
优先级队列,可以按元素排序,最大或者最小的元素排在队列头部。
比如我们需要从100个数里面找出最大的3个数。我们可以怎么做呢?我们可以维护一个只有三个元素的优先级队列,队头存最小值,队尾存最大值
,每次入队做好排序,同时把队头小的元素优先出队,直到所有元素入队完成,最后队列里留下的数都是比其他元素大的数了。
三、队列实战
leetcode队列实现栈225. 用队列实现栈
- 方案一使用一个队列
class MyStack {
LinkedList<Integer> linkedList = new LinkedList<>();
LinkedList<Integer> linkedList2 = new LinkedList<>();
public MyStack() {
}
public void push(int x) {
linkedList.addLast(x);
}
public int pop() {
int len = linkedList.size();
if(len == 0) {
return 0;
}
int l = len-1;
while(l > 0) {
int v = linkedList.poll();
linkedList2.addLast(v);
l--;
}
int val = linkedList.poll();
linkedList = linkedList2;
linkedList2 = new LinkedList<>();
return val ;
}
public int top() {
return linkedList.peekLast();
}
public boolean empty() {
return linkedList.isEmpty();
}
}
- 方案二使用两个队列
class MyStack {
LinkedList<Integer> linkedList = new LinkedList<>();
public MyStack() {
}
public void push(int x) {
linkedList.addLast(x);
}
public int pop() {
int len = linkedList.size();
if(len == 0) {
return 0;
}
int l = len-1;
while(l > 0) {
int v = linkedList.poll();
linkedList.addLast(v);
l--;
}
return linkedList.poll();
}
public int top() {
return linkedList.peekLast();
}
public boolean empty() {
return linkedList.isEmpty();
}
}
topk问题,347. 前 K 个高频元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//先统计频率数量
Map<Integer,Integer> map = new HashMap();
for(int i=0; i<nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i],0) + 1);
}
//只寸k个元素 队列里面保留最大的队头存最小的 从小到大排序 传入比较器
PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>(k, (e1, e2) -> e1.getValue().equals(e2.getValue()) ? 0 : ((e1.getValue()<e2.getValue())? -1 : 1));
//只存两个元素
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(queue.size() < k) {
queue.add(entry);
} else {
//超过了k个了,将队列头移除,再入队
Map.Entry<Integer, Integer> e = queue.peek();
//大于队头元素,入队
if(e.getValue() < entry.getValue()) {
queue.poll();
queue.add(entry);
}
}
}
int[] result = new int[k];
int i = 0;
for(Map.Entry<Integer, Integer> q : queue) {
result[i] = q.getKey();
i++;
}
return result;
}
}
四、总结
队列具有先进先出
的特性,本文分析了几种常见的使用场景,我们可以通过队列实现栈的能力,也可以实现通过优先级队列解决TopK的问题,其实队列在我们实际开发中使用场景很多的,比如线程池通过队列缓存待执行任务,再比如ReentrantLock里面的公平锁实现也是通过队列来实现的。
算法知识是我们开发的基本功,有空我们学习探索一些算法知识呀!!
推荐阅读
-
【2022新手指南】Java编程进阶之路 - 六、技术架构篇 ### MySQL索引底层解析与优化实战 - 你会讲解MySQL索引的数据结构吗?性能调优技巧知多少? - Redis深度揭秘:你知道多少?从基础到哨兵、主从复制全梳理 - Redis持久化及哨兵模式详解,还有集群搭建和Leader选举黑箱打开 - Zookeeper是个啥?特性和应用场景大公开 - ZooKeeper集群搭建攻略及 Leader选举、读写一致性、共享锁实现细节 - 探究ZooKeeper中的Leader选举机制及其在分布式环境中的作用 - Zab协议深入剖析:原理、功能与在Zookeeper中的核心地位 - RabbitMQ全方位解读:工作模式、消费限流、可靠投递与配置策略 - 设计者视角:RabbitMQ过期时间、死信队列与延时队列实践指南 - RocketMQ特性和应用场景揭示:理解其精髓与差异化优势 - Kafka详细介绍:特性及广泛应用于实时数据处理的场景解析 - ElasticSearch实力揭秘:特性概述与作为搜索引擎的广泛应用 - MongoDB认知升级:非关系型数据库的优势阐述,安装与使用实战教学 - BIO/NIO/AIO网络模型对比:掌握它们的区别与在网络编程中的实际应用 - Netty带你飞:理解其超快速度背后的秘密,包括线程模型分析 - 网络通信黑科技:Netty编解码原理与常用编解码器的应用,Protostuff实战演示 - 解密Netty粘包与拆包现象,怎样有效应对这一常见问题 - 自定义Netty心跳检测机制,轻松调整检测间隔时间的艺术 - Dubbo轻骑兵介绍:核心特性概览,服务降级实战与其实现益处 - Dubbo三大神器解读:本地存根与本地伪装的实战运用与优势呈现 ----------------------- 七、结语与回顾
-
深入理解STL中的queue(队列)机制:探索队列在STL中的工作原理与应用
-
掌握技巧:深入理解优先级队列(Priority Queue)在数据结构中的应用
-
必备技巧:深入理解 queue(队列)在算法中的经典应用场景