0001 /* 0002 * 基于双向链表实现双端队列结构 0003 */ 0004 0005 package dsa; 0006 0007 public class Deque_DLNode implements Deque { 0008 protected DLNode header;//指向头节点(哨兵) 0009 protected DLNode trailer;//指向尾节点(哨兵) 0010 protected int size;//队列中元素的数目 0011 0012 //构造函数 0013 public Deque_DLNode() { 0014 header = new DLNode(); 0015 trailer = new DLNode(); 0016 header.setNext(trailer); 0017 trailer.setPrev(header); 0018 size = 0; 0019 } 0020 0021 //返回队列中元素数目 0022 public int getSize() 0023 { return size; } 0024 0025 //判断队列是否为空 0026 public boolean isEmpty() 0027 { return (0 == size) ? true : false; } 0028 0029 //取首元素(但不删除) 0030 public Object first() throws ExceptionQueueEmpty { 0031 if (isEmpty()) 0032 throw new ExceptionQueueEmpty("意外:双端队列为空"); 0033 return header.getNext().getElem(); 0034 } 0035 0036 //取末元素(但不删除) 0037 public Object last() throws ExceptionQueueEmpty { 0038 if (isEmpty()) 0039 throw new ExceptionQueueEmpty("意外:双端队列为空"); 0040 return trailer.getPrev().getElem(); 0041 } 0042 0043 //在队列前端插入新节点 0044 public void insertFirst(Object obj) { 0045 DLNode second = header.getNext(); 0046 DLNode first = new DLNode(obj, header, second); 0047 second.setPrev(first); 0048 header.setNext(first); 0049 size++; 0050 } 0051 0052 //在队列后端插入新节点 0053 public void insertLast(Object obj) { 0054 DLNode second = trailer.getPrev(); 0055 DLNode first = new DLNode(obj, second, trailer); 0056 second.setNext(first); 0057 trailer.setPrev(first); 0058 size++; 0059 } 0060 0061 //删除首节点 0062 public Object removeFirst() throws ExceptionQueueEmpty { 0063 if (isEmpty()) 0064 throw new ExceptionQueueEmpty("意外:双端队列为空"); 0065 DLNode first = header.getNext(); 0066 DLNode second = first.getNext(); 0067 Object obj = first.getElem(); 0068 header.setNext(second); 0069 second.setPrev(header); 0070 size--; 0071 return(obj); 0072 } 0073 0074 //删除末节点 0075 public Object removeLast() throws ExceptionQueueEmpty { 0076 if (isEmpty()) 0077 throw new ExceptionQueueEmpty("意外:双端队列为空"); 0078 DLNode first = trailer.getPrev(); 0079 DLNode second = first.getPrev(); 0080 Object obj = first.getElem(); 0081 trailer.setPrev(second); 0082 second.setNext(trailer); 0083 size--; 0084 return(obj); 0085 } 0086 0087 //遍历 0088 public void Traversal() { 0089 DLNode p = header.getNext(); 0090 while (p != trailer) { 0091 System.out.print(p.getElem() + " "); 0092 p = p.getNext(); 0093 } 0094 System.out.println(); 0095 } 0096 }