极客笔记Java 如何使用数组和泛型实现队列
队列是一种重要的数据结构，它遵循先进先出（FIFO）的原则，即先进入的元素先被移除。在Java中，通过使用数组和泛型来创建队列可以提供灵活性和多样性。通过使用泛型，我们可以轻松创建可以容纳任何类型的数据的队列，而使用数组可以创建一个内存高效存储的封闭空间。
通过结合各种特性，有助于设计一个健壮的队列。本文讨论了如何使用数组和泛型在Java中实现队列，同时探讨了底层概念和代码结构。
数组
数组是一种在Java编程中用于存储类似性质和大小的元素序列的数据结构。这种数据结构使得在一个变量名称下轻松管理和访问一组值变得高效。在Java中，声明数组的语法如下：
datatype[] arrayName;
在处理数组时，“datatype”指定了将存储在数组中的元素类型，如int或String。同时，要声明数组变量，需要在变量名后面包含方括号[]。
一旦在Java中声明了数组，就可以使用不同的方法对其进行初始化和赋值，除了改变其长度外（长度在创建时已固定和定义）。一些初始化选项包括使用new运算符或用预定义的元素初始化数组。
方法
有多种使用数组和通用类型实现队列的方法。让我们探索两种常见的方法：
- 固定大小数组方法
-
动态调整大小的数组方法
固定大小数组方法
在这个方法中，队列的元素存储在一个固定大小的数组中。在入队时，将元素添加到后面的索引处并递增索引。出队时，递增前面的索引并返回元素。
然而，如果额外的入队操作导致元素的数量等于数组的大小，那么会抛出异常，因为此时队列被认为是满的。这种技术提供了一个简单的实现，但限制了可以包含的元素数量 – 不能超过数组的最大大小。
步骤
- 用固定大小的数组、前端索引、后端索引和大小计数器初始化队列。
-
入队：
-
检查队列是否已满。
- 如果不满，递增后端索引并在该位置添加元素。
-
更新大小计数器。
-
出队：
- 检查队列是否为空。
-
如果不为空，访问前端索引处的元素。
-
递增前端索引并更新大小计数器。
-
返回元素。
- 查看：返回前端索引处的元素而不移除它。
- 通过将大小计数器与零进行比较来检查队列是否为空。
-
通过将大小计数器与数组大小进行比较来检查队列是否已满。
-
通过返回大小计数器来获取队列的大小。
示例
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
动态调整大小的数组方法
在这种方法中，首先使用一个小尺寸的数组，当队列增长并达到数组容量时，创建一个新的更大尺寸的数组。然后将原始数组中的元素复制到新的数组中。这样可以动态调整队列的大小，容纳更多的元素。出队涉及到递增前面的索引并返回元素，入队将元素追加到数组的末尾。这种方法在大小方面提供了灵活性，但由于数组调整大小而产生了额外的开销。
步骤
- 用小尺寸的数组、前面的索引、后面的索引和计数器初始化队列。
-
入队：
- 通过将计数器与数组大小进行比较来检查队列是否已满。
-
如果已满，则创建一个新的更大尺寸的数组，并将原始数组中的元素复制过来。
-
递增后面的索引，并将元素添加到数组的该位置。
-
更新计数器。
-
出队：
- 通过将计数器与零进行比较来检查队列是否为空。
-
如果不为空，则访问前面索引处的元素。
-
递增前面的索引并更新计数器。
-
返回元素。
-
查看：返回前面索引处的元素，而不移除它。
-
通过将计数器与零进行比较来检查队列是否为空。
-
通过将计数器与数组大小进行比较来检查队列是否已满。
-
通过返回计数器来获取队列的大小。
示例
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的顺序管理元素。可以使用数组来实现队列，对于小型数据集来说非常好，但是对于较大的数据集来说不可扩展，因为数组是具有固定大小的方法。为了克服这个挑战，可以使用动态调整大小的数组，使队列可以随着添加更多元素而动态增长，从而可以容纳更多的元素而不限制存储容量。
正确的方法取决于特定的应用要求，需要在固定大小约束和动态调整大小能力之间进行权衡。