队列集训：科普队列概念与leetcode相关题目精讲
Author：zhoulujun Date：
队列（Queue）
队列（Queue）：一种线性表数据结构，是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。
简单来说，队列是一种 「先进先出（First In First Out）」 的线性表，简称为 「FIFO 结构」。
更详细的，推荐阅读：https://algo.itcharge.cn/04.Queue/01.Queue-Basic/01.Queue-Basic/
优先队列（Priority Queue）
优先队列（Priority Queue）：一种特殊的队列。在优先队列中，元素被赋予优先级，当访问队列元素时，具有最高优先级的元素最先删除。
优先队列与普通队列最大的不同点在于 出队顺序。
普通队列的出队顺序跟入队顺序相关，符合「先进先出（First in, First out）」的规则。
优先队列的出队顺序跟入队顺序无关，优先队列是按照元素的优先级来决定出队顺序的。优先级高的元素优先出队，优先级低的元素后出队。优先队列符合 「最高级先出（First in, Largest out）」 的规则。
优先队列的适用场景
优先队列的应用场景非常多，比如：
数据压缩：赫夫曼编码算法；
最短路径算法：Dijkstra 算法；
最小生成树算法：Prim 算法；
任务调度器：根据优先级执行系统任务；
事件驱动仿真：顾客排队算法；
排序问题：查找第 k 个最小元素。
更详细的推荐阅读：https://algo.itcharge.cn/04.Queue/02.Priority-Queue/01.Priority-Queue/
leetcode题目：
LeetCode上有很多题目涉及到队列（Queue）的使用，包括普通队列、循环队列、双端队列（Deque）、优先队列等。下面是一些与队列相关的典
队列的顺序存储与链式存储
队列实现
232. 用栈实现队列 (Implement Queue using Stacks)：实现一个队列，只允许使用栈来完成。
622. 设计循环队列 (Design Circular Queue)：设计一个循环队列的数据结构，包括队列的插入、删除、检查是否为空和检查是否已满等
641. 设计循环双端队列 (Design Circular Deque)：设计一个循环双端队列，允许在两端进行插入和删除操作
1670. 设计前中后队列 (Design Front Middle Back Queue)：设计一个队列，允许在队列的前端、中间和后端进行插入和删除操作
队列题
933. 最近的请求次数 (Number of Recent Calls)：记录最近的N个请求，并返回在过去3000毫秒内被调用的次数。
859. 亲密字符串 (Buddy Strings)：检查两个字符串是否可以通过交换一次字符变成相同的字符串。
860. 柠檬水找零 (Lemonade Change)：模拟顾客购买柠檬水的过程，处理找零问题，确保有足够的零钱找给顾客。
969. 煎饼排序 (Pancake Sorting)：通过一系列翻转操作将一个数组按升序排序。
621. 任务调度器 (Task Scheduler)：给定一个任务列表和冷却时间，确定完成所有任务所需的最短时间。
338. 比特位计数 (Counting Bits)：计算从0到给定整数n之间的每个数字的二进制表示中1的个数。
优先队列相关题目
215. 数组中的第K个最大元素 (Kth Largest Element in an Array)：找到未排序数组中的第k个最大元素。
23. 合并K个排序链表 (Merge k Sorted Lists)：合并多个已排序的链表。
973.最接近原点的 K 个点
239. 滑动窗口最大值 (Sliding Window Maximum)：在给定数组的每个滑动窗口中找到最大值。
前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2: 输入: nums = [1], k = 1 输出: [1]
最简单粗暴的思路就是 使用排序算法对元素按照频率由高到低进行排序，然后再取前 k 个元素。
排序中，可以使用桶排序（推荐阅读《再谈桶排排序算法—从计数排序到桶排序》）
桶排序法
首先依旧使用哈希表统计频率，统计完成后，创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标即可。
//基于桶排序求解「前 K 个高频元素」
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList();
// 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
HashMap<Integer,Integer> map = new HashMap();
for(int num : nums){
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
//桶排序
//将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
List<Integer>[] list = new List[nums.length+1];
for(int key : map.keySet()){
// 获取出现的次数作为下标
int i = map.get(key);
if(list[i] == null){
list[i] = new ArrayList();
}
list[i].add(key);
}
// 倒序遍历数组获取出现顺序从大到小的排列
for(int i = list.length - 1;i >= 0 && res.size() < k;i--){
if(list[i] == null) continue;
res.addAll(list[i]);
}
return res;
}
}哈希表 + 优先队列
使用哈希表统计元素频率： 首先遍历数组，使用哈希表统计每个元素出现的频率。
使用优先队列获取前 K 高频元素： 将哈希表中的元素和对应的频率存入优先队列中。优先队列可以用 JavaScript 中的最小堆来实现。
取出前 K 高频元素： 从优先队列中取出前 K 个元素即可。
var topKFrequent = function (nums, k) {
// Step 1: Count frequency using a hash map
const freqMap = new Map();
nums.forEach(num => {
freqMap.set(num, (freqMap.get(num) || 0) + 1);
});
// Step 2: Create PriorityQueue
const pq = new PriorityQueue((a, b) => a.freq - b.freq);
for (const [num, freq] of hashTable.entries()) {
if (pq.size < k) {
pq.push({ num, freq });
} else if (freq > pq.top().freq) {
pq.pop();
pq.push({ num, freq });
}
}
// Step 3: Collect the result
const result = [];
while (pq.size > 0) {
result.push(pq.pop().num);
}
return result;
};有先队列JavaScript实现（一般使用第三方库）
class PriorityQueue {
constructor() {
this.data = [];
}
enqueue(element) {
this.data.push(element);
this.bubbleUp(this.data.length - 1);
}
dequeue() {
if (this.data.length === 0) return null;
const top = this.data[0];
this.data[0] = this.data[this.data.length - 1];
this.data.pop();
this.sinkDown(0);
return top;
}
size() {
return this.data.length;
}
bubbleUp(index) {
while (index > 0 && this.compare(this.data[Math.floor((index - 1) / 2)], this.data[index])) {
const parentIndex = Math.floor((index - 1) / 2);
[this.data[index], this.data[parentIndex]] = [this.data[parentIndex], this.data[index]];
index = parentIndex;
}
}
sinkDown(index) {
let childIndex = (index * 2) + 1;
while (childIndex < this.data.length) {
const rightChildIndex = childIndex + 1;
if (
rightChildIndex < this.data.length &&
this.compare(this.data[childIndex], this.data[rightChildIndex])
) {
childIndex = rightChildIndex;
}
if (this.compare(this.data[index], this.data[childIndex])) {
return;
}
[this.data[index], this.data[childIndex]] = [this.data[childIndex], this.data[index]];
index = childIndex;
}
}
compare(a, b) {
return a.count < b.count; // 降序排列
}
}根据字符出现频率排序
给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案，返回其中任何一个。
示例 1: 输入: s = "tree" 输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2: 输入: s = "cccaaa" 输出: "cccaaa"
解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起
优先队列
使用哈希表 s_dict 统计字符频率。
然后遍历哈希表 s_dict，将字符以及字符频数存入优先队列中。
将优先队列中频数最高的元素依次加入答案数组中。
最后拼接答案数组为字符串，将其返回。
function sortCharactersByFrequency(str) {
const hashTable = new Map();
for (const char of str) {
hashTable.set(char, hashTable.get(char) || 0) + 1;
}
const priorityQueue = new PriorityQueue((a, b) => b.count - a.count);
for (const [char, count] of hashTable.entries()) {
priorityQueue.enqueue({ char, count });
}
let result = "";
while (priorityQueue.size()) {
const { char } = priorityQueue.dequeue();
result += char;
}
return result;
}滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1： 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]
这个和直接滑动窗口是不一样的（回忆一下《双指针：对撞/快慢/分离/滑动窗口的案例(数组/回文/求和等) 》），这个是是如何求一个区间里的最大值呢？
此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值。
function maxSlidingWindow(nums, k) {
if (k > nums.length) return [];
const pq = new PriorityQueue((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length; i++) {
pq.enqueue(nums[i]);
if (pq.size() > k) {
pq.dequeue();
}
if (i >= k - 1) {
result.push(pq.top());
}
}
return result;
}使用优先队列求上面的解，代码非常简洁。
参考文章：
https://algo.itcharge.cn/04.Queue/02.Priority-Queue/01.Priority-Queue/
https://programmercarl.com/0239.滑动窗口最大值.html
转载本站文章《队列集训：科普队列概念与leetcode相关题目精讲》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9102.html