java一个类搞定栈、队列、双端队列

java 的Deque本身是一个双端队列，可以实现栈、队列、双端队列三种数据结构。

Deque deque = new LinkedList<>();

deque.push(1);
deque.pop();

deque.add(1);
deque.poll();

deque.addFirst(1);
deque.removeFirst();
deque.addLast(1);
deque.removeLast();

LinkedList本身是一个双向链表，每个元素的结构如下。

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

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

具有头尾指针。

    
    transient Node first;

    
    transient Node last;

头插法插入元素

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

尾插法插入元素

void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

删除头部元素并返回值

private E unlinkFirst(Node f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node 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;
}

删除尾部元素并返回值

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