队列介绍

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

数组模拟队列

• 代码实现

package com.atguigu.queue;

import java.util.Scanner;

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("j(join):入队");
            System.out.println("l(leave):出队");
            key = scanner.next().charAt(0);
            switch (key) {
            case 's':
                queue.showQueue();
                break;
            case 'e':
                loop = false;
                scanner.close();
                break;
            case 'j':
                System.out.print("请输入一个数据:");
                queue.joinQueue(scanner.nextInt());
                break;
            case 'l':
                try {
                    System.out.println("出队的数据为:" + queue.leaveQueue());
                } catch (RuntimeException e) {
                    System.out.println(e.getMessage());
                }
                break;
            default:
                break;
            }
        }
    }
}

//使用数组模拟队列：编写一个ArrayQueue类
class ArrayQueue {
    private int maxSize;// 表示数组的最大容量
    /*
     * front指向队列的第一个元素，初始值为0。rear指向队列最后一个元素的后一个位置，初始值为0
     */
    private int front, rear;// 队头和队尾
    private int[] arr;// 模拟队列

    // 创建队列的构造器
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }

    // 判断队满
    public boolean isFull() {
        return rear == maxSize;
    }

    // 判断队空
    public boolean isEmpty() {
        return front == rear;
    }

    // 添加数据到队列：入队
    public void joinQueue(int num) {
        // 如果队列不满才可添加
        if (isFull()) {
            System.out.println("队列已满");
        } else {
            arr[rear++] = num;// rear后移一位
        }
    }

    // 从队列中取数据：出队
    public int leaveQueue() {
        // 如果队列不空才可取
        if (isEmpty()) {
            throw new RuntimeException("队列已空");
        } else {
            return arr[front++];// front后移一位
        }
    }

    // 显示队列所有数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列空");
        } else {
            for (int i = front; i < rear; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }
}

• 问题分析并优化：目前数组使用一次就不能用，没有达到复用的效果。-> 环形队列，取模%

数组模拟环形队列

对前面的数组模拟队列的优化，充分利用数组.因此将数组看做是个环形的。(通过取模的方式来实现即可)
分析说明：

5.png

6.png

7.png

package com.atguigu.queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        //测试数组模拟环形队列
        
        //创建一个环形队列
        CircleArray queue = new CircleArray(4);//说明：设置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("j(join):入队");
            System.out.println("l(leave):出队");
            key = scanner.next().charAt(0);
            switch (key) {
            case 's':
                queue.showQueue();
                break;
            case 'e':
                loop = false;
                scanner.close();
                break;
            case 'j':
                System.out.print("请输入一个数据:");
                queue.joinQueue(scanner.nextInt());
                break;
            case 'l':
                try {
                    System.out.println("出队的数据为:" + queue.leaveQueue());
                } catch (RuntimeException e) {
                    System.out.println(e.getMessage());
                }
                break;
            default:
                break;
            }
        }
    }
}

class CircleArray {
    private int maxSize;// 表示数组的最大容量
    /*
     * front指向队列的第一个元素，初始值为0。rear指向队列最后一个元素的后一个位置，初始值为0
     */
    private int front, rear;// 队头和队尾
    private int[] arr;// 模拟队列

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

    // 判断队满
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    // 判断队空
    public boolean isEmpty() {
        return front == rear;
    }

    // 添加数据到队列：入队
    public void joinQueue(int num) {
        // 如果队列不满才可添加
        if (isFull()) {
            System.out.println("队列已满");
        } else {
            // 直接将数据加入
            arr[rear] = num;
            // rear后移，这里必须考虑取模
            rear = (rear + 1) % maxSize;
        }
    }

    // 从队列中取数据：出队
    public int leaveQueue() {
        // 如果队列不空才可取
        if (isEmpty()) {
            throw new RuntimeException("队列已空");
        } else {
            // 1.先把front对应的值保留到一个临时变量
            // 2.将front后移，考虑取模
            // 3.将临时变量返回
            int value = arr[front];
            front = (front + 1) % maxSize;
            return value;
        }
    }

    // 显示队列所有数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列空");
        } else {
            //思路：从front开始遍历，遍历多少个元素
            for (int i = front; i < front+size(); i++) {
                System.out.print(arr[i%maxSize] + " ");
            }
            System.out.println();
        }
    }
    
    //求出当前队列中有效数据的个数
    public int size() {
        return (rear+maxSize-front)%maxSize;
    }
}