使用数组实现循环队列

什么是队列

队列（Queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。队列的特点就是先进先出(FIFO)。

之前我们在 Java实现单向链表 一文中通过链表实现了队列。下面我们通过数组实现队列。

队列之循环队列

使用数组实现队列要注意的是，如果队首和队尾的指针随着出队和入队变化，会造成队列的容量变小。

下面通过循环队列的方式，实现在不扩容的情况下队列容量恒定：

入队时，队尾指针位置为： (rear + 1) % array.length。

出队时，队头指针位置为： (front + 1) % array.length。

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.queue.impl;

import java.lang.reflect.Array;

/**
 * queue
 *
 * @author ijiangtao
 * @create 2019-07-10 21:06
 **/
public class ArrayQueue<T> {

    /**
     * 队列容器
     */
    private T[] array;

    /**
     * 队头指针
     */
    private int front;

    /**
     * 队尾指针
     */
    private int rear;

    /**
     * 构造函数
     *
     * @param capacity 队列容量
     */
    public ArrayQueue(Class<T> type, int capacity) {
        //通过反射创建泛型数组
        this.array = (T[]) Array.newInstance(type, capacity);
    }

    public int capacity() {
        return array.length;
    }

    public boolean isFull() {
        return (rear + 1) % array.length == front;
    }

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

    /**
     * 元素入队
     *
     * @param element
     * @throws Exception
     */
    public void enqueue(T element) throws Exception {
        if ((rear + 1) % array.length == front) {
            throw new Exception("队列已经满了");
        }
        array[rear] = element;
        rear = (rear + 1) % array.length;
    }

    /**
     * 元素出队
     *
     * @return
     * @throws Exception
     */
    public T dequeue() throws Exception {
        if (rear == front) {
            throw new Exception("队列已经空空如也");
        }
        T element = array[front];
        front = (front + 1) % array.length;
        return element;
    }

    public static void main(String[] args) throws Exception {

        ArrayQueue<String> queue = new ArrayQueue<>(String.class, 8);
        System.out.println("E1"+queue.capacity());
        int i = 1;
        while (!queue.isFull()) {
            queue.enqueue("E" + (i++));
        }

        while (!queue.isEmpty()) {
            System.out.println(queue.dequeue());
        }

    }
}

复制代码

测试方法执行输出结果如下：

queue size = 8
E1
E2
E3
E4
E5
E6
E7
复制代码