Java 数组实现队列：高效储存和检索元素171

队列是一种先进先出 (FIFO) 数据结构，这意味着第一个进入队列的元素也是第一个离开队列的元素。Java 中的队列可以通过数组轻松实现，这是一种简单且高效的方法，特别适合需要在快速访问元素方面进行优化的情况。

数组实现队列

要使用数组实现队列，我们需要定义一个数组来存储元素，并跟踪队列的头和尾指针，如下所示：```java
class Queue {
private int[] arr;
private int head;
private int tail;
}
```

在初始化时，head 和 tail 指向数组的开头：```java
public Queue(int size) {
arr = new int[size];
head = 0;
tail = 0;
}
```

入队操作

插入元素（称为入队）的操作涉及将元素添加到数组的尾部并更新 tail 指针：```java
public void enqueue(int element) {
if (isFull()) {
throw new IllegalStateException("Queue is full");
}
arr[tail] = element;
tail = (tail + 1) % ;
}
```

isFull() 方法检查数组是否已满，以防止超出数组范围：```java
private boolean isFull() {
return (tail + 1) % == head;
}
```

出队操作

从队列中移除元素（称为出队）的操作包括从数组的头部读取元素并更新 head 指针：```java
public int dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
int element = arr[head];
head = (head + 1) % ;
return element;
}
```

isEmpty() 方法检查队列是否为空，以防止从空队列中移除元素：```java
private boolean isEmpty() {
return tail == head;
}
```

优势

基于数组的队列提供了以下优势：* 快速访问元素：O(1) 复杂度
* 高效插入和删除元素：O(1) 复杂度
* 空间利用率高：只需要一个数组来存储元素

局限性

基于数组的队列也有一些限制：* 固定大小：数组大小必须在创建时指定，不能动态增长
* 浪费空间：如果队列没有满，数组中会有未使用的元素
* 循环缓冲区：需要处理数组末尾和开头之间的循环

示例

以下是一个使用数组实现队列的示例：```java
public class QueueMain {
public static void main(String[] args) {
Queue queue = new Queue(5);
(1);
(2);
(3);
(4);
(5);
("Queue: " + queue);
int element = ();
("Dequeued element: " + element);
(6);
("Queue after enqueue: " + queue);
}
}
```

输出：```
Queue: 1 2 3 4 5
Dequeued element: 1
Queue after enqueue: 2 3 4 5 6
```

2024-11-14

上一篇：Java 构造方法重写：理解和实务

下一篇：Java 中静态方法的重写