在 Devin 中试用 DeepWiki 处理私有仓库
DeepWiki

TheAlgorithms/Java

菜单

队列实现

相关源文件

本文档详细介绍了 The Algorithms Java 仓库中的队列数据结构实现。队列是遵循先进先出（FIFO）原则的基础数据结构，其中元素从队尾添加，从队头移除。该仓库提供了多种队列实现，它们具有不同的底层机制和性能特征。

队列实现概述

该仓库提供了两种主要的队列实现

  1. CircularQueue - 一种基于数组的实现，通过循环利用空间来高效利用内存
  2. LinkedQueue - 一种基于链表的实现，提供动态大小分配

这些实现展示了队列抽象数据类型的不同方法，每种方法都有其自身的优点和权衡。

来源：src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java

队列操作

两种队列实现都支持具有相似语义的标准队列操作

操作描述CircularQueueLinkedQueue
入队（Enqueue）向队尾添加元素enQueue(T value)enqueue(T data)
出队（Dequeue）从队头移除元素deQueue()dequeue()
查看查看队头元素peek()peekFront()
大小获取元素数量size()size()
是否为空检查队列是否为空isEmpty()isEmpty()
清空移除所有元素deleteQueue()clear()

来源：src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java55-137 src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java39-175

循环队列（CircularQueue）实现

循环队列（CircularQueue）使用固定大小的数组实现队列，具有循环环绕行为。这种方法通过在元素出队后重用数组中的位置来高效利用空间。

内部结构

循环队列（CircularQueue）的工作原理

循环队列（CircularQueue）使用两个指针来跟踪队列的头部和尾部

  • beginningOfQueue - 指向队头元素（元素出队的位置）
  • topOfQueue - 指向队尾元素（元素入队的位置）

当元素添加或移除时，这些指针在到达数组末尾时会“循环环绕”，从而产生循环行为。

关键操作

  1. 入队操作:

    • 检查队列是否已满
    • 更新 topOfQueue（如有必要则循环）
    • 在新位置添加元素
    • 增加大小计数器

  2. 出队操作:

    • 检查队列是否为空
    • 检索 beginningOfQueue 位置的元素
    • 更新 beginningOfQueue（如有必要则循环）
    • 减少大小计数器
    • 返回被移除的元素

  3. 循环行为：环绕通过模运算实现：(index + 1) % size。

来源：src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java25-48 src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java74-105

链式队列（LinkedQueue）实现

链式队列（LinkedQueue）使用链表结构实现队列，其中每个元素引用队列中的下一个元素。这种方法允许在添加和移除元素时动态调整大小。

内部结构

链式队列（LinkedQueue）的工作原理

链式队列（LinkedQueue）维护着链表的头部和尾部节点的引用

  • front - 指向第一个节点（元素出队的位置）
  • rear - 指向最后一个节点（元素入队的位置）

关键操作

  1. 入队操作:

    • 创建一个带有提供数据的新节点
    • 如果队列为空，则将 front 和 rear 都设置为新节点
    • 否则，将当前的 rear 链接到新节点并更新 rear
    • 增加大小计数器

  2. 出队操作:

    • 检查队列是否为空
    • 从 front 节点检索数据
    • 将 front 更新为下一个节点
    • 如果队列变空，也同时将 rear 设置为 null
    • 减少大小计数器
    • 返回被移除的元素

  3. 附加功能:

    • 通过 Iterator 接口支持队列元素的迭代
    • 提供 peekRear() 方法以查看最后一个元素
    • 通过 peek(int pos) 提供位置访问

来源：src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java6-22 src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java49-85

实现对比

时间复杂度

操作CircularQueueLinkedQueue
入队（Enqueue）O(1)O(1)
出队（Dequeue）O(1)O(1)
查看O(1)O(1)
位置访问O(1)O(n)

空间和特性

功能CircularQueueLinkedQueue
内存分配静态（创建时固定）动态（按需增长）
空间效率可能在未充分利用的数组中浪费空间仅使用实际元素所需的空间
容量限制固定最大容量无限制（受可用内存限制）
迭代支持没有内置迭代器实现 Iterable 接口
额外操作仅支持基本队列操作支持查看队尾和特定位置的元素

来源：src/main/java/com/thealgorithms/datastructures/queues/CircularQueue.java src/main/java/com/thealgorithms/datastructures/queues/LinkedQueue.java

使用示例

循环队列（CircularQueue）示例

来源：src/test/java/com/thealgorithms/datastructures/queues/CircularQueueTest.java12-32 src/test/java/com/thealgorithms/datastructures/queues/CircularQueueTest.java107-121

链式队列（LinkedQueue）示例

来源：src/test/java/com/thealgorithms/datastructures/queues/LinkedQueueTest.java36-54 src/test/java/com/thealgorithms/datastructures/queues/LinkedQueueTest.java72-91 src/test/java/com/thealgorithms/datastructures/queues/LinkedQueueTest.java126-137

何时使用哪种实现

何时使用循环队列（CircularQueue）

  • 你需要一个具有固定预设最大容量的队列时
  • 内存效率很重要，并且你想重用空间时
  • 你需要对队列中任何位置进行常数时间访问时
  • 你正在实现一个有界缓冲区或循环缓冲区模式时

何时使用链式队列（LinkedQueue）

  • 你需要一个可以动态增长而没有预设容量的队列时
  • 你需要遍历队列元素时
  • 你需要访问队列两端时
  • 你需要基于位置访问元素（尽管这是 O(n) 时间）时
  • 节点指针的内存开销可以接受时

队列的应用

队列是许多算法和系统中使用的基本数据结构

  1. 任务调度 - 管理进程的执行顺序
  2. BFS 遍历 - 逐层探索图
  3. 打印作业管理 - 按顺序处理打印请求
  4. 消息队列 - 促进系统组件之间的通信
  5. 缓冲 - 管理进程或系统之间的数据流

来源：src/main/java/com/thealgorithms/datastructures/trees/PrintTopViewofTree.java62-64

实现细节

两种队列实现都妥善处理了边缘情况

  • 空队列操作
  • 满队列操作（针对循环队列）
  • 空元素处理

这些细节可以在验证两种实现正确性的大量测试用例中找到。

来源：src/test/java/com/thealgorithms/datastructures/queues/CircularQueueTest.java79-87 src/test/java/com/thealgorithms/datastructures/queues/LinkedQueueTest.java57-69