数据结构 - 队列 && 环形队列（循环队列）

文章目录

• 队列介绍
• 数组模拟队列设计思路
• 数组模拟队列代码实现
• 环形队列相关知识说明
• 队列长度公式推导
• 数组模拟环形队列代码实现

队列介绍

• 队列是一个有序列表，可以用数组或是链表来实现。
• 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。

数组模拟队列设计思路

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 MaxSize 是该队列的最大容量。

因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变。

数组模拟队列代码实现

当我们将数据存入队列时称为addQueue，步骤如下：

1. 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。前提判断队列 容量是否满了。 rear == maxSize - 1【队列满】
2. 如果队列没满，将 rear++；rear 后移。然后存入数据 arr[rear] = n;

当我们将数据从队列取出时称为getQueue，步骤如下：

1. 首先判断队列 是否为空 取决于 front == rear 【空】
2. 队列为空，无法取数据
3. 队列不为空，front++; // front队列头后移 ，取出数据 int result = arr[front];

代码实现

/**
 * @ClassName ArrayQueueDemo
 * @author: shouanzh
 * @Description 数组模拟队列
 * @date 2022/4/26 19:38
 */
public class ArrayQueueDemo {

    public static void main(String[] args) {
        // 创建一个队列
        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): 查看队列头的数据");
            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) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': // 查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': // 退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }

        System.out.println("程序退出~~");
    }
    

}
// 使用数组模拟一个队列：ArrayQueue类
class ArrayQueue{
    private int maxSize;// 数组最大的容量
    private int front;  // 队列头
    private int rear;   // 对列尾
    private int[] arr;  // 该数组用于存放数据，模拟队列
    
    // 创建队列构造器
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1;// 指向队列头部，分析出目前初始化的 front 是指向队列头的前一个位置       
        rear = -1; // 指向队列尾部，意思就是队列最后一个数据的位置
    }
    
    // 判断队列是否满
    public boolean isFull() {
        return rear == maxSize-1;// 队列尾  == 数组的最后一个数据
    }
    
    // 判断你队列是否为空
    public boolean isEmpty() {
        return front == rear;// 头尾相等，说明没数据
    }
    
    // 添加数据到队列
    public void addQueue(int n) {
        // 判断队列是否满
        if(isFull()) {
            System.out.println("队列已满,无法添加数据~~~~");
            return;
        }
        rear++; // 让 rear 后移
        arr[rear] = n;
    }
    
    // 获取队列数据(出队列)
    public int getQueue() {
        // 判断队列是否为空
        if(isEmpty()) {
            // 通过异常抛出 null
            throw new RuntimeException("队列为空，无法取数据~~~");
        }
        front++;// front后移
        int result = arr[front];
        arr[front] = 0;// 此时取出的值 位置存放的为0
        return result;
    }
    
    // 显示队列的所有数据
    public void showQueue() {
        // 判空
        if(isEmpty()) {
            System.out.println("队列为空,无法显示数据~~~~");
            return;
        }
        // 遍历
        for (int i = front + 1; i <= rear; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }
    
    // 显示头队列，而非取出
    public int headQueue() {
        // 判空
        if (isEmpty()) {
            // 通过异常抛出 null
            throw new RuntimeException("队列为空，无法取数据~~~");
        }
        // 显示
        return arr[front+1];// 这边加一的原因是一开始，初始化指向的是队列头的前一个
    }
}

存在的问题

解决方案

把数组的前端和后端连接起来，形成一个环形的顺序表，即把存储队列元素的表从逻辑上看成一个环，称为环形队列或循环队列。

环形队列相关知识说明

实际上内存地址一定是连续的，不可能是环形的，这里是通过逻辑方式 实现环形队列，也就是将rear++和 front++改为：

• rear=(rear+1)%MaxSize
• front=(front+1)%MaxSize

图示 ：空队、进队、出队

以上各个变量的意义如下：

rear：队尾。指向数列队尾元素的下一个空间。
front：队头。指向数列队头元素。
MaxSize：队列的最大长度。如队列data[10]的表示data[0]~data[9]一共十个元素。

---

1、初始条件：front== rear == 0；

2、进队 *** 作：队列没满时，先将值送到队尾，再将队尾指针加1。即data[rear] = n，rear=（rear+1）% MaxSize；

3、出队 *** 作：队列不空时，先取队头元素，再将队头元素加一。即x=data[front]，front=（front+1）% MaxSize；

4、判断队列是否为空：front==rear，注意这里队头和队尾不一定是指向0号元素。举个例子，初始时front==rear==0，假如我先在data[0]存入一个数，这时front==0，而rear==1。在这个前提下我们再进行出队 *** 作，则此时front==rear==1，队列为空 ，如图所示。

5、判断队列是否满了：（rear+1）% MaxSize==front。我们要知道一个前提，即队列如果有十个单元，则我们只能使用9个单元，当队尾指针指向最后一个空单元时，则认为队列已满。这虽然牺牲了一个单元，但也避免了判空条件的冲突。比如 MaxSize=3，如果三个单元都装入元素，那么rear=（2+1）% 3 = 0；front=（2+1）% 3 = 0；这样就和判空冲突了。

6、rear一定大于front吗？这肯定不对。我们在进队的时候也可以进行出队 *** 作。
当队列满时，如果我们进行出队 *** 作，则front>0。此时队列又变为不满的 *** 作，我们可以继续进行进队 *** 作，则rear会从data[MaxSize-1]（即末尾）回到开头。

队列长度公式推导

队列长度=（rear + MaxSize - front）% MaxSize

由上面介绍的队列的知识，我们可以知道rear有大于、小于和等于front三种情况。

*以下推导假设MaxSize=10；

1、rear > front
假设rear=5，front=2，则现在队列占得单元有data[2]、data[3]、data[4]三个，那么队列长度L=rear-front=3。

2、rear=front
假设rear=5，front=5。我们知道rear是一定指向空单元的，
所以队列长度L=rear-front=0；

3、rear 假设rear=3，front=5，那么队列占得单元有front开头的data[5]、data[6]、data[7]、data[8]、data[9] 5个单元，再加上rear往下数的data[2]、data[1]、data[0]三个单元，一共有8个单元。则MaxSize-front=5，MaxSize-front+rear=8，
所以队列长度L=MaxSize-front+rear；

---

3的结果我们将变量位置变一下，则L = rear - front + MaxSize；

这时我们发现3的结果不就是在1和2的结果上加了一个MaxSize吗。根据数学取余的性质，

（x+ky）% y=x（注：x

L=（rear-front+MaxSize）% MaxSize

比如1的结果 可以看作 （（rear-front）+MaxSize）% MaxSize = rear-front；
比如3的结果：rear-front+MaxSize < MaxSize 取模后 还是 rear-front+MaxSize；

数组模拟环形队列代码实现

/**
 * @ClassName CircleArrayQueueDemo
 * @author: shouanzh
 * @Description 数组模拟环形队列
 * @date 2022/4/26 19:38
 */
public class CircleArrayQueueDemo {

    public static void main(String[] args) {
        // 创建一个队列
        CircleArrayQueue queue = new CircleArrayQueue(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) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }

        System.out.println("程序退出~~");
    }
    
}

//使用数组模拟一个环形队列：CArrayQueue类
class CircleArrayQueue{
    
    private int maxSize;// 数组最大的容量
    // front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 
    private int front;
    // rear 指向队列的最后一个元素的后一个位置
    private int rear;
    private int[] arr;  
    
    // 创建队列构造器
    public CircleArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[arrMaxSize];
        // front rear 默认值为0，声明的默认值也为0，既不需要重复赋值
    }
    
    // 判断队列是否满
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    // 判断你队列是否为空
    public boolean isEmpty() {
        return front == rear;// 头尾相等，说明没数据
    }
    
    // 添加数据到队列
    public void addQueue(int n) {
        // 判断队列是否满
        if (isFull()) {
            System.out.println("队列已满,无法添加数据~~~~");
            return;
        }
        // 直接插入进来
        arr[rear] = n;
        // rear 后移, 得考虑取模(环形)
        rear = (rear + 1) % maxSize;
    }

    // 获取队列数据(出队列)
    public int getQueue() {
        // 判断队列是否为空
        if (isEmpty()) {
            // 通过异常抛出 null
            throw new RuntimeException("队列为空，无法取数据~~~");
        }
        // 分析得 front 是指向队列的第一个元素
        // 先 将 front 值保存到临时变量，用于返回
        // 然后再进行后移
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    // 显示队列的所有数据
    public void showQueue() {
        // 判空
        if (isEmpty()) {
            System.out.println("队列为空,无法显示数据~~~~");
            return;
        }
        // 遍历(从头队列 到 都队列 + 有效数据个数)
        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 - front + maxSize) % maxSize;  
    }
    
    // 显示头队列，而非取出
    public int headQueue() {
        // 判空
        if (isEmpty()) {
            // 通过异常抛出 null
            throw new RuntimeException("队列为空，无法取数据~~~");
        }
        // 显示
        return arr[front];
    }
}