一个用Java实现的双向队列，可以分别在头尾插入和删除节点

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

通常使用一个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;elsefirst.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;elselast.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));elsedq.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();elsedq.removeLast();}}StdOut.println("Done!");}}