如何使用数组和泛型在 Java 中实现队列?
队列是一种重要的数据结构，其工作原理是先进先出 (FIFO)，即先输入的元素先被移除。对于 Java，通过数组创建队列并使用泛型可以提供适应性和多功能性。通过结合泛型，我们可以轻松创建包含任何数据类型的队列，同时利用数组可以创建一个包含空间以实现高效的内存存储。
结合各种功能有助于设计一个强大的队列。本文讨论了如何使用数组和泛型在 Java 中实现队列，同时探索底层概念和代码结构。
数组
数组是 Java 编程中用于存储性质和大小相似的元素序列的一种数据结构。这种数据结构使得在一个变量名下管理和访问值集合变得毫不费力。在 Java 中，声明数组遵循以下语法:
datatype[] arrayName;
使用数组时，"数据类型"指定将存储在数组中的元素类型，如 int 或 String。同时，要声明数组变量，应在变量名称后包含方括号 []。
在 Java 中声明数组后，可以使用不同的方法对其进行初始化和赋值，但不能更改其长度，长度在创建时是固定和定义的。一些初始化选项包括利用 new 运算符或使用预定义元素对其进行初始化。
方法
有多种方法可以使用数组和泛型在 Java 中实现队列。让我们来探索两种常用方法:
固定大小数组方法
动态调整大小数组方法
固定大小数组方法
在这种方法中，队列的元素存储在固定大小的数组中。入队时，元素在增加后索引后添加到后索引中。出队涉及增加前索引并返回元素。
但是，如果额外的入队操作导致元素数量等于数组的大小，则会引发异常，因为此时队列被视为已满。这种技术提供了一个简单的实现，但也有其局限性，因为它限制了可以包含的元素数量 - 不能超过数组的最大大小。
算法
使用固定大小的数组、前索引、后索引和大小计数器初始化队列。
入队:
检查队列是否已满。
如果队列未满，则增加后索引并在该位置添加元素。
更新大小计数器。
出队:
检查队列是否为空。
如果不为空，则访问前索引处的元素。
增加前索引并更新大小计数器。
返回元素。
Peek:返回前索引处的元素而不将其移除。
通过将大小计数器与零进行比较来检查队列是否为空。
通过将大小计数器与数组大小进行比较来检查队列是否已满。
通过返回大小计数器来获取队列的大小。
示例
import java.util.NoSuchElementException;
public class FixedSizeArrayQueue<T> {
private T[] queueArray;
private int front;
private int rear;
private int size;
public FixedSizeArrayQueue(int capacity) {
queueArray = (T[]) new Object[capacity];
front = 0;
rear = -1;
size = 0;
}
public void enqueue(T item) {
if (isFull()) {
throw new IllegalStateException("Queue is full. Cannot enqueue item.");
}
rear = (rear + 1) % queueArray.length;
queueArray[rear] = item;
size++;
}
public T dequeue() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty. Cannot dequeue item.");
}
T item = queueArray[front];
front = (front + 1) % queueArray.length;
size--;
return item;
}
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty. Cannot peek item.");
}
return queueArray[front];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == queueArray.length;
}
public int size() {
return size;
}
public static void main(String[] args) {
FixedSizeArrayQueue<String> queue = new FixedSizeArrayQueue<>(4);
queue.enqueue("Apple");
queue.enqueue("Banana");
queue.enqueue("Cherry");
System.out.println("Size of the queue: " + queue.size()); // Output: Size of the queue: 3
System.out.println("Front element: " + queue.peek()); // Output: Front element: Apple
String item1 = queue.dequeue();
String item2 = queue.dequeue();
System.out.println("Dequeued items: " + item1 + ", " + item2); // Output: Dequeued items: Apple, Banana
queue.enqueue("Durian");
System.out.println("Is the queue full? " + queue.isFull()); // Output: Is the queue full? false
while (!queue.isEmpty()) {
System.out.println("Dequeued item: " + queue.dequeue());
}
System.out.println("Is the queue empty? " + queue.isEmpty()); // Output: Is the queue empty? true
}
}
输出
Size of the queue: 3 Front element: Apple Dequeued items: Apple, Banana Is the queue full? false Dequeued item: Cherry Dequeued item: Durian Is the queue empty? true
动态调整数组大小的方法
在此方法中，最初使用一个小型数组，随着队列增长并达到数组容量，将创建一个新的更大数组。然后将原始数组中的元素复制到新数组。这允许队列动态调整大小并容纳更多元素。出队涉及增加前端索引并返回元素，而入队将元素附加到数组末尾。此方法在大小方面提供了灵活性，但由于数组大小调整而产生额外开销。
算法
使用小尺寸数组、前索引、后索引和大小计数器初始化队列。
入队:
通过将大小计数器与数组大小进行比较来检查队列是否已满。
如果已满，则创建一个新的更大尺寸的数组并从原始数组中复制元素。
增加后索引并将元素添加到数组中的该位置。
更新大小计数器。
出队:
通过比较大小计数器和数组大小来检查队列是否为空将大小计数器与零进行比较。
如果不为空，则访问前索引处的元素。
增加前索引并更新大小计数器。
返回元素。
Peek:返回前索引处的元素而不将其移除。
通过将大小计数器与零进行比较来检查队列是否为空。
通过将大小计数器与数组大小进行比较来检查队列是否已满。
通过返回大小计数器获取队列的大小。
示例
import java.util.Arrays;
import java.util.NoSuchElementException;
public class DynamicResizingArrayQueue<T> {
private T[] queueArray;
private int front;
private int rear;
private int size;
public DynamicResizingArrayQueue() {
queueArray = (T[]) new Object[4];
front = 0;
rear = -1;
size = 0;
}
public void enqueue(T item) {
if (isFull()) {
resizeArray();
}
rear++;
queueArray[rear] = item;
size++;
}
public T dequeue() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty. Cannot dequeue item.");
}
T item = queueArray[front];
front++;
size--;
if (size < queueArray.length / 2) {
shrinkArray();
}
return item;
}
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty. Cannot peek item.");
}
return queueArray[front];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == queueArray.length;
}
public int size() {
return size;
}
private void resizeArray() {
int newCapacity = queueArray.length * 2;
queueArray = Arrays.copyOf(queueArray, newCapacity);
}
private void shrinkArray() {
int newCapacity = queueArray.length / 2;
queueArray = Arrays.copyOfRange(queueArray, front, front + size, (Class<? extends T[]>) queueArray.getClass());
front = 0;
rear = size - 1;
}
public static void main(String[] args) {
DynamicResizingArrayQueue<Integer> queue = new DynamicResizingArrayQueue<>();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
System.out.println("Size of the queue: " + queue.size()); // Output: Size of the queue: 3
System.out.println("Front element: " + queue.peek()); // Output: Front element: 10
int item1 = queue.dequeue();
int item2 = queue.dequeue();
System.out.println("Dequeued items: " + item1 + ", " + item2); // Output: Dequeued items: 10, 20
queue.enqueue(40);
queue.enqueue(50);
queue.enqueue(60);
System.out.println("Is the queue full? " + queue.isFull()); // Output: Is the queue full? false
while (!queue.isEmpty()) {
System.out.println("Dequeued item: " + queue.dequeue());
}
System.out.println("Is the queue empty? " + queue.isEmpty()); // Output: Is the queue empty? true
}
}
输出
Size of the queue: 3 Front element: 10 Dequeued items: 10, 20 Is the queue full? true Dequeued item: 30 Dequeued item: 40 Dequeued item: 50 Dequeued item: 60 Is the queue empty? true
结论
本教程将介绍如何使用数组和泛型在 Java 中实现队列。它提供了一种灵活的数据结构，可以按 FIFO 顺序管理元素。可以使用数组来实现，数组非常适合小型数据集，但由于其固定大小的方法，因此无法扩展到更大的数据集。为了克服这一挑战，动态调整大小数组允许队列随着更多元素的添加而动态增长，从而可以容纳更多元素，而不受存储容量限制。
正确的方法取决于特定的应用程序要求，需要在固定大小约束和动态调整大小功能之间进行权衡。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/
