数据结构之队列

什么是队列

1. 队列是一个有序列表, 可以用数组或链表实现
2. 先入先出

使用数组模拟队列和环形队列

• 用数组模拟队列

思路:
1.根据队列的最大容量创建一个数组来保存队列数据
2.定义两个变量, front和rear分别记录队列前后端的下标, 取数据front++, 存数据rear++

class ArrayQueue{

    private int maxSize; //数组的最大容量
    private int front; //队列头
    private int rear;  //队列尾
    private int[] arr; //存放数据

    /**
     * 创建队列
     * @param maxSize
     */
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = -1;
        rear = -1;
    }

    /**
     * 判断队列是否已经满了
     * @return
     */
    public boolean isFull(){
        return rear == maxSize - 1;
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty(){
        return rear == front;
    }

    /**
     * 添加数据到队列
     * @param n
     */
    public void addQueue(int n){
        if(isFull()){
            System.out.println("满了");
            return;
        }
        rear ++;
        arr[rear] = n;
    }

    /**
     * 从队列中获取数据
     * @return
     */
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("空");
        }
        front ++;
        return arr[front];
    }

    /**
     * 获取队列的第一个数据, 注意不是取数据
     * @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]);
        }
    }
}

• 使用数组模拟环形队列
  为了充分利用数组，我们可以将数组看做是一个环形的

思路:
1.尾索引的下一个为头索引时表示满, 即(rear + 1)%maxSize == front
2.rear == front时, 表示空

class CircleArrayQueue{

    private int maxSize; //数组的最大容量
    private int front; //指向队列的第一个元素, 初始值为0
    private int rear;  //指向队列的最后一个元素的后一个位置, 初始值为0
    private int[] arr; //存放数据

    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;
    }

    /**
     * 添加数据到队列
     * @param n
     */
    public void addQueue(int n){
        if(isFull()){
            System.out.println("满");
            return;
        }
        //rear指向对尾下一步, 所以把插入的数组复制给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;
    }

    /**
     * 显示头数据
     * @return
     */
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("空队列");
        }
        return arr[front];
    }

    /**
     * 遍历队列数据
     */
    public void showQueue(){
        if(isEmpty()){
            System.out.println("空");
            return;
        }
        //求队列中有效数据的个数
        int size = (rear + maxSize - front) % maxSize;
        for(int i=0; i<front+size; i++){
            System.out.println(arr[i%maxSize]);
        }
    }
}