队列

什么是队列？
队列也是一种线性数据结构，和栈不同的是队列是先进先出，队列可以理解为一个管道，一端添加数据被称为入队，另外一端删除数据称为出队。
我们也可以通过动态数组来实现我们的队列.

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

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

    public ArrayQueue(){
        this(10);
    }
  
    public void enqueue(E e) {
        array.addLast(e);
    }

  
    public E dequeue() {
        return array.deleteFirst();
    }

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

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

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

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

由于我们在dequeue()的时候时间复杂度是O(n),效率不是很好，那我们有没有什么办法让dequeue()时间复杂度也是O(1)呢？
答案是我们可以通过 循环数组 的方式来实现队列。
在循环数组实现的队列中我们定义个泛型数组E[] e,front和tail,规定front==tail时数组为空，(tail+1)e.length==front时数组为满数组,每次调用dequeue()方法时不时真正的删除元素，而是把front向后添加一位。。

public class CircularQueue<E> implements Queue<E> {
    private E[] data;
    private int front;//记录dequeue()数据的位置
    private int tail;//记录()添加的位置
    private int size;

    public CircularQueue(int capacity) {
        //由于我们规定(tail+1)/data.length==front 为满数组，
        //所以我们要多出来一个数据大小，但是用户无感知。
        data = (E[]) new Object[capacity+1];
        size = 0;
        front = 0;
        tail = 0;
    }

    public CircularQueue() {
        this(10);
    }

    @Override
    public void enqueue(E e) {
        if (front == (tail + 1) % data.length) {
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    private void resize(int newSize) {
        E[] newData = (E[]) new Object[newSize+1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
    }

    @Override
    public E dequeue() {
        E e = data[front];
        data[front] = null;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        front = (front + 1) % data.length;
        size--;
        return e;
    }

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

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

    @Override
    public int getCapacity() {
        return data.length-1;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder =new StringBuilder();
        stringBuilder.append(String.format("capacity : %s front[",getCapacity()));
        for (int i = 0; i < size; i++) {
            if(i!=size-1){
                stringBuilder.append(data[(i+front)%data.length]+",");
            }else{
                stringBuilder.append(data[(i+front)%data.length]+"]tail");
            }

        }
        return stringBuilder.toString();
    }
}

循环数组队列的enqueue()和dequeue()时间复杂度都是O(1)，只是我们多浪费了一个存储空间。