資料結構
網路
關係型資料庫管理系統
作業系統
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+ 瀏覽量
