什么是隊列

1. 隊列是一個有序列表, 可以用數(shù)組或鏈表實現(xiàn)
2. 先入先出

使用數(shù)組模擬隊列和環(huán)形隊列

• 用數(shù)組模擬隊列

思路:
1.根據(jù)隊列的最大容量創(chuàng)建一個數(shù)組來保存隊列數(shù)據(jù)
2.定義兩個變量, front和rear分別記錄隊列前后端的下標(biāo), 取數(shù)據(jù)front++, 存數(shù)據(jù)rear++

class ArrayQueue{

    private int maxSize; //數(shù)組的最大容量
    private int front; //隊列頭
    private int rear;  //隊列尾
    private int[] arr; //存放數(shù)據(jù)

    /**
     * 創(chuàng)建隊列
     * @param maxSize
     */
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = -1;
        rear = -1;
    }

    /**
     * 判斷隊列是否已經(jīng)滿了
     * @return
     */
    public boolean isFull(){
        return rear == maxSize - 1;
    }

    /**
     * 判斷隊列是否為空
     * @return
     */
    public boolean isEmpty(){
        return rear == front;
    }

    /**
     * 添加數(shù)據(jù)到隊列
     * @param n
     */
    public void addQueue(int n){
        if(isFull()){
            System.out.println("滿了");
            return;
        }
        rear ++;
        arr[rear] = n;
    }

    /**
     * 從隊列中獲取數(shù)據(jù)
     * @return
     */
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("空");
        }
        front ++;
        return arr[front];
    }

    /**
     * 獲取隊列的第一個數(shù)據(jù), 注意不是取數(shù)據(jù)
     * @return
     */
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("空");
        }
        return arr[front + 1];
    }

    /**
     * 遍歷隊列
     */
    public void showQueue(){
        if(isEmpty()){
            System.out.println("空隊列");
            return;
        }
        for(int i=0; i<arr.length; i++){
            System.out.println(arr[i]);
        }
    }
}

• 使用數(shù)組模擬環(huán)形隊列
  為了充分利用數(shù)組啄栓，我們可以將數(shù)組看做是一個環(huán)形的

思路:
1.尾索引的下一個為頭索引時表示滿, 即(rear + 1)%maxSize == front
2.rear == front時, 表示空

class CircleArrayQueue{

    private int maxSize; //數(shù)組的最大容量
    private int front; //指向隊列的第一個元素, 初始值為0
    private int rear;  //指向隊列的最后一個元素的后一個位置, 初始值為0
    private int[] arr; //存放數(shù)據(jù)

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }

    /**
     * 隊列是否已滿
     * @return
     */
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }

    /**
     * 隊列是否為空
     * @return
     */
    public boolean isEmpty(){
        return rear == front;
    }

    /**
     * 添加數(shù)據(jù)到隊列
     * @param n
     */
    public void addQueue(int n){
        if(isFull()){
            System.out.println("滿");
            return;
        }
        //rear指向?qū)ξ蚕乱徊? 所以把插入的數(shù)組復(fù)制給arr[rear]即可
        arr[rear] = n;
        rear = (rear + 1) % maxSize; //rear后移
    }

    /**
     * 出隊列
     * @return
     */
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("空");
        }
        //取第一個值
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    /**
     * 顯示頭數(shù)據(jù)
     * @return
     */
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("空隊列");
        }
        return arr[front];
    }

    /**
     * 遍歷隊列數(shù)據(jù)
     */
    public void showQueue(){
        if(isEmpty()){
            System.out.println("空");
            return;
        }
        //求隊列中有效數(shù)據(jù)的個數(shù)
        int size = (rear + maxSize - front) % maxSize;
        for(int i=0; i<front+size; i++){
            System.out.println(arr[i%maxSize]);
        }
    }
}