队列(链式队列和循环队列)

队列FIFO,先进先出。

1. API

public interface Queue<E> {
    boolean isEmpty();

    int length();

    boolean enqueue(E elem);

    E dequeue();
}

2. 链式队列

public class QueueImpl<E> implements Queue<E> {
    private Node<E> head;
    private Node<E> rear;
    private int size;

    private class Node<E> {
        Node<E> prev;
        Node<E> next;
        E elem;
    }

    public QueueImpl() {
        head = rear = new Node<>();
    }

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

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

    @Override
    public boolean enqueue(E elem) {
        Node<E> enqueue = new Node<>();
        enqueue.elem = elem;
        rear.next = enqueue;
        enqueue.prev = rear;
        rear = enqueue;
        size++;
        return true;
    }

    @Override
    public E dequeue() {
        if (size == 0) {
            return null;
        }
        head = head.next;
        size--;

        return head.elem;
    }
}

3. 循环队列

public class CircleQueue<E> implements Queue<E> {
    //元素个数
    private int size;
    //自定义容量
    private int capacity;
    //预留一个空间来判断是空还是满
    private final static int DEFAULT_CAPACITY = 11;
    //存储数据
    private Object[] elemData;
    //队列头索引
    private int head;
    //队列尾索引
    private int rear;

    public CircleQueue() {

        elemData = new Object[(capacity = DEFAULT_CAPACITY)];
    }

    public CircleQueue(int capacity) {
        this.capacity = capacity;
        elemData = new Object[capacity = (capacity + 1)];
    }

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

    /**
     * 可直接返回size
     * @return
     */
    @Override
    public int length() {
        return (rear + capacity - head) % capacity;
    }

    /**
     * (rear + 1) % capacity == head 满  当rear位于head的下面的时候,说明满了
     *
     * if (size == capacity) {
     *     return false;
     * }
     * 可相互替换
     * if ((rear + 1) % capacity == head) {
     *     return false;
     * }
     */
    @Override
    public boolean enqueue(E elem) {
        if (elem == null) {
            return false;
        }
        //
        if ((rear + 1) % capacity == head) {
            for (int i = 0; i < elemData.length; i++) {
                System.out.print(elemData[i] + "\t");
            }
            System.out.println();
            return false;
        }

        elemData[rear] = elem;
        System.out.println("current:" + rear);
        size++;
        System.out.println("next:" + (rear + 1) % capacity);
        rear = (rear + 1) % capacity;
        return true;
    }

    /**
     * rear == head的时候为空
     * if (size == 0) {
     *     return null;
     * }
     * 可相互替换
     * if (rear == head) {
     *     return null;
     * }
     */
    @Override
    public E dequeue() {
        if (rear == head) {
            return null;
        }
        E result = (E) elemData[head];
        head = (head + 1) % capacity;
        size--;
        return result;
    }
}