队列、环形队列

数据结构与算法

单队列ArrayQueue、环形队列CircleArrayQueue

1. 单队列

• 队列是一个有序列表，可以使用数组或链表来实现。

• 先入先出，先存入队列的数据先取出，如排队。

单队列的3个属性：

• MaxSize表示队列最大容量
• rear表示尾指针，指向队列末尾，记录该数据的下标，随着数据输入而改变。
• 而front表示头指针，一般让它指向队列头的前一个位置，记录队列头的前一个下标，先自增后取值。

单队列生命周期

开始时，rear与front均指向-1，这是初始状态。

每把一个数据放入队列，尾指针rear就会+1。

当rear=MaxSize-1时，队列满。

每把一个数据从队列中取出，头指针front+1。

当front==rear时，即头指针与尾指针指向同一处，此时队列为空。

无法再取，所以，front<=rear。

单队列使用完一次后，便不能再次使用。

单队列数组实现

package Queue;

import java.util.Scanner;

public class ArrayQueue {

    private int MaxSize;
    private int front;
    private int rear;
    private int[] array;

    //初始化数组
    ArrayQueue(int MaxSize){

        this.MaxSize=MaxSize;
        array=new int[MaxSize];
        front=-1;
        rear=-1;

    }

    //判断队列是否满
     boolean isFull(){
        return rear==MaxSize-1;
    }

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

    //向队列增加数据
    void add(int data){

        if (isFull()){//判断队列是否已满
            System.out.println("队列已满，无法存");
        }else {
            rear++;//尾指针后移
            array[rear]=data;//赋值
            System.out.println("尾指针+1："+rear);
        }

    }

    //从队列取数据
    int get(){

       if (isEmpty()){//判断队列是否为空
           throw new RuntimeException("队列为空，无法取");
       }else {
           front++;
           System.out.println("头指针+1："+front);
           
           return array[front];//取值
       }

    }

    //显示整个队列
    void show(){
        if (isEmpty()){//判断队列是否为空
            throw new RuntimeException("队列空，无数据");
        }else {
            for (int data:array){//打印数组
             System.out.print(data+"\t");
            }
            System.out.println();
        }

    }

    //展示队列头数据
    int showFront(){
        if (isEmpty()){//判断队列是否为空
            throw new RuntimeException("队列空，无数据");
        }else {
           return array[front+1];//返回头数据，指针不变
            }
        }


    //展示队列尾数据
    int showRear(){
        if (isEmpty()){//判断队列是否为空
            throw new RuntimeException("队列空，无数据");
        }else {
            return array[rear];//返回尾数据，指针不变
        }

    }

    //测试队列
    public static void main(String[] args) {
        //创建一个队列对象，容量为3
        ArrayQueue queue = new ArrayQueue(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): 查看队列头的数据");
            System.out.println("r(rear): 查看队列尾的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.show();
                    break;
                case 'a':
                    System.out.println("输入一个数");
                    int value = scanner.nextInt();
                    queue.add(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.get();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.showFront();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'r': //查看队列头的数据
                    try {
                        int rear = queue.showRear();
                        System.out.printf("队列尾的数据是%d\n", rear);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~");
    }
}

2. 环形队列

相比单队列，环形队列属性设定有所变动：

属性的设定

• 初始时front = rear = 0，而不是-1

• rear指向队列尾数据的下一个空间，在尾数据后预留一个空间，即rear指向的位置不放值。（预留空间是为了区分队列空和队列满，空元素作为队尾的标志）

• front直接指向头数据

• 容量为MaxSize-1

环形队列生命周期

开始时，rear与front均指向0，这是初始状态。

每把一个数据放入队列，尾指针rear就会+1。

当（rear+1)%MaxSize=front 时，队列满。因为rear指向尾数据的下一个空间，队列满时rear+1自然等于front。

之所以%MaxSize取模是因为：环形队列指针的值会一直增加，%Maxsize会得到周期性的值，就像角度会加到362度、750度一样。

温馨提示：

%运算符：比如2%3就是，2除以3等于0余2，所以2%3就是2，而3%2=1。

每把一个数据从队列中取出，头指针front+1。

当front==rear时，即头指针与尾指针指向同一处，此时队列为空。

重点

这里不再像单队列，在循环中，front与rear的大小关系是不定的，有时rear>front，有时front>rear。

为什么会出现这种情形呢，rear>front的情形好理解，尾与头嘛。至于front>rear的情形，我们类比一下角度，假如rear在361度的位置，front在365度的位置，别忘了是环形。

由此可以得出，环形队列中的元素总数为：(rear-front+MaxSize)%MaxSize，始终用尾减去头，又因为rear-front的值正负不定，所以要加上MaxSize再%MaxSize。

环形队列可循环使用。

遍历时，从front开始，一直到front+size结束，size是当前元素个数，因为元素个数size会随着出队进队变化，变化量与front的移动量是一致的

环形队列数组实现

package Queue;

import java.util.Scanner;

public class CircleQueue {

    private int MaxSize;
    private int front;
    private int rear;
    private int[] array;

    //初始化数组
    CircleQueue(int MaxSize){

        this.MaxSize=MaxSize;
        array=new int[MaxSize];
        front=0;
        rear=0;

    }

    //判断队列是否满
    boolean isFull(){
        return (rear+1)%MaxSize==front;
    }

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

    //向队列增加数据
    void add(int data){

        if (isFull()){//判断队列是否已满
            System.out.println("队列已满，无法存");
        }else {
            array[rear%MaxSize]=data;//赋值
            rear++;//尾指针后移
            System.out.println("尾指针+1："+rear%MaxSize);
        }

    }

    //从队列取数据
    int get(){

        if (isEmpty()){//判断队列是否为空
            throw new RuntimeException("队列为空，无法取");
        }else {
            int data=array[front%MaxSize];
            front++;
            System.out.println("头指针+1："+front%MaxSize);
            return data;//取值
        }

    }

    //队列中的有效元素总数
    int getSize(){
        return (rear-front+MaxSize)%MaxSize;
    }


    //显示整个队列
    void show(){
        if (isEmpty()){//判断队列是否为空
            System.out.println("队列为空");
        }else {
            for (int i=front%MaxSize;i<front%MaxSize+getSize();i++){//打印数组
                System.out.println(array[i]+"\t");
            }
            System.out.println();
        }

    }

    //展示队列头数据
    int showFront(){
        if (isEmpty()){//判断队列是否为空
            throw new RuntimeException("队列空，无数据");
        }else {
            return array[front%MaxSize];//返回头数据，指针不变
        }
    }


    //展示队列尾数据
    int showRear(){
        if (isEmpty()){//判断队列是否为空
            throw new RuntimeException("队列空，无数据");
        }else {
            return array[(rear-1)%MaxSize];//返回尾数据，指针不变
        }

    }



    //测试队列
    public static void main(String[] args) {
        //创建一个队列对象，容量为5
        CircleQueue queue = new CircleQueue(5);
        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("z(getSize): 查看有效元素个数");
            System.out.println("h(head): 查看队列头的数据");
            System.out.println("r(rear): 查看队列尾的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.show();
                    break;
                case 'a':
                    System.out.println("输入一个数");
                    int value = scanner.nextInt();
                    queue.add(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.get();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.showFront();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'r': //查看队列头的数据
                    try {
                        int rear = queue.showRear();
                        System.out.printf("队列尾的数据是%d\n", rear);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                    case 'z': //查看队列头的数据
                    try {
                        int size = queue.getSize();
                        System.out.printf("元素个数是%d\n", size);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~");
    }
}