環形隊列
- 數組模拟隊列的優化,充分利用數組. 是以将數組看做是一個環形的。(通過取模的方式來實作即可)
優化思路
- front變量的含義做一個調整:front就指向隊列的第一個元素,也就是說arr[front]就是隊列的第一個元素,front的初始值為0
- rear變量的含義做一個調整:rear指向隊列的最後一個元素的後一個位置,因為希望留出一個空間做為約定,隊列的有效資料個數為maxsize-1,rear的初始值為0
- 此前隊列滿時,條件是
,調整過後,條件變為rear == maxSize - 1
(rear+1)%maxSize == front
- 當隊列尾空時,條件為
rear == front
- 這樣調整之後,隊列中有效的資料的個數
(rear + maxSize - front) % maxSize
- 根據以上思路進行修改後,就可以得到一個環形隊列
環形隊列的Java實作
package com.jason.queue;
import java.util.Scanner;
public class CircleArrayQueueDemo {
public static void main(String[] args) {
// 測試隊列
System.out.println("測試環形隊列:");
// 建立一個環形隊列
CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4);
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':
circleArrayQueue.showQueue();
break;
case 'e':
scanner.close();
loop = false;
break;
case 'a':
System.out.println("請輸入一個數");
int n = scanner.nextInt();
circleArrayQueue.addQueue(n);
break;
case 'g':
try {
int res = circleArrayQueue.getQueue();
System.out.printf("取出的資料為%d\n",res);
} catch (Exception e){
e.printStackTrace();
}
break;
case 'h':
try {
int res = circleArrayQueue.headQueue();
System.out.printf("隊列頭的資料為%d\n",res);
} catch (Exception e){
e.printStackTrace();
}
break;
default:
break;
}
}
System.out.println("程式退出");
}
}
class CircleArrayQueue {
private int maxSize; //表示隊列的最大容量
private int front; //隊列頭
private int rear; //隊列尾
private int[] arr; //該數組用于存放資料,模拟隊列
public CircleArrayQueue (int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
}
// 判斷隊列是否已滿
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 判斷隊列是否為空
public boolean isEmpty() {
return front == rear;
}
// 添加資料到隊列,入隊列
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 temp = arr[front];
front = (front + 1) % maxSize;
return temp;
}
// 顯示隊列的所有資料
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() {
return (rear + maxSize - front) % maxSize;
}
// 顯示隊列的頭資料,不是取出資料
public int headQueue() {
//判斷是否已空,若空則提示無資料
if (isEmpty()) {
// 通過抛出異常來傳回
throw new RuntimeException("隊列已空,無法取出資料");
}
return arr[front];
}
}