Java队列实现：基于数组的循环队列详解178

Java中队列是一种常用的数据结构，遵循先进先出（FIFO）的原则。虽然Java提供了``接口以及多种队列实现，例如`LinkedList`和`PriorityQueue`，但理解队列的底层实现原理对于深入掌握数据结构和算法至关重要。本文将深入探讨如何使用数组来实现一个高效的循环队列，并分析其优缺点以及与其他队列实现的比较。

传统的数组实现队列，会在入队和出队操作时频繁移动元素，导致效率低下。而循环队列通过巧妙地利用数组的循环特性，避免了这种低效的元素移动。它将数组视为一个环形结构，当到达数组末尾时，下一个位置回到数组开头。这样，即使队列已满，仍然可以继续入队，只要还有空闲空间。

下面是一个基于数组的循环队列的Java实现：```java
public class ArrayQueue {
private T[] data;
private int front; // 队头索引
private int rear; // 队尾索引
private int size; // 队列大小
private int capacity; // 队列容量
public ArrayQueue(int capacity) {
= capacity;
= (T[]) new Object[capacity];
= 0;
= 0;
= 0;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public void enqueue(T element) {
if (isFull()) {
throw new IllegalStateException("Queue is full");
}
data[rear] = element;
rear = (rear + 1) % capacity; // 循环移动队尾指针
size++;
}
public T dequeue() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
T element = data[front];
front = (front + 1) % capacity; // 循环移动队头指针
size--;
return element;
}
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return data[front];
}
public int size() {
return size;
}
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(5);
(1);
(2);
(3);
("Queue size: " + ()); // Output: 3
("Dequeued element: " + ()); // Output: 1
("Queue size: " + ()); // Output: 2
(4);
(5);
("Queue size: " + ()); // Output: 4
("Peek element: " + ()); // Output: 2
//测试循环
(6);
("Queue size: " + ()); //Output 5
("Dequeued element: " + ()); //Output 2
("Dequeued element: " + ()); //Output 3
("Dequeued element: " + ()); //Output 4
("Dequeued element: " + ()); //Output 5
("Dequeued element: " + ()); //Output 6
// (); // Throws NoSuchElementException
}
}
```