0001 /* 0002 * 基于单链表实现队列结构 0003 */ 0004 0005 package dsa; 0006 0007 public class Queue_List implements Queue { 0008 protected Node head;//指向表首元素 0009 protected Node tail;//指向表末元素 0010 protected int size;//队列中元素的数目 0011 0012 //构造方法(空队列) 0013 public Queue_List() 0014 { head = tail = null; size = 0; } 0015 0016 //查询当前队列的规模 0017 public int getSize() 0018 { return size; } 0019 0020 //判断队列是否为空 0021 public boolean isEmpty() 0022 { return (0 == size) ? true : false; } 0023 0024 //入队 0025 public void enqueue(Object obj) { 0026 Node node = new Node(); 0027 node.setElem(obj); 0028 node.setNext(null);//新节点作为末节点插入 0029 if (0 == size) head = node;//若此前队列为空,则直接插入 0030 else tail.setNext(node);//否则,将新节点接至队列末端 0031 tail = node;//更新指向末节点引用 0032 size++;//更新规模 0033 } 0034 0035 //出队 0036 public Object dequeue() throws ExceptionQueueEmpty { 0037 if (0 == size) 0038 throw new ExceptionQueueEmpty("意外:队列空"); 0039 Object obj = head.getElem(); 0040 head = head.getNext(); 0041 size--; 0042 if (0 == size) tail = null;//若队列已空,须将末节点引用置空 0043 return obj; 0044 } 0045 0046 //取(并不删除)队首元素 0047 public Object front() throws ExceptionQueueEmpty { 0048 if (isEmpty()) 0049 throw new ExceptionQueueEmpty("意外:队列空"); 0050 return head.getElem(); 0051 } 0052 0053 //遍历(不属于ADT) 0054 public void Traversal() { 0055 Node p = head; 0056 while (null != p) { 0057 System.out.print(p.getElem() + " "); 0058 p = p.getNext(); 0059 } 0060 } 0061 }