队列

特点: 先进先出

存元素:从最后位置开始存放,存满为止 (rear)
取元素:从第一个位置取元素 (front)

图解:

百度百科

环形队列

特点:和队列一样特点一样先进先出,可以无限复用

存元素:从最后位置开始存放 (rear)
- 若存满,则提示队列满了
- 若没有存满(队列元素被取出了),则复用队列
取元素:从第一个位置取元素 (front)

分析:

要想使队列变成环形队列,那么只需要一点,当队列存放满时,则存放到队列第一个元素

注意 : 这里存放队列第一个元素不会覆盖原有元素

图解:

红色:代表有元素存放

假设现在队列存满:

此时有新的元素需要进入队列,但是此时队列满了,不能添加进去

什么时候可以使用环形添加进去元素呢?

上边也强调了,队列是先进先出的原则,取数据的时候从第一个元素开始取

分析:

需要满足环形队列也非常容易,当元素满时,则让元素存放到第 0 个位置即可

if(index++ == size){
    index = 0;
}
复制代码

但是这种办法非常笨,接下来给大家介绍%运算,懂的朋友直接跳过!

%运算

%运算也是求余数

直接举个例子应该能看懂:

public static void initRemainder() {
        int index = 3;
        int size = 10;
        System.out.println(index % size);
}
结果为:3
复制代码

public static void initRemainder() {
        int index = 10;
        int size = 10;
        System.out.println(index % size);
}
结果为:0
复制代码

public static void initRemainder() {
        int index = 14;
        int size = 10;
        System.out.println(index % size);
}
结果为:4
复制代码

百度百科

数组模拟环形队列分析

int front 记录元素开始位置
int rear 记录元素最后一个位置
int maxSize 总大小
int[] array 元素数组

队列空:

rear == front(第一个元素 == 最后一个元素 )

队列满:

(rear + 1) % mMaxSize == front;

rear+1 表示队列始终预留一个位置,防止下标越界

添加数据:

array[rear] = value

取出数据:

int value = array[front]

完整代码:

public class ArrayQueue {
    //数组长度
    private final int mMaxSize;
    //队列头(队列第一个元素)
    private int front;
    //对列尾部(队列最后一个元素)
    private int rear;
    private final int[] array;

    public ArrayQueue(int mMaxSize) {
        this.mMaxSize = mMaxSize;
        //初始化队列长度
        array = new int[this.mMaxSize];
    }

    //队列是否满
    public boolean isFull() {
        /*
         * 队列一直预留一个位置,所以这里需要 rear + 1
         */
        return (rear + 1) % mMaxSize == front;
    }

    //队列是否为空
    public boolean isEmpty() {
        /*
         * 当 rear = front 时表示队列没有数据
         */
        return rear == front;
    }

    //添加数据
    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("不能添加,队列满");
            return;
        }

        array[rear] = n;

        //rear + 1 表示默认预留一个位置防止下标越界
        rear = (rear + 1) % mMaxSize;
    }

    //取出数据
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("不能取数据,队列空");
        }

//        front 指向队列第一个元素
//        1.先把 front 对应的值保留到一个临时变量
//        2.将 front 后移动 取模
//        3.把临时保存的变量返回
        int temp = array[front];
        front = (front + 1) % mMaxSize;
        return temp;
    }

    //打印所有数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("不能打印,队列为空");
            return;
        }
        for (int i = front; i < front + EffectiveSize(); i++) {
            System.out.printf("arr[%d] = %d \n", i % mMaxSize, array[i % mMaxSize]);
        }
        System.out.println();
    }

    //当前个数有效数据
    public int EffectiveSize() {
        //(最大值 - 最小值 + 总数) % 总数 = 当前有效个数
        return (rear + mMaxSize - front) % mMaxSize;
    }

    //头元素
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("头元素没有数据");
        }
        return array[front];
    }
}
复制代码

使用:

public class Client {

    public static void main(String[] args) {

        initRemainder();

        ArrayQueue arrayQueue = new ArrayQueue(4);

        //输入
        Scanner scanner = new Scanner(System.in);

        //true 循环 false 不循环
        boolean isWhile = true;

        while (isWhile) {
            showLog();
            char key = scanner.next().charAt(0);
            switch (key) {
                case 'a':
                    //添加数据
                    System.out.println("请输入一个数:");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    System.out.println("get 数据为:" + arrayQueue.getQueue());
                    break;
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'h':
                    System.out.println("第一个数据为:" + arrayQueue.headQueue());
                    break;
                case 'e':
                    System.out.println("队列有效个数为:" + arrayQueue.EffectiveSize());
                    break;
                case 'r':
                    isWhile = false;
                    System.out.println("退出成功~");
                    break;
                default:
                    throw new IllegalStateException("Unexpected value: " + key);
            }
        }
    }

    public static void showLog() {
        System.out.println("a(add)添加元素");
        System.out.println("g(get)获取元素");
        System.out.println("h(head)获取队列头部元素");
        System.out.println("s(show)显示队列元素");
        System.out.println("e(effectiveSize)队列有效元素长度");
    }

    public static void initRemainder() {
        int index = 3;
        int size = 10;
        System.out.println(index % size);
    }
}
复制代码