数据结构笔记总结（2.4）数组队列-极客文库

队列（Queue）

队列也是一种线性结构
相比数组，队列对应的操作是数组的子集
只能从一端（队尾）添加元素，只能从另一端（队首）取出元素

接下来看一个演示，假设上图是一个队列，定义下面是队首，上面是队尾。

类比于我们去银行办事情，相应的就有一个柜台，排队到柜台办业务。

一旦来了个新的人，类比于数据结构中也就是来了一个新的元素。

新的元素就应该从队尾的位置进入队列，依次类推……

如果要出队，比如服务员已经办完了一个人的业务了，有空闲去办另一个人的业务。

这就需要从队列中取出一个元素，取出的这个元素就应该是队首的元素，也就是1。

综上可得：

队列是一种先进先出的数据结构（先到先得）
Fist In First Out（FIFO）

队列的实现

类比于之前栈的实现，队列中主要实现这些方法，其实这些方法和栈是对应的，只不过换了一下数据结构名字叫法而已。

同理，我们实现队列也不用关心底层实现的，我们实现一个接口Queue，和之前的栈一样，复用array动态数组类来实现一个属于我们自己的arrayQueue。

代码演示

首先创建一个叫Queue的接口

public interface Queue {

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

再创建一个arrayQueue来实现Queue接口

public class ArrayQueue implements Queue {

    private Array array;

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

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

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

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

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

    @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();
    }

    public static void main(String[] args) {

        ArrayQueue 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);
            }
        }
    }
}

运行程序，分析结果：