Queue 队列

队列也是一种线性的数据结构。队列主要支持两种操作: enqueue 和 dequeue 。我们用前面实现的动态数组Array来实现我们自己的队列！

什么是队列？

队列也是一种线性的，用于存储数据的线性数据结构。队列主要支持两种操作：

1. 入队, 也称 enqueue

2. 出队, 也称 dequeue

队列满足FIFO规则，也就是先进先出规则。越早入队的元素出队时也越早，越晚入队的元素出队也越晚。就如下图所示，数据结构的队列和我们生活中排队上车，排队结账的道理类似，越早排队的人越早上车，越早排队的人越先结账。

队列的内部也有一个指针, 指向下一个入队元素的索引。

这么一看我们完全可以利用我们前面实现的Array来实现我们自己的队列！

队列的实现

队列的实现有多种方式，一种是通过动态数组, 另一种是通过链表。

为了增强代码的复用性和解耦，我们不从头实现一个队列。而是定义一个队列的接口, 动态数组或者链表，去实现这个接口即可。而事实上，通过我们上一节所学的Array来实现一个队列是非常简单的。

public interface IQueue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();

}

enqueue()方法 将一个元素入队。getFront()方法返回队首元素，但是不取出。dequeue() 取出队首的元素，并返。其他两个方法与Array相同, 这里就不做解释了。

随后我们定义一个ArrayQueue 类去实现 IQueue 接口即可。

public class ArrayQueue<E> implements IQueue<E> {
    private Array<E> array;

    public ArrayQueue(int capacity){
        array=new Array<>(capacity);
    }

    public ArrayQueue(){
        array=new Array<>();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder res =new StringBuilder();
        res.append("Queue");
        res.append(" front [");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if(i!=array.getSize()-1){
                res.append(", ");
            }
        }
        res.append("] tail");
        return  res.toString();
    }


}

可以看出，所有队列的操作, 都可以直接调用Array 的方法进行实现

最后定义一个ArryStackQueue类进行测试。我们依次向队列中enque 数字0到9, 每隔三次循环，就指向一次出队操作，每次入队，出队完都要打印输出。

public class QueueTest {

    public static void main(String[] args) {
        ArrayQueue<Integer> queue=new ArrayQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);
            if (i%3==2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }

}

输出结果:

Queue front [0] tail
Queue front [0, 1] tail
Queue front [0, 1, 2] tail
Queue front [1, 2] tail
Queue front [1, 2, 3] tail
Queue front [1, 2, 3, 4] tail
Queue front [1, 2, 3, 4, 5] tail
Queue front [2, 3, 4, 5] tail
Queue front [2, 3, 4, 5, 6] tail
Queue front [2, 3, 4, 5, 6, 7] tail
Queue front [2, 3, 4, 5, 6, 7, 8] tail
Queue front [3, 4, 5, 6, 7, 8] tail
Queue front [3, 4, 5, 6, 7, 8, 9] tail