数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究如何使用数组和泛型在 Java 中实现队列？
队列是一种重要的数据结构，其工作原理是先进先出 (FIFO)，即先进入的元素先被移除。对于 Java 来说，通过数组创建队列并使用泛型可以提供适应性和通用性。通过整合泛型，我们可以轻松创建容纳任何类型数据的队列，而利用数组则为内存高效存储创建了一个封闭的空间。
结合各种特性有助于设计一个强大的队列。本文讨论了如何在 Java 中使用数组和泛型来实现队列，同时探讨了底层概念和代码结构。
数组
数组是一种在 Java 编程中用于存储一系列元素的数据结构，这些元素的性质和大小相同。这种数据结构使得在单个变量名下高效地管理和访问值集合变得轻而易举。在 Java 中，声明数组遵循以下语法
datatype[] arrayName;
在使用数组时，“数据类型”指定将存储在数组中的元素类型，例如 int 或 String。同时，要声明数组变量，应在变量名后面包含方括号 []。
在 Java 中声明数组后，可以使用不同的方法对其进行初始化和赋值，但不能更改其长度，因为长度是固定的，并在创建时定义。一些初始化选项包括使用 new 运算符或使用预定义元素进行初始化。
方法
有多种方法可以使用数组和泛型在 Java 中实现队列。让我们探索两种常见的方法
固定大小数组方法
动态调整大小数组方法
固定大小数组方法
在这种方法中，队列的元素存储在一个固定大小的数组中。入队时，在递增后索引后将元素添加到尾部索引。出队涉及递增前端索引并返回元素。
但是，如果额外的入队操作导致元素数量等于数组的大小，则会抛出异常，因为此时队列被视为已满。此技术提供了一个简单的实现，但它也存在限制，因为它限制了可以包含的元素数量 - 不能超过数组的最大大小。
算法
使用固定大小的数组、前端索引、尾部索引和大小计数器初始化队列。
入队
检查队列是否已满。
如果未满，则递增尾部索引并在该位置添加元素。
更新大小计数器。
出队
检查队列是否为空。
如果未空，则访问前端索引处的元素。
递增前端索引并更新大小计数器。
返回元素。
窥视：返回前端索引处的元素，但不将其移除。
通过将大小计数器与零进行比较来检查队列是否为空。
通过将大小计数器与数组大小进行比较来检查队列是否已满。
通过返回大小计数器获取队列的大小。
示例
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 顺序管理元素。数组可用于实现，非常适合小型数据集，但由于其固定大小的方法，无法扩展到大型数据集。为了克服这一挑战，动态调整大小的数组允许队列随着添加更多元素而动态增长，从而在存储容量方面没有限制地容纳更多元素。
正确的方法取决于特定的应用程序需求，需要在固定大小约束和动态调整大小功能之间进行权衡。
1K+ 浏览量
