Java循环队列的介绍（代码示例）

为了解决数组队列带来的问题，本篇给大家介绍一下循环队列。

思路分析图解

啰嗦一下，由于笔者不太会弄贴出来的图片带有动画效果，比如元素的移动或者删除（毕竟这样看大家比较直观），笔者在这里只能通过静态图片的方式，帮助大家理解实现原理，希望大家不要见怪，如果有朋友知道如何搞的话，欢迎在评论区慧言。

在这里，我们声明了一个容量大小为8的数组，并标出了索引0-7，然后使用front和tail分别来表示队列的，队首和队尾；在下图中，front和tail的位置一开始都指向是了索引0的位置，这意味着当frOnt== tai的时候 队列为空 大家务必牢记这一点，以便区分后面介绍队列快满时的临界条件

了解了循环队列的实现原理之后，下面我们用代码实现一下。

代码实现

接口定义 ：Queue

public interface Queue {
    /**
     * 入队
     *
     * @param e
     */
    void enqueue(E e);

    /**
     * 出队
     *
     * @return
     */
    E dequeue();

    /**
     * 获取队首元素
     *
     * @return
     */
    E getFront();

    /**
     * 获取队列中元素的个数
     *
     * @return
     */
    int getSize();

    /**
     * 判断队列是否为空
     *
     * @return
     */
    boolean isEmpty();
}

接口实现：LoopQueue

public class LoopQueue implements Queue {
    /**
     * 承载队列元素的数组
     */
    private E[] data;
    /**
     * 队首的位置
     */
    private int front;
    /**
     * 队尾的位置
     */
    private int tail;
    /**
     * 队列中元素的个数
     */
    private int size;

    /**
     * 指定容量，初始化队列大小
     * (由于循环队列需要浪费一个空间，所以我们初始化队列的时候，要将用户传入的容量加1)
     *
     * @param capacity
     */
    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
    }

    /**
     * 模式容量，初始化队列大小
     */
    public LoopQueue() {
        this(10);
    }


    @Override
    public void enqueue(E e) {
        // 检查队列为满
        if ((tail + 1) % data.length == front) {
            // 队列扩容
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }


    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        // 出队元素
        E element = data[front];
        // 元素出队后，将空间置为null
        data[front] = null;
        // 维护front的索引位置(循环队列)
        frOnt= (front + 1) % data.length;
        // 维护size大小
        size--;

        // 元素出队后，可以指定条件，进行缩容
        if (size == getCapacity() / 2 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return element;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return frOnt== tail;
    }


    // 队列快满时，队列扩容；元素出队操作，指定条件可以进行缩容
    private void resize(int newCapacity) {
        // 这里的加1还是因为循环队列我们在实际使用的过程中要浪费一个空间
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i public class LoopQueueTest {
    @Test
    public void testLoopQueue() {
        LoopQueue loopQueue = new LoopQueue<>();
        for (int i = 0; i <10; i++) {
            loopQueue.enqueue(i);
        }
        // 初始化队列数据
        System.out.println("原始队列: " + loopQueue);
        // 元素0出队
        loopQueue.dequeue();
        System.out.println("元素0出队: " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素1出队: " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素2出队: " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素3出队: " + loopQueue);
        loopQueue.dequeue();
        System.out.println("元素4出队,发生缩容: " + loopQueue);
        // 队首元素
        System.out.println("队首元素：" + loopQueue.getFront());
    }
}

测试结果：

原始队列: LoopQueue{【队首】data=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, frOnt=0, tail=10, size=10, capacity=10}
元素0出队: LoopQueue{【队首】data=[null, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, frOnt=1, tail=10, size=9, capacity=10}
元素1出队: LoopQueue{【队首】data=[null, null, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, frOnt=2, tail=10, size=8, capacity=10}
元素2出队: LoopQueue{【队首】data=[null, null, null, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, frOnt=3, tail=10, size=7, capacity=10}
元素3出队: LoopQueue{【队首】data=[null, null, null, null, 4, 5, 6, 7, 8, 9, null]【队尾】, frOnt=4, tail=10, size=6, capacity=10}
元素4出队,发生缩容: LoopQueue{【队首】data=[5, 6, 7, 8, 9, null]【队尾】, frOnt=0, tail=5, size=5, capacity=5}
队首元素：5

完整版代码GitHub仓库地址：Java版数据结构-队列（循环队列）

本篇文章到这里就已经全部结束了，更多其他精彩内容可以关注的Java视频教程栏目！

以上就是Java循环队列的介绍（代码示例）的详细内容，更多请关注其它相关文章！