0001 /* 0002 * 基于有序(非升)列表实现的优先队列 0003 */ 0004 0005 package dsa; 0006 0007 public class PQueue_SortedList implements PQueue { 0008 private List L; 0009 private Comparator C; 0010 0011 //构造方法(使用默认比较器) 0012 public PQueue_SortedList() 0013 { this(new ComparatorDefault(), null); } 0014 0015 //构造方法(使用指定比较器) 0016 public PQueue_SortedList(Comparator c) 0017 { this(c, null); } 0018 0019 //构造方法(使用指定初始元素) 0020 public PQueue_SortedList(Sequence s) 0021 { this(new ComparatorDefault(), s); } 0022 0023 //构造方法(使用指定比较器和初始元素) 0024 public PQueue_SortedList(Comparator c, Sequence s) { 0025 L = new List_DLNode(); 0026 C = c; 0027 if (null != s) 0028 while (!s.isEmpty()) { 0029 Entry e = (Entry)s.removeFirst(); 0030 insert(e.getKey(), e.getValue()); 0031 } 0032 } 0033 0034 //统计优先队列的规模 0035 public int getSize() 0036 { return L.getSize(); } 0037 0038 //判断优先队列是否为空 0039 public boolean isEmpty() 0040 { return L.isEmpty(); } 0041 0042 //若Q非空,则返回其中的最小条目(并不删除);否则,报错 0043 public Entry getMin() throws ExceptionPQueueEmpty { 0044 if (L.isEmpty()) 0045 throw new ExceptionPQueueEmpty("意外:优先队列空"); 0046 return (Entry) L.last(); 0047 } 0048 0049 //将对象obj与关键码k合成一个条目,将其插入Q中,并返回该条目 0050 public Entry insert(Object key, Object obj) throws ExceptionKeyInvalid { 0051 Entry entry = new EntryDefault(key, obj);//创建一个新条目 0052 if (L.isEmpty()//若优先队列为空 0053 || (0 > C.compare(((Entry) (L.first().getElem())).getKey(), entry.getKey()))) 0054 //或新条目是当前最大者 0055 L.insertFirst(entry);//则直接插入至表头 0056 else {//否则 0057 Position curPos = L.last();//从尾条目开始 0058 while (0 > C.compare(((Entry)(curPos.getElem())).getKey(), entry.getKey())) 0059 curPos = L.getPrev(curPos);//不断前移,直到第一个不小于entry的条目 0060 L.insertAfter(curPos, entry);//紧接该条目之后插入entry 0061 } 0062 return(entry); 0063 } 0064 0065 //若Q非空,则从其中摘除关键码最小的条目,并返回该条目;否则,报错 0066 public Entry delMin() throws ExceptionPQueueEmpty { 0067 if (L.isEmpty()) 0068 throw new ExceptionPQueueEmpty("意外:优先队列空"); 0069 return (Entry) L.remove(L.last()); 0070 } 0071 }