数据结构与算法 / 系统课时
队列
队列
队列从一端加入元素,从另一端删除,遵循先进先出。固定容量循环队列用下标回绕来复用出队后留下的位置,入队和出队无需搬移其余元素。
学习目标
- 用
head、tail和size描述固定容量队列。 - 区分空、满和回绕,并约定操作失败时的行为。
- 对照队首顺序验证循环数组,区分容量与当前元素数。
三个状态量如何配合
head 指向下一个可读元素的位置,空时没有可读元素。tail 指向下一次可写的下标,满时不得使用它覆盖旧元素。size 在 0 和容量之间。对任意有效元素,从 head 沿循环数组前进,读取 size 个位置即可得到 FIFO 顺序。逻辑上 tail 与 head+size 按容量同余,因此空和满都可能出现 head==tail。

| 操作 | 成功时 | 边界 |
|---|---|---|
offer(value) |
写入、后移 tail,并返回 true |
满时返回 false,不改变状态 |
remove() |
从 head 取出,前移 head |
空时抛 NoSuchElementException |
element() |
查看队首,不更改状态 | 空时抛 NoSuchElementException |
命名参考 Java Queue 的契约,本例只是一个专用整数类。通用接口中,poll() 和 peek() 可在队列为空时返回 null,本例用抛异常的 remove()、element() 保持返回类型为 int。每次核心操作做固定数量的操作,时间为 。初始分配占 空间,其中 是容量;遍历或打印取决于当前元素数。 Java Queue 方法约定
Java 17 可运行示例
将代码保存为 CircularQueueDemo.java。执行 javac -encoding UTF-8 --release 17 CircularQueueDemo.java,再执行 java CircularQueueDemo。
import java.util.NoSuchElementException;
public class CircularQueueDemo {
static final class IntCircularQueue {
private final int[] elements;
private int head;
private int tail;
private int size;
IntCircularQueue(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("capacity must be positive");
}
elements = new int[capacity];
}
private int next(int index) {
return index == elements.length - 1 ? 0 : index + 1;
}
boolean offer(int value) {
if (size == elements.length) {
return false;
}
elements[tail] = value;
tail = next(tail);
size++;
return true;
}
int element() {
if (size == 0) {
throw new NoSuchElementException("queue is empty");
}
return elements[head];
}
int remove() {
int value = element();
head = next(head);
size--;
return value;
}
int size() {
return size;
}
@Override
public String toString() {
StringBuilder text = new StringBuilder("[");
int index = head;
for (int count = 0; count < size; count++) {
if (count > 0) {
text.append(", ");
}
text.append(elements[index]);
index = next(index);
}
return text.append("]").toString();
}
}
public static void main(String[] args) {
IntCircularQueue queue = new IntCircularQueue(4);
queue.offer(10);
queue.offer(20);
queue.offer(30);
System.out.println("入队后: " + queue);
System.out.println("出队: " + queue.remove());
queue.offer(40);
queue.offer(50);
System.out.println("发生回绕后: " + queue);
System.out.println("满时写入成功: " + queue.offer(60));
System.out.println("队首: " + queue.element());
System.out.print("依次出队:");
while (queue.size() > 0) {
System.out.print(" " + queue.remove());
}
System.out.println();
}
}入队后: [10, 20, 30]
出队: 10
发生回绕后: [20, 30, 40, 50]
满时写入成功: false
队首: 20
依次出队: 20 30 40 50出队后,旧值可能仍在底层整数数组中,但它已不在有效区域。这里存的是基本类型,不会持有被移除对象的引用。实现对象队列时,应考虑清除出队槽位以免继续持有对象。遍历按 next 每步回绕,无需先将 head 和偏移相加。
本课练习
把容量改成 1,多次交替入队和出队。再验证队满拒绝写入后,现有元素与 FIFO 顺序都未改变。并发生产者和消费者还需要同步和明确的阻塞或拒绝策略,可参考 Java 的 BlockingQueue。下一课在两端都支持写入和删除。 Java BlockingQueue