数据结构与算法 / 系统课时

队列

队列

队列从一端加入元素,从另一端删除,遵循先进先出。固定容量循环队列用下标回绕来复用出队后留下的位置,入队和出队无需搬移其余元素。

学习目标

  • 用 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。每次核心操作做固定数量的操作,时间为 Θ(1)\Theta(1)。初始分配占 Θ(C)\Theta(C) 空间,其中 CC 是容量;遍历或打印取决于当前元素数。 Java Queue 方法约定

Java 17 可运行示例

将代码保存为 CircularQueueDemo.java。执行 javac -encoding UTF-8 --release 17 CircularQueueDemo.java,再执行 java CircularQueueDemo。

java
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();
    }
}
text
入队后: [10, 20, 30]
出队: 10
发生回绕后: [20, 30, 40, 50]
满时写入成功: false
队首: 20
依次出队: 20 30 40 50

出队后,旧值可能仍在底层整数数组中,但它已不在有效区域。这里存的是基本类型,不会持有被移除对象的引用。实现对象队列时,应考虑清除出队槽位以免继续持有对象。遍历按 next 每步回绕,无需先将 head 和偏移相加。

本课练习

把容量改成 1,多次交替入队和出队。再验证队满拒绝写入后,现有元素与 FIFO 顺序都未改变。并发生产者和消费者还需要同步和明确的阻塞或拒绝策略,可参考 Java 的 BlockingQueue。下一课在两端都支持写入和删除。 Java BlockingQueue

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

队列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通