本文共 6664 字，大约阅读时间需要 22 分钟。

分析，双向队列的内部实现是一个双向链表，可以分别从头尾插入和删除节点。

通常使用一个first指向头 last指向尾。然后分别维护各种next和prev指针。通常情况要考虑边界条件，即当队列本身为空的时候插入新节点如何维护first和last的指向

删除节点的时候，若队列变为空又应该如何维护first和last指针。非常繁琐而且容易写错，不过使用的空间最少，代码如下

import java.util.Iterator;import java.util.NoSuchElementException;import edu.princeton.cs.algs4.StdOut;public class Deque<Item> implements Iterable<Item> {    private int n;    private Node first;    private Node last;    private class Node {        private Item item;        private Node next;        private Node prev;    }    public Deque() {        n = 0;        first = null;        last = null;    }    public boolean isEmpty() {        return first == null;    }    public int size() {        return n;    }    public void addFirst(Item item) {        if (item == null)            throw new NullPointerException("can't add null element!");        Node oldfirst = first;        first = new Node();        first.item = item;        first.prev = null;        // it is and empty queue..        if (oldfirst == null) {            last = first;            first.next = null;        }        else {            first.next = oldfirst;            oldfirst.prev = first;        }        n++;    }    public void addLast(Item item) {        if (item == null)            throw new NullPointerException("can't add null element!");        Node oldlast = last;        last = new Node();        last.item = item;        last.next = null;        if (oldlast == null) {            first = last;            last.prev = null;        } else {            last.prev = oldlast;            oldlast.next = last;        }        n++;    }    public Item removeFirst() {        if (isEmpty())            throw new NoSuchElementException(                    "Can't remove from empty deque");        Item item = first.item;        first = first.next;        n--;        if (n == 0)            last = null;        else            first.prev = null;        return item;    }    public Item removeLast() {        if (isEmpty())            throw new NoSuchElementException(                    "Stack underflow");        Item item = last.item;        last = last.prev;        n--;        if (n == 0)            first = null;        else            last.next = null;        return item;    }    public Iterator<Item> iterator() {        return new DequeIterator();    }    private class DequeIterator implements Iterator<Item> {        private Node current = first;        public boolean hasNext() {            return current != null;        }        public void remove() {            throw new UnsupportedOperationException(                    "remove is not supported!");        }        public Item next() {            if (!hasNext())                throw new NoSuchElementException();            Item item = current.item;            current = current.next;            return item;        }    }    public static void main(String[] args) {        Deque<String> dq = new Deque<String>();        dq.addFirst("A");        dq.addFirst("B");        dq.addFirst("C");        dq.addLast("Q");        dq.addLast("E");        dq.addLast("D");        for (String s : dq) {            StdOut.println(s);        }        StdOut.println("Remove first" + dq.removeFirst());        StdOut.println("Remove last" + dq.removeLast());        for (String s : dq) {            StdOut.println(s);        }    }}

另一种方法是引入一个哨兵节点nil， 初始化时nil的prev和next分别指向自身。用于判断队列是否为空

加入新元素以后只需要操作新增节点，nil 和 nil的下一个节点。不需要考虑边界情况（因为没有nullpointer）

该方法仅多使用了一个节点的空间，但是代码看起来更加简洁如下

import java.util.Iterator;import java.util.NoSuchElementException;import edu.princeton.cs.algs4.StdOut;import edu.princeton.cs.algs4.StdRandom;public class Deque<Item> implements Iterable<Item> {    private int n;    private Node nil;    private class Node {        private Item item;        private Node next;        private Node prev;    }    public Deque() {        n = 0;        nil = new Node();        nil.next = nil;        nil.prev = nil;    }    public boolean isEmpty() {        return nil.next == nil;    }    public int size() {        return n;    }    public void addFirst(Item item) {        if (item == null)            throw new NullPointerException("can't add null element!");        Node first = new Node();        first.item = item;        first.prev = nil;        first.next = nil.next;        nil.next.prev = first;        nil.next = first;                n++;    }    public void addLast(Item item) {        if (item == null)            throw new NullPointerException("can't add null element!");        Node last = new Node();        last.item = item;        last.next = nil;        last.prev = nil.prev;        nil.prev.next = last;        nil.prev = last;        n++;    }    public Item removeFirst() {        if (isEmpty())            throw new NoSuchElementException(                    "Can't remove from empty deque");        Node del = nil.next;        Item item = del.item;        del.next.prev = nil;        nil.next = del.next;        n--;        return item;    }    public Item removeLast() {        if (isEmpty())            throw new NoSuchElementException(                    "Stack underflow");        Node del = nil.prev;        Item item = del.item;        del.prev.next = nil;        nil.prev = del.prev;        n--;        return item;    }    public Iterator<Item> iterator() {        return new DequeIterator();    }    private class DequeIterator implements Iterator<Item> {        private Node current = nil.next;        public boolean hasNext() {            return current != nil;        }        public void remove() {            throw new UnsupportedOperationException(                    "remove is not supported!");        }        public Item next() {            if (!hasNext())                throw new NoSuchElementException();            Item item = current.item;            current = current.next;            return item;        }    }    public static void main(String[] args) {        Deque<Integer> dq = new Deque<Integer>();        for (int i = 0; i < 10; i++) {            int r = StdRandom.uniform(1, 65535);            StdOut.println("Random add and remove node for " + r);            for (int j = 0; j < r; j++) {               if (StdRandom.uniform() > 0.5)                   dq.addFirst(StdRandom.uniform(0, 10));               else                   dq.addLast(StdRandom.uniform(0, 10));            }            for (int n : dq)                StdOut.println(n);             for (int j = 0; j < r; j++) {                if (StdRandom.uniform() > 0.5)                    dq.removeFirst();                else                    dq.removeLast();            }        }        StdOut.println("Done!");    }}