队列：循环队列

基于非动态数组实现的循环队列

循环队列.PNG

时间复杂度
入队：O(1)
出队：O(1)

接口类：

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

实现类：

public class CircularQueue<E> implements Queue<E> {

    private E[] data ;
    private int head;
    private int tail;
    private int size ;
    private int capacity;

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

    @Override
    public void enqueue(E e) {
        //队满条件为(tail+1)%capacity == head
        if ((tail+1)%capacity == head){
            throw new IllegalArgumentException("队满无法添加元素");
        }
        data[tail] = e;
        tail = (tail+1)%capacity;
        size++;

    }

    @Override
    public E dequeue() {

        if (tail == head){
            throw new IllegalArgumentException("队列为空，无法删除元素");

        }

        E r = data[head];

        head = (head+1)%capacity;
        size--;
        return r;
    }

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

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

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

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size=%d , capacity = %d\n",size ,capacity));
        res.append("head[");
        for (int i = 0; i <size ; i++){
            res.append(data[(i+head)%data.length]);
            if( (i+head+1)%data.length != tail){
                res.append(",");
            }
        }
        res.append("]tail");
        return res.toString();
    }
}

测试：

public class Main {

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

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

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


      System.out.println(queue.getFront());
      System.out.println(queue.getSize());
    }
}

image.png