队列：顺序队列

使用数组实现的队列
时间复杂度
入队：最好O(1) 最坏O(n) 均摊O(1）
出队：O(1)

接口类：

public interface Queue<E> {
    void enqueue(E e);
    E dequeue();
    E getFront();
    int getSize();
    boolean isEmpty();
}

实现类：

public class ArrayQueue<E> implements Queue<E> {
    private E[] data ;
    private int size ;
    private int head;
    private int tail;
    private int capacity;

    public ArrayQueue(int capacity){
       this.data = (E[]) new Object[capacity];
        this.size = 0;
        this.head = 0;
        this.tail = 0;
        this.capacity = capacity;

    }

    @Override
    public void enqueue(E e) {
        //判断是否队满了
        if (tail == capacity){
            if (head == 0)
            throw new IllegalArgumentException("队满了无法插入");

            for (int i = head; i < tail ; i++){
                data[i-head] = data[i];
            }

            tail -= head;
            head = 0;
        }
        data[tail] = e;
        tail++;
        size++;
    }

    @Override
    public E dequeue() {

        if (isEmpty())
            throw new IllegalArgumentException("队列是空的，无法删除元素");

        E r = data[head];
        head++;
        size--;
        return r;
    }

    @Override
    public E getFront() {
        return data[head];
    }

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

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

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder("[size:"+getSize() + " capacity:"+capacity+" head  ");

        for (int i = head ; i < tail ; i++){
            if (i != tail-1)
            res.append(data[i]+",");
            else res.append(data[i]+"  tail]");
        }
        return res.toString();
    }
}

测试：

public class Main {

    public static void main(String[] args) {
    Queue<Integer> queue = new ArrayQueue<>(10);

    for (int i = 0 ; i < 10 ; i ++){
        queue.enqueue(i);
        System.out.println(queue);
    }


    queue.dequeue();
        System.out.println(queue);

    }
}

image.png