數據結構(二)-隊列(對數組的重複利用)
數組模擬隊列
隊列的一個應用場景
銀行叫號排隊的案例
隊列介紹
- 隊列是一個有序列表，可以用數組或鏈表來實現。
- 遵循先入先出的原則。例如：銀行先叫號的人先於後叫號的人辦理業務。誰先叫號誰先辦理，誰後叫號誰後辦理。即：先進入隊列的數據先取出，後進入隊列的數據後取出。
- 示意圖(使用數組模擬隊列示意圖)
數組模擬隊列思路
-
隊列本身是有序列表，若使用數組的結構來存儲隊列的數據，則隊列數組的聲明如上圖，其中， maxSize 為隊列最大容量。
-
隊列的輸出、輸入分別是從隊列的頭部和尾部來處理，因此需要兩個變數 front 和 rear 來記錄隊列前後端的位置。front 隨著數據的取出而改變，rear 隨著數據的輸入而改變。
front：指向隊列的頭部數據的前一個位置
rear：指向隊列的尾部數據 -
當我們將數據存入隊列時稱為”addQueue”，addQueue 有兩個步驟
① 將隊列的尾部指針往後移一位：rear + 1;
② 當 rear == maxSize – 1;則隊列已滿，無法添加數據到隊列中。反之，arr[++rear] = value。注意，添加一個數據只需要隊尾後移一位即可。 -
當我們將數據從隊列中取出時稱為”getQueue”，getQueue 有兩個步驟
① 將隊列的頭部指針後移一位：front + 1;
② 當 front == rear;則隊列為空，沒有數據可取，否則，返回arr[++front]。
程式碼實現
public class ArrayQueueTest {
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(3);
Scanner scanner = new Scanner(System.in);
boolean loop = true;
char selection = ' ';
while(loop) {
System.out.println("s(show)列印隊列");
System.out.println("a(add)添加數據");
System.out.println("g(get)獲取數據");
System.out.println("p(peek)查看隊列的頭部");
System.out.println("q(exit)退出程式");
System.out.print("請輸入你的選擇：");
selection = scanner.next().trim().charAt(0);
switch (selection) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.print("請輸入要添加的數據：");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g':
try {
int value1 = queue.getQueue();
System.out.printf("獲取到的數據為：%d", value1);
System.out.println();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'p':
try {
queue.peek();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'q':
scanner.close();
loop = false;
break;
default:
break;
}
}
}
}
class ArrayQueue{
private int maxSize;
private int front;
private int rear;
private int[] arr;
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
front = -1;
rear = -1;
arr = new int[maxSize];
}
public boolean isFull() {
return rear == maxSize - 1;
}
public boolean isEmpty() {
return front == rear;
}
public void addQueue(int value) {
if(isFull()) {
throw new RuntimeException("隊列已滿，無法添加");
}
arr[++rear] = value;
System.out.println("添加成功");
}
public int getQueue() {
if(isEmpty()) {
throw new RuntimeException("隊列為空~~");
}
return arr[++front];
}
public void showQueue() {
if(isEmpty()) {
System.out.println("隊列為空~~");
}
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
System.out.println();
}
public void peek() {
if(isEmpty()) {
throw new RuntimeException("隊列為空~~");
}
System.out.println(arr[front + 1]);
}
}
數組模擬環形隊列
針對上述數組模擬隊列，在測試的時候發現，當隊列數據已滿時，無法添加數據，但是當取出一個數據時，還是提示隊列已滿。
問題分析並優化
目前數組模擬的隊列的只能使用一次，沒有達到復用的效果。
將這個數組使用一個演算法，改進成 “環形隊列“：取模 %
思路分析1
> 注意
front：在數組模擬環形隊列中指向數組頭部的數據，初始值為0
rear：在數組模擬環形隊列中執行尾部數據的後一位(跟數據模擬隊列有區別)，因為希望空出一個空間作為約定，初始值為0
- 數組模擬隊列之所以不能復用的原因是因為，一旦 rear == maxSize – 1; 就判斷為隊列已滿，但是在數據添加滿之後，這個 rear 在數組模擬隊列中就不會再發生改變，沒有形成一個環形結構。
- 思路就是如何讓這個 rear 在滿了之後還能再回到起點重新來過(操場跑圈)，就需要在rear == maxSize – 1之後，手動將 rear 的值值為 0；front 隨著隊列中數據的取出也會逐漸趨向於 maxSize – 1，所以也需要手動將 front 的值置為0，判斷隊列已滿的條件就是 rear 所處的位置的下一個位置就是 front 所處的位置：即 rear + 1 = front；
- 手動將達到最大值置為0的思路理解起來較容易，實現起來較繁瑣。
思路分析2(取模)
- 首先判斷已滿的條件為(rear + 1) % maxSize == front；maxSize 為數組的長度，而實際隊列存儲數據的個數為 maxSize – 1 個
這樣取模的原因，如果向後面這樣取，rear % maxSize == front；在還沒向隊列添加數據時，則等式成立，無法添加數據
- 判斷為空的條件：rear == front;
- 當我們如上述分析時，這時隊列中的有效數據個數為 (rear + maxSize – front) % maxSize;
+maxSize 的原因，是因為，如果出現 rear 比 front 快一圈的情況(跑圈)，rear – front 就會出現負數，與需求相悖。
程式碼實現
public class CircleArrayQueueTest {
public static void main(String[] args) {
CircleArrayQueue queue = new CircleArrayQueue(4);
Scanner scanner = new Scanner(System.in);
boolean loop = true;
char selection = ' ';
while (loop) {
System.out.println("s(show)列印隊列");
System.out.println("a(add)添加數據");
System.out.println("g(get)獲取數據");
System.out.println("p(peek)查看隊列的頭部");
System.out.println("q(exit)退出程式");
System.out.print("請輸入你的選擇：");
selection = scanner.next().trim().charAt(0);
switch (selection) {
case 's':
queue.showQueue();
int front = queue.getFront();
int rear = queue.getRear();
System.out.printf("front=%d\n", front); // 在列印隊列的時候可以看出front和rear的變化
System.out.printf("rear=%d\n", rear); // 從而可以理解size()函數的寫法
break;
case 'a':
System.out.print("請輸入要添加的數據：");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g':
try {
int value1 = queue.getQueue();
System.out.printf("獲取到的數據為：%d", value1);
System.out.println();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'p':
try {
queue.peek();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'q':
scanner.close();
loop = false;
break;
default:
break;
}
}
}
}
class CircleArrayQueue {
private int maxSize;
private int front; // 指向隊列頭部的數據
private int rear; // 指向隊列尾部的後一個位置，預留一個空位，以方便下面的取余操作
private int[] arr;
public CircleArrayQueue(int maxSize) {// maxSize為數組長度，不是隊列的長度
this.maxSize = maxSize;
arr = new int[maxSize];
}
public boolean isFull() {
// 不寫(rear+1)的話就會出現rear=0;front=0;還沒添加數據就判斷為隊列為滿
return (rear + 1) % maxSize == front; // 隊列實際存儲的數據個數最多為maxSize-1個
}
public boolean isEmpty() {
return front == rear;
}
public void addQueue(int value) {
if (isFull()) {
System.out.println("隊列已滿，無法添加");
return;
}
arr[rear] = value;
rear = (rear + 1) % maxSize; // 防止索引越界
}
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("隊列為空~~");
}
int value = arr[front];
front = (front + 1) % maxSize; // 防止索引越界
return value;
}
public void showQueue() {
if (isEmpty()) {
System.out.println(("隊列為空~~"));
return;
}
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
public int size() {
// 寫rear + maxSize是為了防止出現rear在第二圈，front在第一圈的情況
return (rear + maxSize - front) % maxSize;
}
public void peek() {
if (isEmpty()) {
throw new RuntimeException("隊列為空~~");
}
System.out.println(arr[front]);
}
public int getFront() {
return front;
}
public int getRear() {
return rear;
}
}
本篇隨筆內容是來自於學習尚矽谷韓順平老師的數據結構和演算法課(java版)的筆記，如有整理疏漏或錯誤之處，請大家多多指出
