1. 引言在计算机科学中队列Queue是一种基础且重要的数据结构遵循先进先出FIFO的原则。双端队列Deque和单调队列Monotonic Queue是队列的两种重要变体它们在算法设计与问题求解中扮演着关键角色。本文将深入探讨这三种数据结构的核心概念、实现原理、典型应用场景以及它们之间的区别与联系。2. 队列Queue2.1 基本概念队列是一种线性数据结构元素从一端队尾加入从另一端队首移除。这种操作模式使其成为模拟现实世界排队场景的理想选择。2.2 核心操作入队Enqueue在队尾添加元素。出队Dequeue从队首移除并返回元素。查看队首Peek/Front返回队首元素但不移除。判空IsEmpty检查队列是否为空。获取大小Size返回队列中元素的数量。2.3 实现方式队列可以通过数组或链表实现// 基于数组的循环队列实现示例 public class ArrayQueue { private int[] data; private int front; private int rear; private int capacity; public ArrayQueue(int k) { capacity k 1; // 多留一个空间用于区分空和满 data new int[capacity]; front 0; rear 0; } public boolean enqueue(int value) { if (isFull()) return false; data[rear] value; rear (rear 1) % capacity; return true; } public boolean dequeue() { if (isEmpty()) return false; front (front 1) % capacity; return true; } public int front() { if (isEmpty()) return -1; return data[front]; } public boolean isEmpty() { return front rear; } public boolean isFull() { return (rear 1) % capacity front; } }2.4 应用场景广度优先搜索BFS算法任务调度系统消息队列如 RabbitMQ、Kafka 的生产者-消费者模型打印任务管理3. 双端队列Deque3.1 基本概念双端队列Deque全称 Double-Ended Queue允许在队列的两端进行插入和删除操作。它结合了栈Stack和队列Queue的特性提供了更大的灵活性。3.2 核心操作前端操作addFirst() / offerFirst(), removeFirst() / pollFirst(), getFirst() / peekFirst()后端操作addLast() / offerLast(), removeLast() / pollLast(), getLast() / peekLast()3.3 Java 中的实现Java 的java.util.Deque接口及其实现类如ArrayDeque、LinkedList提供了完整的双端队列功能import java.util.ArrayDeque; import java.util.Deque; public class DequeExample { public static void main(String[] args) { // 创建双端队列 DequeString deque new ArrayDeque(); // 前端操作 deque.addFirst(First); deque.offerFirst(Front); // 后端操作 deque.addLast(Last); deque.offerLast(Back); System.out.println(Deque: deque); // [Front, First, Last, Back] // 移除操作 String front deque.removeFirst(); // 移除 Front String back deque.removeLast(); // 移除 Back System.out.println(After removal: deque); // [First, Last] } }3.4 应用场景滑动窗口问题实现栈和队列两种数据结构回文字符串检查撤销操作Undo功能的实现4. 单调队列Monotonic Queue4.1 基本概念单调队列是一种特殊的双端队列它维护队列中元素的单调性递增或递减。在元素入队时会移除破坏单调性的元素从而保证队列头部始终是当前窗口的最值。4.2 核心特性单调性队列中的元素保持单调递增或递减时效性过期的元素超出窗口范围会被移除高效性每个元素最多入队和出队一次均摊时间复杂度为 O(1)4.3 实现原理单调队列通常用于解决滑动窗口最值问题。以下是维护单调递减队列的 Java 实现import java.util.ArrayDeque; import java.util.Deque; public class MonotonicQueue { // 单调递减队列队首始终是当前窗口的最大值 private DequeInteger deque new ArrayDeque(); // 入队操作移除所有小于当前值的元素保持递减 public void push(int val) { while (!deque.isEmpty() deque.peekLast() val) { deque.pollLast(); } deque.offerLast(val); } // 出队操作如果队首元素等于给定值则移除 public void pop(int val) { if (!deque.isEmpty() deque.peekFirst() val) { deque.pollFirst(); } } // 获取当前最大值 public int max() { return deque.peekFirst(); } // 滑动窗口最大值问题解决方案 public static int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0) return new int[0]; int n nums.length; int[] result new int[n - k 1]; MonotonicQueue mq new MonotonicQueue(); // 初始化第一个窗口 for (int i 0; i k; i) { mq.push(nums[i]); } result[0] mq.max(); // 滑动窗口 for (int i k; i n; i) { mq.pop(nums[i - k]); // 移除窗口左侧元素 mq.push(nums[i]); // 添加窗口右侧元素 result[i - k 1] mq.max(); } return result; } }4.4 典型应用滑动窗口最大值/最小值LeetCode 239 题下一个更大元素LeetCode 496、503 题股票价格跨度LeetCode 901 题队列的最大值剑指 Offer 59-II5. 三种队列的对比分析特性队列Queue双端队列Deque单调队列Monotonic Queue操作位置一端入另一端出两端都可入队和出队两端操作但保持单调性数据结构特性FIFO先进先出结合了栈和队列的特性元素具有单调顺序时间复杂度入队/出队 O(1)两端操作均为 O(1)均摊 O(1)主要应用BFS、任务调度滑动窗口、回文检查滑动窗口最值、单调栈问题Java 实现LinkedList, PriorityQueueArrayDeque, LinkedList通常基于 Deque 自定义实现6. 实战案例使用单调队列解决实际问题6.1 问题描述滑动窗口最大值给定一个整数数组 nums 和一个整数 k有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。返回每个窗口中的最大值。6.2 解决方案public class SlidingWindowMaximum { public int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0) return new int[0]; int n nums.length; int[] result new int[n - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 移除超出窗口范围的元素 if (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } // 维护单调递减队列 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 添加当前元素索引 deque.offerLast(i); // 记录窗口最大值 if (i k - 1) { result[i - k 1] nums[deque.peekFirst()]; } } return result; } public static void main(String[] args) { SlidingWindowMaximum solution new SlidingWindowMaximum(); int[] nums {1, 3, -1, -3, 5, 3, 6, 7}; int k 3; int[] result solution.maxSlidingWindow(nums, k); // 输出: [3, 3, 5, 5, 6, 7] System.out.println(Arrays.toString(result)); } }6.3 复杂度分析时间复杂度O(n)每个元素最多入队和出队一次空间复杂度O(k)队列最多存储 k 个元素7. 总结队列、双端队列和单调队列是算法竞赛和工程实践中不可或缺的数据结构。理解它们的特性和应用场景能够帮助我们更高效地解决各类问题队列是基础数据结构适用于需要 FIFO 顺序的场景双端队列提供了更大的灵活性是许多高级算法的基础单调队列是解决滑动窗口最值问题的利器时间复杂度优异在实际开发中应根据具体需求选择合适的数据结构。对于 Java 开发者熟练掌握ArrayDeque和LinkedList的实现特性能够写出更高效的代码。