//Deque.java
package dsa; //根據自己的程序位置不同
public interface Deque {
public int getSize();//返回隊列中元素數目
public boolean isEmpty();//判斷隊列是否為空
public Object first() throws ExceptionQueueEmpty;//取首元素（但不刪除）
public Object last() throws ExceptionQueueEmpty;//取末元素（但不刪除）
public void insertFirst(Object obj);//將新元素作為首元素插入
public void insertLast(Object obj);//將新元素作為末元素插入
public Object removeFirst() throws ExceptionQueueEmpty;//刪除首元素
public Object removeLast() throws ExceptionQueueEmpty;//刪除末元素
public void Traversal();//遍歷
}
雙向鏈表實現：
//Deque_DLNode.java
/*
* 基於雙向鏈表實現雙端隊列結構
*/
package dsa;
public class Deque_DLNode implements Deque {
protected DLNode header;//指向頭節點（哨兵）
protected DLNode trailer;//指向尾節點（哨兵）
protected int size;//隊列中元素的數目
//構造函數
public Deque_DLNode() {
header = new DLNode();
trailer = new DLNode();
header.setNext(trailer);
trailer.setPrev(header);
size = 0;
}
//返回隊列中元素數目
public int getSize()
{ return size; }
//判斷隊列是否為空
public boolean isEmpty()
{ return (0 == size) ? true : false; }
//取首元素（但不刪除）
public Object first() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊列為空");
return header.getNext().getElem();
}
//取末元素（但不刪除）
public Object last() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊列為空");
return trailer.getPrev().getElem();
}
//在隊列前端插入新節點
public void insertFirst(Object obj) {
DLNode second = header.getNext();
DLNode first = new DLNode(obj, header, second);
second.setPrev(first);
header.setNext(first);
size++;
}
//在隊列後端插入新節點
public void insertLast(Object obj) {
DLNode second = trailer.getPrev();
DLNode first = new DLNode(obj, second, trailer);
second.setNext(first);
trailer.setPrev(first);
size++;
}
//刪除首節點
public Object removeFirst() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊列為空");
DLNode first = header.getNext();
DLNode second = first.getNext();
Object obj = first.getElem();
header.setNext(second);
second.setPrev(header);
size--;
return(obj);
}
//刪除末節點
public Object removeLast() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊列為空");
DLNode first = trailer.getPrev();
DLNode second = first.getPrev();
Object obj = first.getElem();
trailer.setPrev(second);
second.setNext(trailer);
size--;
return(obj);
}
//遍歷
public void Traversal() {
DLNode p = header.getNext();
while (p != trailer) {
System.out.print(p.getElem()+" ");
p = p.getNext();
}
System.out.println();
}
}