队列（Queue）是一种先进先出（FIFO）的线性数据结构，与栈的 LIFO 特性形成鲜明对比。队列广泛应用于 BFS 广度优先搜索、任务调度、消息传递等场景。本文将从零实现一个基于数组的循环队列，解决普通顺序队列的”假溢出”问题，并重点讲解单调队列技巧——在 O(n) 时间内求解滑动窗口最大值这一经典问题。
数据结构原理
普通顺序队列使用头尾指针管理元素，但当元素出队后，前面的空间无法复用，导致”假溢出”。循环队列通过取模运算将数组逻辑上首尾相连，充分利用每一寸空间。
单调队列是双端队列（Deque）的进阶应用，维护队列内元素的单调递减（或递增）性。通过从队尾移除破坏单调性的元素、从队头移除滑出窗口的元素，保证队首始终是当前窗口的最大值。
Java 实现
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
/**
* 队列完整实现：循环队列与单调队列高级应用
*/
public class QueueDemo {
/**
* 基于数组的循环队列实现
* 解决顺序队列的假溢出问题
*/
static class CircularQueue {
private int[] data;
private int head; // 队首下标
private int tail; // 队尾下一个位置下标
private int size; // 当前元素个数
private int capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
this.data = new int[capacity];
this.head = 0;
this.tail = 0;
this.size = 0;
}
/**
* 入队操作
*
* @param val 待入队元素
* @return true 若入队成功
*/
public boolean enqueue(int val) {
if (isFull()) {
System.out.println("队列已满");
return false;
}
data[tail] = val;
tail = (tail + 1) % capacity; // 循环移动
size++;
return true;
}
/**
* 出队操作
*
* @return 队首元素
*/
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
int val = data[head];
head = (head + 1) % capacity; // 循环移动
size--;
return val;
}
/**
* 查看队首元素
*/
public int front() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return data[head];
}
/**
* 查看队尾元素
*/
public int rear() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
// tail 指向下一个位置，所以队尾在 tail 前一个位置
return data[(tail - 1 + capacity) % capacity];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public int size() {
return size;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
sb.append(data[(head + i) % capacity]);
if (i < size - 1) sb.append(", ");
}
sb.append("]");
return sb.toString();
}
}
/**
* 单调队列应用：滑动窗口最大值
* 给定数组 nums 和窗口大小 k，返回每个滑动窗口中的最大值
*
* 核心思想：维护一个双端队列，队列中保存下标，对应值单调递减
* 1. 入队时，从队尾移除所有值小于等于新元素的旧元素（它们不可能成为最大值）
* 2. 队首元素若已滑出窗口，则移除
* 3. 队首即为当前窗口最大值
*
* @param nums 输入数组
* @param k 窗口大小
* @return 每个窗口的最大值
*/
public static int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> 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;
}
/**
* 单调队列应用：滑动窗口最小值
*
* @param nums 输入数组
* @param k 窗口大小
* @return 每个窗口的最小值
*/
public static int[] minSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> 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 long subArrayRangesSum(int[] nums) {
int n = nums.length;
long sum = 0;
// 对每个元素，计算以它为最大值的所有子数组个数
// 左边界：前一个更大元素的位置；右边界：后一个更大或等于元素的位置
Deque<Integer> stack = new ArrayDeque<>();
int[] left = new int[n];
int[] right = new int[n];
// 左边界：严格大于
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
// 右边界：大于或等于（避免重复计数）
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
stack.pop();
}
right[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
for (int i = 0; i < n; i++) {
long count = (long) (i - left[i]) * (right[i] - i);
sum += nums[i] * count;
}
return sum;
}
public static void main(String[] args) {
// 测试循环队列
CircularQueue cq = new CircularQueue(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
System.out.println("循环队列: " + cq);
System.out.println("出队: " + cq.dequeue());
cq.enqueue(40);
cq.enqueue(50);
cq.enqueue(60);
System.out.println("满队列: " + cq);
System.out.println("队首: " + cq.front() + ", 队尾: " + cq.rear());
// 测试滑动窗口最大值
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
System.out.println("\n原始数组: " + Arrays.toString(nums));
System.out.println("窗口大小: " + k);
System.out.println("滑动窗口最大值: " + Arrays.toString(maxSlidingWindow(nums, k)));
System.out.println("滑动窗口最小值: " + Arrays.toString(minSlidingWindow(nums, k)));
// 测试子数组范围之和
int[] arr = {1, 2, 3};
System.out.println("\n子数组范围之和: " + subArrayRangesSum(arr));
}
}
复杂度分析
| 操作/算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 循环队列 enqueue / dequeue | O(1) | O(1) |
| 滑动窗口最大值 | O(n) | O(k) |
| 滑动窗口最小值 | O(n) | O(k) |
| 子数组范围之和 | O(n) | O(n) |
单调队列的精髓在于：每个元素最多入队和出队各一次，因此整体时间复杂度为线性。这种”每个元素只被处理有限次”的思想是 amortized analysis（摊还分析）的典型应用。
适用场景
循环队列适用于固定缓冲区、生产者-消费者模型、以及任何需要 FIFO 且空间受限的场景。单调队列则广泛应用于：滑动窗口极值问题；股票价格跨度；接雨水问题的双单调栈/队列解法；以及需要维护窗口内元素单调性的各类优化问题。掌握这两种结构，是处理线性数据流问题的重要武器。
