【資料結構與算法】用數組模拟實作環形隊列

在之前的實踐中，已經使用數組實作了隊列，但是其有缺陷，就是數組隻能使用一次，由此提出改進，用數組模拟實作環形隊列

隊列

隊列是一個有序清單，可以用數組或是連結清單來實作

隊列遵循先入先出的原則

隊列的輸出輸入分别從前後端處理，是以需要倆個變量front和rear分别記錄隊列前後端的下标，front會随着資料輸出而改變，而rear則是随着資料輸入而改變

環形隊列

1.front指向隊列的第一個元素，arr[front]是隊列的第一個元素，front的初始值為0

2.rear指向隊列最後一個元素的後一個位置，因為希望空出一個空間做約定，rear的初始值為0

3.隊列滿，(rear+1)%maxSize=front

4.隊列空，rear==front

5.隊列中有效的資料個數，(rear+maxSize-front)%maxSize

基于數組實作環形隊列

class CircleArray{
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;
    public CircleArray(int arrMaxSize){
        maxSize=arrMaxSize;
        front=0;
        rear=0;
        arr=new int[maxSize];
    }
    //判斷隊列為滿
    public boolean isFull(){
        return (rear+1) % maxSize==front;
    }
    //判斷隊列為空
    public boolean isEmpty(){
        return front==rear;
    }
    //求隊列的有效個數
    public int size(){
        return (rear+maxSize-front)%maxSize;
    }
    //入隊
    public void enqueue(int data){
        if(isFull()){
          throw new RuntimeException("隊列滿，不能入隊");
        }
        arr[rear]=data;
        rear=(rear+1)%maxSize;
    }
    //出隊
    public int dequeue(){
        if (isEmpty()){
            throw new RuntimeException("隊列空，不能出隊");
        }
        int getData=arr[front];
        front=(front+1)%maxSize;
        return getData;
    }
    //顯示隊列
    public void showQueue(){
        if (isEmpty()){
            throw new RuntimeException("隊列空");
        }
        for (int i = front; i < front+size(); i++) {
            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
        }
    }

    //顯示頭資料
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("隊列空");
        }
        return arr[front];
    }
}
           

測試環形隊列

public class Test {
	public static void main(String[] args) {
	   int headQueue; //用于顯示頭資料
        CircleArray circleArray=new CircleArray(4);
        circleArray.enqueue(3);
        headQueue= circleArray.headQueue();
        circleArray.enqueue(5);
        headQueue= circleArray.headQueue();
        circleArray.enqueue(8);
        headQueue= circleArray.headQueue();
        circleArray.dequeue();
        headQueue= circleArray.headQueue();
        circleArray.dequeue();
        headQueue= circleArray.headQueue();
        circleArray.enqueue(13);
        headQueue= circleArray.headQueue();
        circleArray.enqueue(15);
        headQueue= circleArray.headQueue();
    }  
}
           

隊列變化