除了可以通过一维数组，单链表实现queue队列，还可以通过双链表实现queue队列。
在基于NLNode类实现双向链表的时候，为了使编程更加简洁，，通常我们都要在最前端和最后端各设置一个哑元节点（ Dummy node ）。这两个节点分别称作头节点（ Header node ）和尾节点（ Trailer node） ㈠，起哨兵（ Sentinel）的作用。也就是说，它们并不存储任何实质的数据对象，头（尾）节点的next（ prev）引用指向首（末）节点，而prev（next）引用为空。如此构成的双向链表结构，如下代码示：
Java代码：
DoubleNode 类：
package com.doub.list;/** * * @author gannyee * */{//Declared elementprivate Object element;//Declared priorprivate DoubleNode prior;//Declared nextprivate DoubleNode next;(){this(null,null,null);}public DoubleNode(DoubleNode prior,Object element, DoubleNode next){this.prior = prior;this.element = element;this.next = next;}//Get elementpublic Object getElement() {return element;}(Object element) {this.element = element;}//Get priorpublic DoubleNode getPrior() {return prior;}(DoubleNode prior) {this.prior = prior;}//Get nextpublic DoubleNode getNext() {return next;}(DoubleNode next) {this.next = next;}}
DoubleListQueue 类：
package com.doub.list;import java.util.Arrays;import com.queue.ExceptionQueueEmpty;{DoubleNode head;DoubleNode rear;size;length;() {//initialize head = new DoubleNode();rear = new DoubleNode();head.setNext(rear);head.setPrior(null);rear.setNext(null);rear.setPrior(head);this.size = this.length = 0;}() {return size;}(){return length;}() {return size == 0;}(Object element) {DoubleNode newNode = new DoubleNode(head,element,head.getNext());head.getNext().setPrior(newNode);head.setNext(newNode);size ++;length = size;}(Object element) {DoubleNode newNode = new DoubleNode(rear.getPrior(),element,rear);rear.getPrior().setNext(newNode);rear.setPrior(newNode);size ++;length = size;}() throws ExceptionQueueEmpty{if(isEmpty())throw new ExceptionQueueEmpty(“Queue is empty”);head.getNext().getNext().setPrior(head);head.setNext(head.getNext().getNext());size –;}() throws ExceptionQueueEmpty{if(isEmpty())throw new ExceptionQueueEmpty(“Queue is empty”);rear.getPrior().getPrior().setNext(rear);rear.setPrior(rear.getPrior().getPrior());size –;}// Get first node but not isn’t deletionpublic Object getFirst() throws ExceptionQueueEmpty{if(isEmpty())throw new ExceptionQueueEmpty(“Queue is empty”);return head.getNext().getElement();}// Get last node but not isn’t deletionpublic Object getLast() throws ExceptionQueueEmpty{if(isEmpty())throw new ExceptionQueueEmpty(“Queue is empty”);return rear.getPrior().getElement();}(){Object[] array = new Object[getSize()];DoubleNode travelNode = new DoubleNode();travelNode = head.getNext();for(int i = 0; travelNode != rear;i ++){array[i] = travelNode.getElement();travelNode = travelNode.getNext();}System.out.println(“All elements are: ” + Arrays.toString(array));}}
DoubleListQueueTest 类：
package import /** * * @author gannyee * */public class DoubleListQueueTest {public static void main(String[] args) throws ExceptionQueueEmpty {DoubleListQueue dlq = new DoubleListQueue();System.out.println(“Size: ” + dlq.getSize());System.out.println(“Is empty? ” + dlq.isEmpty());for(int i = 0;i < 6;i ++){dlq.insertFirst(i);}System.out.println(“Size: ” + dlq.getSize());System.out.println(“Is empty? ” + dlq.isEmpty());dlq.getAllElements();System.out.println(dlq.getFirst());System.out.println(dlq.getLast());for(int i = 0;i < 6;i ++){dlq.insertLast(i + 1);}System.out.println(“Size: ” + dlq.getSize());System.out.println(“Is empty? ” + dlq.isEmpty());dlq.getAllElements();System.out.println(dlq.getFirst());System.out.println(dlq.getLast());for(int i = 0;i < 6;i ++){dlq.removeFirst();}System.out.println(“Size: ” + dlq.getSize());System.out.println(“Is empty? ” + dlq.isEmpty());dlq.getAllElements();System.out.println(dlq.getFirst());System.out.println(dlq.getLast());for(int i = 0;i < 6;i ++){dlq.removeLast();}System.out.println(“Size: ” + dlq.getSize());System.out.println(“Is empty? ” + dlq.isEmpty());dlq.getAllElements();}}人生伟业的建立 ，不在能知，乃在能行。
