Java数据结构之循环队列简单定义与用法示例

什么是循环队列？

循环队列是一种数据结构，它具有先进先出（FIFO）的特点，即最先进队列的元素总是被最先取出。不同于普通队列，循环队列的尾指针指向数组的头部，因此可以实现循环利用数组空间，提高存储空间的利用率，避免因队列的操作大量移动数组元素而导致的时间浪费。

循环队列的基本操作

循环队列的基本操作包括：入队、出队、判断队列是否为空、判断队列是否已满、求队列长度。

下面是循环队列的基本数据结构定义：

public class CircularQueue {
    private int[] array;
    private int front;
    private int rear;
    private int size;

    public CircularQueue(int n) {
        array = new int[n];
        front = 0;
        rear = 0;
        size = n;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % size == front;
    }

    public int getLength() {
        return (rear - front + size) % size;
    }

    public boolean enqueue(int item) {
        if (isFull()) {
            return false;
        }
        array[rear] = item;
        rear = (rear + 1) % size;
        return true;
    }

    public int dequeue() {
        if (isEmpty()) {
            return Integer.MIN_VALUE;
        }
        int item = array[front];
        front = (front + 1) % size;
        return item;
    }
}

上述代码中，front表示队列头的下标，rear表示队列尾的下标，array是存储队列元素的数组，size表示队列的大小。当队列满时，(rear+1)%size == front。

示例1：利用循环队列解决约瑟夫问题

约瑟夫问题是一个经典的问题，它的描述如下：

在计算机程序设计中，经常用到一个变体：$N$个人围成一圈，从第$1$个人开始报数，报到$M$的那个人出列，然后从出列的下一个人开始重新报数，报到$M$的那个人又出列，直到所有人出列为止。这个问题的解决策略就是使用循环队列。

代码如下：

public class Josephus {
    public static void main(String[] args) {
        int n = 7;
        int m = 3;
        CircularQueue queue = new CircularQueue(n);
        for (int i = 1; i <= n; i++) {
            queue.enqueue(i);
        }
        while (!queue.isEmpty()) {
            for (int i = 0; i < m - 1; i++) {
                queue.enqueue(queue.dequeue());
            }
            System.out.print(queue.dequeue() + " ");
        }
    }
}

上述代码中，将$n$个人的编号，分别放到循环队列中，然后不断取出队头的元素报数，直到所有的人都出列为止。

示例2：利用循环队列实现打印队列元素

以下代码实现利用循环队列输出队列中的元素：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue(5);
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入五个数据：");
        for (int i = 0; i < 5; i++) {
            int num = scanner.nextInt();
            queue.enqueue(num);
        }
        while (!queue.isEmpty()) {
            System.out.print(queue.dequeue() + " ");
        }
    }
}

上述代码中，首先创建了一个循环队列，用于存储用户输入的五个数。然后，调用Scanner类的nextInt()方法读取用户输入的数字，并将其存储到循环队列中。最后，使用循环队列的出队操作，将所有元素输出。

总结

循环队列是一种非常常用的数据结构，可以提高空间的利用率，避免因为队列操作对数组元素的移动而造成的时间浪费。同时，循环队列也具有先进先出的性质，非常适用于需要按照顺序处理数据的场景。在实际应用中，循环队列还有着更广泛的应用，例如在操作系统中，循环队列被广泛应用于缓存管理、任务调度以及内存分配等方面。