Java队列深度解析：从集合框架到自定义实现

概述

本文将系统梳理Java在队列（Queue）方面的能力。首先，我们深入探讨Java集合框架中队列的基础知识。

接着，我们分析Java集合框架中固定大小队列的实现方案。最后，我们将亲手实现一个固定大小的队列。

Java集合框架中的队列

Java集合框架提供了多种队列实现，可根据具体需求灵活选用：

需要线程安全实现？选择ConcurrentLinkedQueue
需要自定义元素排序规则？使用PriorityQueue

集合框架内置了几种固定大小队列实现：

ArrayBlockingQueue
- 基于固定数组的FIFO有界队列
- 创建后容量不可修改
LinkedBlockingQueue
- 同样是FIFO队列，但支持可选边界
- 未设置容量时上限为Integer.MAX_VALUE
- 非并发环境下，链表队列比数组队列吞吐量更高
LinkedBlockingDeque
- 注意：该类实现了Deque接口而非单纯的Queue接口

尽管框架提供了丰富实现，但实际开发中我们可能需要自定义队列以满足特殊需求。

Java中的Queue接口

为更好理解后续示例，我们先深入Queue接口。该接口继承自Collection接口，并扩展了特定的插入、提取和检查操作。每类操作都提供两种形式：失败时抛出异常或返回特殊值。

插入操作

boolean add(E e);
boolean offer(E e);

两者都在队列尾部插入元素（队列未满时）。区别在于：

offer() 队列满时返回false
add() 队列满时抛出IllegalStateException

提取操作

E remove();
E poll();

均返回并移除队列头部元素：

poll() 队列空时返回null
remove() 队列空时抛出NoSuchElementException

检查操作

E element();
E peek();

注意所有方法中的泛型E，这表明Queue接口是泛型的：

public interface Queue<E> extends Collection<E> {
    // ...
}

固定大小FIFO队列实现：队列满时移除最旧元素

现在我们实现一个固定大小的FIFO队列，队列满时自动移除最旧元素。命名为FifoFixedSizeQueue。

继承AbstractQueue抽象类是个明智选择，它已实现FIFO队列的核心逻辑和大部分接口方法。

我们用数组存储元素，使用Object数组支持任意类型，并用count记录元素数量：

public class FifoFixedSizeQueue<E> extends AbstractQueue<E> {
    final Object[] items;
    int count;

    public FifoFixedSizeQueue(int capacity) {
        super();
        
        items = new Object[capacity];
        count = 0;
    }
    
    ...
}

构造函数初始化数组和计数器。初始状态下数组元素均为null，count为0。

接下来实现所有抽象方法：

offer()方法实现

核心规则：元素必须插入成功，队列满时先移除最旧元素。同时禁止插入null元素：

public boolean offer(E e) {
    if (e == null) {
        throw new NullPointerException("Queue doesn't allow nulls");
    }
    if (count == items.length) {
        this.poll();
    }
    this.items[count] = e;
    count++;
    return true;
}

实现步骤：

拒绝null元素：

if (e == null) {
 throw new NullPointerException("Queue doesn't allow nulls");
}

队列满时移除头部元素：

while (count >= items.length) {
 this.poll();
}

插入新元素并更新计数：
```
this.items[count] = e;
count++;
```

poll()方法实现

队列空时返回null，否则移除并返回头部元素：

@Override
public E poll() {
    if (count <= 0) {
        return null;
    }
    E item = (E) items[0];
    shiftLeft();
    count--;
    return item;
}

关键逻辑：

空队列检查：
```
if (count <= 0) {
 return null;
}
```
保存头部元素并左移剩余元素：
```
E item = (E) items[0];
shiftLeft();
```
更新计数并返回元素

辅助方法*shiftLeft()*实现：

private void shiftLeft() {
    int i = 1;
    while (i < items.length) {
        if (items[i] == null) {
            break;
        }
        items[i - 1] = items[i];
        i++;
    }
}

从第二个元素开始，逐个向左移动一位，直到遇到null或数组末尾。

peek()方法实现

与*poll()*类似但不移除元素：

public E peek() {
    if (count <= 0) {
        return null;
    }
    return (E) items[0];
}

总结

本文系统梳理了Java集合框架中的队列实现，分析了内置的固定大小队列方案，并演示了如何自定义队列实现。实际开发中，根据场景选择合适实现或进行定制化开发，能有效提升代码质量。

完整代码见GitHub仓库。

Persistence

REST

Security

概述