数据结构----队列

1.队列（queue）就是只允许在一端进行插入，另一端进行删除的线性表。
2.不同于栈的是，队列是先进先出的线性表，允许插入的一端叫队尾（rear），删除的一端叫队头(front)。
3.队列也是一种特殊的线性表，其实现方式和线性表完全相同。
4.由于入队（offer）是在队尾添加，所以时间复杂度为O（1），而出队(poll)是从队首删除，需要移动整个队列，时间复杂度为O（n）.

1.为了防止出现出队部分元素以后队列前方空置，而队尾已经到达最大容量，导致队列假溢出的问题，将队列的头和尾相接形成循环队列就可以解决这个问题。

2.通过循环队列这种结构，队列的有效容量得以充分利用，当队列满足（rear + 1%size == front的时候， 队列满；当rear = front的时候，队列空。

3.循环队列的实现
需要注意的是队尾rear始终指向空，所以当队列满组要扩容时需要计算新的容量，不能直接给原length × 2

public class ArrayLoopQueue implements Queue {
    private E[] data;//存储元素的容器
    private int front;
    private int rear;
    private int size;
    private static int DEFAULT_SIZE = 10;
    public ArrayLoopQueue(){
        this(DEFAULT_SIZE);
    }
    public ArrayLoopQueue(int capacity){
        data = (E[]) new Object[capacity + 1];
        front = 0;
        rear = 0;
        size = 0;

    }

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

    @Override
    public boolean isEmpty() {
        return size == 0 && front == rear;
    }

    @Override
    public void offer(E element) {
        if ((rear + 1) % data.length == front){
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            throw new NullPointerException("队列为空");
        }
        E ret = data[front];
        front = (front + 1) % data.length;
        size--;
        if (size == (data.length - 1) / 4 && data.length - 1 > DEFAULT_SIZE){
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    private void resize(int newLength) {
        E[] newData = (E[]) new Object[newLength];
        int index = 0;
        for (int i = front;i != rear;i = (i + 1) % data.length){
            newData[index] = data[i];
            index++;
        }
        front = 0;
        rear = index;
        data = newData;
    }

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

    @Override
    public void clear() {
        data = (E[]) new Object[DEFAULT_SIZE];
        front = 0;
        rear = 0;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(String.format("ArrayLoopQueue:%d/%d[",size,data.length - 1));
        if (isEmpty()) {
            sb.append(']');
        }else {
            for (int i = front; i != rear;i = (i + 1) % data.length){
                sb.append(data[i]);
                if ((i + 1) % data.length == rear){
                    sb.append(']');
                }else {
                   sb.append(',');
                }
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator iterator() {
        return new ArrayLoopQueueIterator();
    }
    class ArrayLoopQueueIterator implements Iterator{
        private int cur;//设置游标
        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E  ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }
}

1.双端队列（Deque）

是限定插入和删除操作在表的两端进行的线性表；是一种具有队列和栈的性质的数据结构，它既可以在队首队尾添加，也可以删除，是特殊的循环队列。除了尤其自身的特点外，也可以当作队列或者栈去使用。

2.双端队列判空和判满的条件相同。
3.区别于循环队列的是，双端队列在队首添加元素时有本来就是第一个位置的情况，这样的话front就需要向前再推一个到达数组最后一个位置，计算他的下标就需要front = (front - 1 + data.length) % data.length

 @Override
    public void addFirst(E element) {
        if (isExpansion()){
            resize(data.length * 2 -1);
        }
        front = (front - 1 + data.length) % data.length;
        data[front] = element;
        size++;
    }

    private void resize(int newLength) {
        E[] newData = (E[]) new Object[newLength];
        int index = 0;
        for (int i = front; i != rear;i = (i + 1) % data.length){
            newData[index] = data[i];
            index++;
        }
        front = 0;
        rear = index;
        data = newData;
    }

在队尾添加元素还是和循环队列思路相同：

@Override
    public void addLast(E element) {
        if (isExpansion()){
            resize(data.length * 2 - 1);
        }
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }

在队首删除元素与添加元素对下标的操作相反：

@Override
    public E removeFirst() {
        if (isEmpty()){
            throw new NullPointerException("队列为空");
        }
        E ret = data[front];
        front = (front + 1) % data.length;
        size--;
        if (isShrink()){
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    private boolean isShrink() {
        return size == (data.length - 1) / 4 && data.length - 1 > DEFAULT_SIZE;
    }

队尾删除元素与循环队列相同：

@Override
    public E removeLast() {
        if (isEmpty()){
            throw new NullPointerException("队列为空");
        }
        E ret = data[rear];
        rear = (rear - 1 + data.length) % data.length;
        size--;
        if (isShrink()){
            resize(data.length / 2 + 1);
        }
        return ret;
    }