数据结构——队列（包括循环队列）——Java版

目录

队列介绍：

基本概念：

应用：

Java实现示例：

循环队列的Java实现：

---

队列介绍：

队列（Queue）是一种常见的数据结构，它按照先进先出（FIFO，First-In-First-Out）的原则管理数据。在现实生活中，队列的概念很容易理解，就像是排队等待服务的人群一样。在计算机科学领域，队列同样扮演着重要的角色，在算法和程序设计中被广泛应用。

基本概念：

1. 入队和出队
队列的两个主要操作是入队（enqueue）和出队（dequeue）。入队指将元素添加到队列的末尾，而出队则是从队列的头部移除一个元素。这两个操作遵循FIFO原则，即先入队的元素会先被出队。

2. 队首和队尾
队列中的第一个元素称为队首（front），而最后一个元素称为队尾（rear）。入队操作会将元素添加到队尾，而出队操作会移除队首元素。

应用：

 1. 算法中的应用
队列在算法中有着广泛的应用，特别是在图的遍历、广度优先搜索（BFS）、迷宫求解等问题中。它们通常用于管理待处理的节点或状态，以确保按照正确的顺序进行处理。

2. 数据结构中的应用
队列可以作为其他数据结构的基础，例如实现线程池、任务调度器、缓冲区等。在这些应用中，队列用于存储待处理的任务或数据，并按照先进先出的顺序进行处理。

Java实现示例：

注意：此队列使用了动态数组可以自动扩容，避免了固定大小数组的限制，如果想用静态数组可以在代码的基础上修改一下，这里我就不展示了

另外，此队列代码实现运用了泛型的相关知识，对泛型还不太了解的小伙伴，可以看一下我下期作品：深入探究Java中的泛型

public class Queue<T> {
    private T[] elements; // 用于存储队列元素的数组
    private int front; // 指向队列头部的指针
    private int rear; // 指向队列尾部的指针
    private int size; // 队列中元素的数量
    private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
    private static final int RESIZE_FACTOR = 2; // 扩容因子
 
    // 构造函数，初始化队列
    public Queue() {
        elements = (T[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = -1;
        size = 0;
    }
 
    // 入队操作，将元素添加到队尾
    public void enqueue(T element) {
        // 检查队列是否需要扩容
        if (size == elements.length) {
            resize();
        }
        // 队尾指针移动并添加元素
        rear = (rear + 1) % elements.length;
        elements[rear] = element;
        size++;
    }
 
    // 出队操作，从队首移除元素并返回
    public T dequeue() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        // 获取队首元素并移动队首指针
        T element = elements[front];
        front = (front + 1) % elements.length;
        size--;
        return element;
    }
 
    // 获取队首元素，但不移除
    public T peek() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return elements[front];
    }
 
    // 检查队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }
 
    // 获取队列大小
    public int size() {
        return size;
    }
 
    // 扩容队列
    private void resize() {
        int newCapacity = elements.length * RESIZE_FACTOR;
        T[] newElements = (T[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[(front + i) % elements.length];
        }
        elements = newElements;
        front = 0;
        rear = size - 1;
    }
}

循环队列的Java实现：

循环利用数组空间： 循环队列通过循环利用数组空间，避免了因队列元素出队导致的空间浪费问题。

入队、出队操作高效： 循环队列的入队和出队操作时间复杂度均为 O(1)，因为它们只涉及修改队尾指针和队首指针，并不需要移动数组元素。

固定大小： 循环队列通常具有固定的大小，一旦初始化后大小不会改变。
 

public class CircularQueue<T> {
    private T[] elements; // 用于存储队列元素的数组
    private int front; // 队列头部指针，指向队首元素
    private int rear; // 队列尾部指针，指向队尾元素的下一个位置
    private int size; // 队列中元素的数量
    private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
 
    // 默认构造函数，创建指定容量的循环队列
    public CircularQueue() {
        elements = (T[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = -1;
        size = 0;
    }
 
    // 带有容量参数的构造函数，创建指定容量的循环队列
    public CircularQueue(int capacity) {
        elements = (T[]) new Object[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }
 
    // 入队操作，将元素添加到队尾
    public void enqueue(T element) {
        // 检查队列是否已满
        if (isFull()) {
            throw new IllegalStateException("队列已满");
        }
        // 计算新的rear位置
        rear = (rear + 1) % elements.length;
        elements[rear] = element;
        size++;
    }
 
    // 出队操作，从队首移除元素并返回
    public T dequeue() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        T element = elements[front];
        // 移动front指针
        front = (front + 1) % elements.length;
        size--;
        return element;
    }
 
    // 获取队首元素，但不移除
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return elements[front];
    }
 
    // 检查队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }
 
    // 检查队列是否已满
    public boolean isFull() {
        return size == elements.length;
    }
 
    // 获取队列大小
    public int size() {
        return size;
    }
}