Java-資料結構系列三：數組模拟環形隊列，實作數組複用

1.背景：數組實作隊列存在的問題：隊列中資料取出後，其指向的空間無法再加入新的資料，會造成空間的浪費，是以需要對數組模拟隊列進行優化；https://blog.csdn.net/money_yao/article/details/99294442

2.環形隊列思路：

• front變量指向隊列的第一個元素，初始值為0；
• rear變量指向隊列最有一個元素的後一個位置，空出一個空間作為約定，初始值為0；
• 隊列滿時的條件為：(rear+1)%maxSize==front
• 隊列空的條件為：rear=front
• 隊列中有效資料的個數（用于列出隊列中資料）：（rear+maxSize-front)%maxSize

3.代碼實作：

package queue;

import java.util.Scanner;

public class CircleArrayQueue {

	public static void main(String[] args) {
		System.out.println("測試環形隊列");
		CircleArray queue=new CircleArray(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) {
					System.out.println(e.getMessage());
				}
				break;
			case 'h':
				try {
					int res=queue.headQueue();
					System.out.printf("隊列頭的資料是%d\n", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				scanner.close();
				loop=false;
				break;
			default:
				break;
			}	
		}
		System.out.println("程式退出");
	}
}
class CircleArray{
	private int maxSize;
	private int front;//front指向隊列的第一個元素，初始值為0
	private int rear;//指向隊列的最後一個元素的後一個位置，空出一個位置空間，初始值為0
	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指向隊列的第一個元素，先把front對應的值儲存到一個臨時變量，之後将front後移，再将臨時儲存的變量傳回
		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() {
		return (rear+maxSize-front)%maxSize;
	}
	//顯示隊列的頭元素
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("隊列為空，無法顯示隊列第一個元素");
		}
		return arr[front];
	}
}
           

4.注意考慮環形隊列，在front和rear後移的時候，需要對其進行取模運算，否則出現下标越界的error。