Java 集合之 Queue

1. 线性数据结构

• 数组、链表、栈、队列

1.1 队列

Queue 是一种遵循先进先出（FIFO: First In, First Out）原则的数据集合，数据在Queue中的流动是单向的，从队尾流向队首

1.2 Queue 接口

// 继承基础集合接口Collection
public interface Queue<E> extends Collection<E> {

    boolean add(E e);  // throwing an IllegalStateException if no space
    boolean offer(E e);

    // Retrieves and removes the head of this queue
    E remove();
    E poll();

    // Retrieves, but does not remove, the head of this queue
    E element(); // throwing an NoSuchElementExceptio if this queue is empty
    E peek();
}

1.3 Deque接口

• Deque 是双端队列
• 在队尾和队首都可以 出队/入队

public interface Deque<E> extends Queue<E> {
    void addFirst(E e);
    void addLast(E e);

    boolean offerFirst(E e);
    boolean offerLast(E e);

    E removeFirst();
    E removeLast();

    E pollFirst();
    E pollLast();

    E getFirst();
    E getLast();

    E peekFirst();
    E peekLast();

    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);
}

2. LinkedList 类

2.1 双向链表

LinkedList 有两个成员变量 first 和 last，类型为Node<E>，表示队列中的首尾节点

public class LinkedList<E> extends AbstractSequentialList<E>
            implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
}

Node<E>是链表的一个节点，成员变量 item 用来存储具体的元素值，变量 next 和变量 prev 表示当前节点的后一个节点和上一个节点

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

2.2 插入元素

• add()
• offer()
• offerFirst() / offerLast()

    public boolean offer(E e) {
        return add(e);
    }

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        // 集合修改次数+1
        modCount++;
    }

    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
    public void addFirst(E e) {
        linkFirst(e);
    }
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

2.3 删除元素

• poll()
• pollFirst() / pollLast()

    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

最终调用的都是 unlinkFirst() 和unlinkLast() ，表示删除链表头部和链表尾部的节点

    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }