Go语言视频零基础入门到精通

ddjava

   java库里的PriorityQueue无法满足我，它不能固定容量，不遍历（遍历后就无序了），它的排序因字是从小到大（虽然可以用Comparator来反转大小顺序）。我所要的是可以固定容量（在一大堆数据通信中选择最大或最小的几个数时很有用），可遍历（不是一个个poll()）。

   于是，在有空的时间里写了一下。内容是一个双向链表（带头的，头不作保存数据），用插入排序。个人认为一个个添加的用插入排序效果比较好。从队尾到队头找合适的插入位置，是稳定的排序。添加的实体可以用Comparator或Comparable，如果这两个都不是，就失去排序的效果

2. import java.util.AbstractQueue;
3. import java.util.Comparator;
4. import java.util.Iterator;
6. /**
7. * @param <E>
8. * 容量capacity大于0,最多只能添加capacity个,多出的被删除掉.<br/>
9. * 删除时根据{@link Comparable}或{@link Comparator} 和 desc
10. * 如果comparator==null时使用Comparable<br/>
11. * non-thread safe
12. * @author chenlb 2008-4-23 下午11:31:06
13. */
14. public class TopPriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
16.     private static final long serialVersionUID = 1L;
18.     private int size;
19.     private LinkedItem head;
20.     private LinkedItem last;
21.     private int top;    //top>0后,容量有限制
22.     private Comparator<? super E> comparator;
23.     private boolean desc;    //降序
24.    
25.     /**
26.      * 容量无限制,升序.
27.      */
28.     public TopPriorityQueue() {
29.         this(0, null, false);
30.     }
31.    
32.     /**
33.      * 容量无限制,
34.      * @param desc true为降序.
35.      */
36.     public TopPriorityQueue(boolean desc) {
37.         this(0, null, desc);
38.     }
40.     /**
41.      * 容量无限制,升序,用comparator排序
42.      */
43.     public TopPriorityQueue(Comparator<? super E> comparator) {
44.         this(0, comparator, false);
45.     }
46.    
47.     /**
48.      * 容量无限制,用comparator排序
49.      * @param desc true为降序
50.      */
51.     public TopPriorityQueue(Comparator<? super E> comparator, boolean desc) {
52.         this(0, comparator, desc);
53.     }
54.    
56.     /**
57.      * 容量限制为capacity.超出容量限制的,会删除优先级最小(队尾).
58.      */
59.     public TopPriorityQueue(int capacity) {
60.         this(capacity, null, false);
61.     }
62.    
63.     public TopPriorityQueue(int capacity, boolean desc) {
64.         this(capacity, null, desc);
65.     }
66.    
67.     public TopPriorityQueue(int capacity, Comparator<? super E> comparator) {
68.         this(capacity, comparator, false);
69.     }
70.    
71.     public TopPriorityQueue(int capacity, Comparator<? super E> comparator, boolean desc) {
72.         head = new LinkedItem();
73.         last = head;
74.         top = capacity;
75.         this.comparator = comparator;
76.         this.desc = desc;
77.     }
78.     @Override
79.     public Iterator<E> iterator() {
80.         // TODO 迭代器
81.         return new It(head);
82.     }
84.     @Override
85.     public int size() {
86.         return size;
87.     }
89.    
90.     public boolean offer(E o) {
91.         // TODO 添加到适当的位置
92.         if(o == null) {
93.             throw new IllegalArgumentException("不能添加值为null的!");
94.         }
95.         LinkedItem temp = new LinkedItem(o);
96.         /*last.next = temp;
97.         temp.prev = last;*/
98.         if(last == head) {    //第一个
99.             last.next = temp;
100.             temp.prev = last;
101.             
102.             last = temp;
103.         } else {
104.             LinkedItem tempPrev = last;
105.             if(comparator != null) {
106.                 while(tempPrev!=null && tempPrev != head) {
107.                
108.                     int r = comparator.compare(tempPrev.data, temp.data);
109.                     if(desc) {
110.                         r = 0 - r;
111.                     }
112.                     if(r == 1) {    //tempPrev > temp
113.                         //重置,继续向前找
114.                         tempPrev = tempPrev.prev;
115.                     } else {    //找到插入的位置
116.                         break;
117.                     }
118.                 }
119.                
120.             } else if(o instanceof Comparable) {    //用Comparable
121.                
122.                 while(tempPrev!=null && tempPrev != head) {
123.                     Comparable<E> tPrev = (Comparable<E>) tempPrev.data;
124.                     int r = tPrev.compareTo(temp.data);
125.                     if(desc) {
126.                         r = 0 - r;
127.                     }
128.                     if(r == 1) {    //tempPrev > temp
129.                         //重置,继续向前找
130.                         tempPrev = tempPrev.prev;
131.                     } else {    //找到插入的位置
132.                         break;
133.                     }
134.                 }
135.             }
136.             if(tempPrev != null) {    //插入
137.                 if(tempPrev == last) {    //后面添加的
138.                     last = temp;
139.                 }
140.                
141.                 temp.next = tempPrev.next;
142.                 if(tempPrev.next != null) {
143.                     tempPrev.next.prev = temp;
144.                 }
145.                 tempPrev.next = temp;
146.                 temp.prev = tempPrev;
147.             }
148.         }
149.         
150.         size++;
151.         if(top > 0 && size > top) {    //去掉优先级最小的
152.             tail();
153.         }
154.         return true;
155.     }
157.     /**
158.      * 从栈底去除
159.      */
160.     public E tail() {
161.         if(last == head) {
162.             return null;
163.         }
164.         LinkedItem laster = last;
165.         last = last.prev;
166.         last.next = null;
167.         laster.prev = null;
168.         size--;
169.         return laster.data;
170.     }
171.    
172.     public E peek() {
173.         // TODO 取得栈顶值
174.         LinkedItem first = head.next;
175.         if(first != null) {
176.             return first.data;
177.         }
178.         return null;
179.     }
181.    
182.     public E poll() {
183.         // TODO 从栈顶去除
184.         LinkedItem first = head.next;
185.         if(first != null) {
186.             head.next = first.next;
187.             if(first.next != null) {
188.                 first.next.prev = head;
189.             }
190.             size--;
191.             return first.data;
192.         }
193.         return null;
194.     }
196.     private class It implements Iterator<E> {
198.         LinkedItem curr;
199.         
200.         public It(LinkedItem curr) {
201.             super();
202.             this.curr = curr;
203.         }
205.         
206.         public boolean hasNext() {
207.             if(curr != null && curr.next != null) {
208.                 return true;
209.             }
210.             return false;
211.         }
213.         
214.         public E next() {
215.             curr = curr.next;
216.             E d = curr.data;
217.             return d;
218.         }
220.         
221.         public void remove() {
222.             curr.prev.next = curr.next;
223.             if(curr.next != null) {
224.                 curr.next.prev = curr.prev;
225.             }
226.             size--;
227.         }
228.         
229.     }
230.    
231.     /**
232.      * @param <E>
233.      * 链结点.
234.      * @author chenlb 2008-5-4 下午04:48:17
235.      */
236.     private class LinkedItem {
237.         LinkedItem prev;
238.         E data;
239.         LinkedItem next;
240.         public LinkedItem() {
241.         }
242.         public LinkedItem(E o) {
243.             this.data = o;
244.         }
245.     }
246. }

复制代码

lwenw22

谢谢哦啊。