借口

package p1.List;

public interface Dequeue <E> extends Queue<E>{
    public void addFirst(E element);
    public  void addLast(E element);
    public void  removeLast(E element);
    public E removeFirst();
    public  E getFirst();
    public E getLast();
}

package P2.线性结构;

import p1.List.Dequeue;

import java.util.Iterator;

public class ArrayDeque<E> implements Dequeue<E> {
    private E[] data;
    private int front;
    private int rear;
    private int size;
    private static int DEFAULT_CAPACITY = 10;

    //创建一个构造函数
    public ArrayDeque() {
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }

    @Override
    //addfirst 是在front前添加
    public void addFirst(E element) {
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        front = (front - 1 + data.length) % data.length;
        data[front] = element;
        size++;
    }

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

    @Override
    public void addLast(E element) {
        //判断是否要扩容
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        //让元素直接去rear
        data[rear] = element;
        //(有循坏在）rear向后移
        rear = (rear + 1) % data.length;
        size++;
    }

    @Override
    public E removeFirst() {
        //删之前先判断空
     
    @Override
    public E removeLast() {
        //removefirst是先让rear向前移指向元素，再把该元素删除
        //删之前先判断空
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        rear = (rear - 1 + data.length) % data.length;
        E ret = data[rear];
        size--;
        //判断是否要缩容
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    @Override
    public E getFirst() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        return data[front];
    }

    @Override
    public E getLast() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        return data[(rear - 1 + data.length) % data.length];
    }

    @Override
    //入队
    public void offer(E element) {
        addLast(element);

    }

    @Override
    //出队
    public E poll() {
        return removeFirst();
    }

    @Override
    public E peek() {
        return getFirst();
    }

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

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

    }

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

    @Override
    public Iterator<E> iterator() {
        return new ArrayDequeIterator();
    }

    class ArrayDequeIterator implements Iterator<E> {
        private int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            return null;
        }
    }
}