/* * 基于雙向鏈表實現(xiàn)雙端隊列結(jié)構(gòu) */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向頭節(jié)點（哨兵） protected DLNode trailer;//指向尾節(jié)點（哨兵） protected int size;//隊列中元素的數(shù)目 //構(gòu)造函數(shù) public Deque_DLNode() { header = new DLNode(); trailer = new DLNode(); header.setNext(trailer); trailer.setPrev(header); size = 0; } //返回隊列中元素數(shù)目 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(); } //在隊列前端插入新節(jié)點 public void insertFirst(Object obj) { DLNode second = header.getNext(); DLNode first = new DLNode(obj, header, second); second.setPrev(first); header.setNext(first); size++; } //在隊列后端插入新節(jié)點 public void insertLast(Object obj) { DLNode second = trailer.getPrev(); DLNode first = new DLNode(obj, second, trailer); second.setNext(first); trailer.setPrev(first); size++; } //刪除首節(jié)點 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); } //刪除末節(jié)點 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.getNex