队列

计算机科学中，queue是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为尾，移除的一端称为头，就如同生活中的排队买商品

FIFO，先进先出

注意

由于有多种实现方式这里提供了接口，不同的实现方式实现接口即可

public interface Queue<T> {

    /**
     * 向队列尾部插入值
     */
    boolean offer(T t);

    /**
     * 从队列头部获取值，并移除
     */
    T poll();

    /**
     * 从队列头部获取值，不移除
     */
    T peek();

    /**
     * 队列是否为空
     */
    boolean isEmpty();

    /**
     * 容量是否已满
     */
    boolean isFull();
}

链表实现

/**
 * 链表实现（单向环形）
 */
public class LinkListQueue<T> implements Queue<T>, Iterable<T> {

    private Node<T> head = new Node(null, null);

    private Node<T> tail = head;

    private int capacity;

    private int size;

    public LinkListQueue() {
        this(Integer.MAX_VALUE);
    }

    public LinkListQueue(int capacity) {
        this.capacity = capacity;
        tail.next = head;
    }

    @Override
    public boolean offer(T t) {
        if (isFull()) {
            return false;
        }
        Node<T> added = new Node<>(t, head);
        tail.next = added;
        tail = added;
        size++;
        return true;
    }

    @Override
    public T poll() {
        if (isEmpty()) {
            return null;
        }
        Node<T> first = head.next;
        head.next = first.next;
        if (first == tail) {
            tail = head;
        }
        size--;
        return first.value;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return head.next.value;
    }

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

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node next = head.next;

            @Override
            public boolean hasNext() {
                return next != head;
            }

            @Override
            public T next() {
                T value = (T) next.value;
                next = next.next;
                return value;
            }
        };
    }


    static class Node<T> {

        Node<T> next;
        T value;


        public Node(T value, Node<T> next) {
            this.next = next;
            this.value = value;
        }
    }

    @Override
    public String toString() {
        return "LinkListQueue{" +
                "head=" + head +
                ", tail=" + tail +
                '}';
    }

}

数字实现

这里是使用了一个算法 尾节点 + 1 取模数组长度，得到的索引是跳过了0，0索引用来头节点占用不保存内容， 也可以再增加一个属性 size，每次操作的时候根据size判断满了还是没满

public class ArrayListQueue<T> implements Queue<T> {

    private T[] arr;

    //头节点
    private int start;
    //尾节点
    private int end;

    public ArrayListQueue(int capacity) {
        this.arr = (T[]) new Object[capacity + 1];
    }

    @Override
    public boolean offer(T t) {
        if (isFull()) {
            return false;
        }
        arr[end] = t;
        end = getInsertIndex();
        return true;
    }

    private int getInsertIndex() {
        return (end + 1) % arr.length;
    }

    @Override
    public T poll() {
        T t = arr[getInsertIndex()];
        end = getInsertIndex();
        return t;
    }

    @Override
    public T peek() {
        return arr[getInsertIndex()];
    }

    @Override
    public boolean isEmpty() {
        return start == end;
    }

    @Override
    public boolean isFull() {
        return ((end + 1) % arr.length) == start;
    }

}