基于數組搭建的環形隊列——Java資料結構
說明
本篇部落格介紹的是Java資料結構中,十分重要的一種類型,隊列。在文中我們用數組來模拟搭建一個環形隊列。在提供代碼前,先帶大家了解一下隊列這種資料結構;然後給出搭建環形隊列的思路以及Java代碼。
隊列介紹
- 隊列是一個有序清單,可以用數組或是連結清單來實作。
- 隊列遵循先入先出的原則。即:先存入隊列的資料,要先取出,後存入的資料要後取出
- 隊列本身是有序清單,若使用數組的結構來存儲隊列的資料,則隊列數組的聲明如下圖, 其中 maxSize 是該隊列的最大容量。 因為隊列的輸出、輸入是分别從前後端來處理,是以需要兩個變量 front及 rear分别記錄隊列前後端的下标,front 會随着資料輸出而改變,而 rear則是随着資料輸入而改變,如圖所示:
代碼思路
尾索引的下一個為頭索引時表示隊列滿,即将隊列容量空出一個作為約定,這個在做判斷隊列滿的時候需要注意
(rear + 1) % maxSize == front [表示隊列滿]
rear == front [表示隊列空]
數組實作環形隊列代碼
import java.util.Scanner;
public class CircleArrayQueueDemo {
public static void main(String[] args) {
//測試一把
System.out.println("測試數組模拟環形隊列的案例~~~");
// 建立一個環形隊列
CircleArray queue = new CircleArray(4); //說明設定4, 其隊列的有效資料最大是3
char key = ' '; // 接收使用者輸入
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
// 輸出一個菜單
while (loop) {
System.out.println("s(show): 顯示隊列");
System.out.println("e(exit): 退出程式");
System.out.println("a(add): 添加資料到隊列");
System.out.println("g(get): 從隊列取出資料");
System.out.println("h(head): 檢視隊列頭的資料");
key = scanner.next().charAt(0);// 接收一個字元
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("輸出一個數");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': // 取出資料
try {
int res = queue.getQueue();
System.out.printf("取出的資料是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': // 檢視隊列頭的資料
try {
int res = queue.headQueue();
System.out.printf("隊列頭的資料是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': // 退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程式退出~~");
}
}
class CircleArray {
private int maxSize; // 表示數組的最大容量
//front 變量的含義做一個調整: front 就指向隊列的第一個元素, 也就是說 arr[front] 就是隊列的第一個元素
//front 的初始值 = 0
private int front;
//rear 變量的含義做一個調整:rear 指向隊列的最後一個元素的後一個位置. 因為希望空出一個空間做為約定.
//rear 的初始值 = 0
private int rear; // 隊列尾
private int[] arr; // 該資料用于存放資料, 模拟隊列
public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
}
// 判斷隊列是否滿
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 判斷隊列是否為空
public boolean isEmpty() {
return rear == front;
}
// 添加資料到隊列
public void addQueue(int n) {
// 判斷隊列是否滿
if (isFull()) {
System.out.println("隊列滿,不能加入資料~");
return;
}
//直接将資料加入
arr[rear] = n;
//将 rear 後移, 這裡必須考慮取模
rear = (rear + 1) % maxSize;
}
// 擷取隊列的資料, 出隊列
public int getQueue() {
// 判斷隊列是否空
if (isEmpty()) {
// 通過抛出異常
throw new RuntimeException("隊列空,不能取資料");
}
// 這裡需要分析出 front是指向隊列的第一個元素
// 1. 先把 front 對應的值保留到一個臨時變量
// 2. 将 front 後移, 考慮取模
// 3. 将臨時儲存的變量傳回
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
// 顯示隊列的所有資料
public void showQueue() {
// 周遊
if (isEmpty()) {
System.out.println("隊列空的,沒有資料~~");
return;
}
// 思路:從front開始周遊,周遊多少個元素
// 動腦筋
for (int i = front; i < front + size() ; i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
// 求出目前隊列有效資料的個數
public int size() {
// rear = 2
// front = 1
// maxSize = 3
return (rear + maxSize - front) % maxSize;
}
// 顯示隊列的頭資料, 注意不是取出資料
public int headQueue() {
// 判斷
if (isEmpty()) {
throw new RuntimeException("隊列空的,沒有資料~~");
}
return arr[front];
}
}