一、隊(duì)列的概念：
隊(duì)列（簡(jiǎn)稱(chēng)作隊(duì)，Queue）也是一種特殊的線性表，隊(duì)列的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線性表完全相同，其差別是線性表允許在任意位置插入和刪除，而隊(duì)列只允許在其一端進(jìn)行插入操作在其另一端進(jìn)行刪除操作。
隊(duì)列中允許進(jìn)行插入操作的一端稱(chēng)為隊(duì)尾，允許進(jìn)行刪除操作的一端稱(chēng)為隊(duì)頭。隊(duì)列的插入操作通常稱(chēng)作入隊(duì)列，隊(duì)列的刪除操作通常稱(chēng)作出隊(duì)列。
下圖是一個(gè)依次向隊(duì)列中插入數(shù)據(jù)元素a0,a1,...,an-1后的示意圖：
上圖中，a0是當(dāng)前 隊(duì)頭數(shù)據(jù)元素，an-1是當(dāng)前 隊(duì)尾數(shù)據(jù)元素。
為了避免當(dāng)只有一個(gè)元素時(shí)，對(duì)頭和隊(duì)尾重合使得處理變得麻煩，所以引入兩個(gè)指針：front指針指向隊(duì)頭元素，rear指針指向隊(duì)尾元素的下一個(gè)位置，這樣的話，當(dāng)front指針等于rear時(shí)，此隊(duì)列不是還剩一個(gè)元素，而是空隊(duì)列。
二、隊(duì)列的抽象數(shù)據(jù)類(lèi)型：
數(shù)據(jù)集合：
隊(duì)列的數(shù)據(jù)集合可以表示為a0,a1,…,an-1，每個(gè)數(shù)據(jù)元素的數(shù)據(jù)類(lèi)型可以是任意的類(lèi)型。
操作集合：
（1）入隊(duì)列append(obj)：把數(shù)據(jù)元素obj插入隊(duì)尾。
（2）出隊(duì)列delete()：把隊(duì)頭數(shù)據(jù)元素刪除并由函數(shù)返回。
（3）取隊(duì)頭數(shù)據(jù)元素getFront()：取隊(duì)頭數(shù)據(jù)元素并由函數(shù)返回。
（4）非空否isEmpty()：非空否。若隊(duì)列非空，則函數(shù)返回false，否則函數(shù)返回true。
三、循環(huán)順序隊(duì)列：
線性表有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，隊(duì)列是一種特殊的線性表，同樣也存在這兩種存儲(chǔ)方式。我們先來(lái)看一下隊(duì)列的順序存儲(chǔ)。
1、順序隊(duì)列的“假溢出”：
上圖中，front指針指向隊(duì)頭元素，rear指針指向隊(duì)尾元素的下一個(gè)位置。圖(d)中b、c、d出隊(duì)后，front指針指向元素e，rear指針在數(shù)組外面。假設(shè)這個(gè)隊(duì)列的總個(gè)數(shù)不超過(guò)5個(gè)，但目前如果接著入隊(duì)的話，因數(shù)組末尾元素已經(jīng)被占用，再向后加就會(huì)產(chǎn)生數(shù)組越界的錯(cuò)誤，可實(shí)際上隊(duì)列在下標(biāo)為0、1、2、3、4的地方還是空閑的，我們把這種現(xiàn)象叫做“假溢出”。
2、循環(huán)順序隊(duì)列：
所以解決假溢出的辦法就是后面滿了，就再?gòu)念^開(kāi)始，也就是頭尾相接的循環(huán)。我們把隊(duì)列的這種邏輯上首尾相連的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)為循環(huán)隊(duì)列。
如何判斷循環(huán)隊(duì)列究竟是空的還是滿的：
現(xiàn)在問(wèn)題又來(lái)了，我們之前說(shuō)，空隊(duì)列時(shí)，front指針等于rear指針，那么現(xiàn)在循環(huán)隊(duì)列滿的時(shí)候，也是front等于rear，那么如何判斷循環(huán)隊(duì)列究竟是空的還是滿的？有如下辦法：
我們?cè)诮酉聛?lái)的代碼中采用方法3來(lái)實(shí)現(xiàn)。
3、代碼實(shí)現(xiàn)：(循環(huán)順序隊(duì)列的創(chuàng)建)
(1)Queue.java:(隊(duì)列接口)
1 //隊(duì)列接口 2 public interface Queue { 3 4 //入隊(duì) 5 public void append(Object obj) throws Exception; 6 7 //出隊(duì) 8 public Object delete() throws Exception; 9 10 //獲得隊(duì)頭元素11 public Object getFront() throws Exception;12 13 //判斷對(duì)列是否為空14 public boolean isEmpty();15 }
(2)CircleSequenceQueue.java:（循環(huán)順序隊(duì)列）
1 //循環(huán)順序隊(duì)列 2 public class CircleSequenceQueue implements Queue { 3 4 static final int defaultSize = 10; //默認(rèn)隊(duì)列的長(zhǎng)度 5 int front; //隊(duì)頭 6 int rear; //隊(duì)尾 7 int count; //統(tǒng)計(jì)元素個(gè)數(shù)的計(jì)數(shù)器 8 int maxSize; //隊(duì)的最大長(zhǎng)度 9 Object[] queue; //隊(duì)列10 11 public CircleSequenceQueue() {12 init(defaultSize);13 }14 15 public CircleSequenceQueue(int size) {16 init(size);17 }18 19 public void init(int size) {20 maxSize = size;21 front = rear = 0;22 count = 0;23 queue = new Object[size];24 }25 26 @Override27 public void append(Object obj) throws Exception {28 // TODO Auto-generated method stub29 if (count > 0 && front == rear) {30 throw new Exception("隊(duì)列已滿！");31 }32 queue[rear] = obj;33 rear = (rear + 1) % maxSize;34 count++;35 }36 37 @Override38 public Object delete() throws Exception {39 // TODO Auto-generated method stub40 if (isEmpty()) {41 throw new Exception("隊(duì)列為空！");42 }43 Object obj = queue[front];44 front = (front + 1) % maxSize;45 count--;46 return obj;47 }48 49 @Override50 public Object getFront() throws Exception {51 // TODO Auto-generated method stub52 if (!isEmpty()) {53 return queue[front];54 } else {55 return null;56 }57 }58 59 @Override60 public boolean isEmpty() {61 // TODO Auto-generated method stub62 return count == 0;63 }64 65 }
(3)Test.java:
1 public class Test { 2 public static void main(String[] args) throws Exception { 3 4 CircleSequenceQueue queue = new CircleSequenceQueue(); 5 queue.append("a"); 6 queue.append("b"); 7 queue.append("c"); 8 queue.append("d"); 9 queue.append("e");10 queue.append("f");11 12 queue.delete();13 queue.delete();14 15 queue.append("g");16 17 while (!queue.isEmpty()) {18 System.out.PRintln(queue.delete());19 }20 }21 }
運(yùn)行效果：
4、循環(huán)隊(duì)列應(yīng)用：
使用順序循環(huán)隊(duì)列和多線程實(shí)現(xiàn)一個(gè)排隊(duì)買(mǎi)票的例子。而且，我們只允許這個(gè)隊(duì)伍中同時(shí)排隊(duì)的只有10個(gè)人，那就需要用到隊(duì)列了。
生產(chǎn)者（等候買(mǎi)票）
消費(fèi)者 (買(mǎi)票離開(kāi))
這里面我們需要用到上面的Queue.java類(lèi)和CircleSequenceQueue.java類(lèi)。
代碼結(jié)構(gòu)：
(3)WindowQueue.java:
1 //賣(mài)票窗口 2 public class WindowQueue { 3 4 //賣(mài)票的隊(duì)列 5 int maxSize = 10; 6 CircleSequenceQueue queue = new CircleSequenceQueue(maxSize); 7 int num = 0; //統(tǒng)計(jì)賣(mài)票的數(shù)量，一天最多賣(mài)100張票。 8 boolean isAlive = true; //判斷是否繼續(xù)賣(mài)票。 9 10 //排隊(duì)買(mǎi)票11 public synchronized void producer() throws Exception {12 if (queue.count < maxSize) {13 queue.append(num++); //等待買(mǎi)票的數(shù)量加114 System.out.println("第" + num + "個(gè)客戶排隊(duì)等待買(mǎi)票！");15 this.notifyAll();//喚醒賣(mài)票的線程16 } else {17 try {18 System.out.println("隊(duì)列已滿...請(qǐng)等待！");19 this.wait();//隊(duì)列滿時(shí)，排隊(duì)買(mǎi)票線程等待。20 } catch (Exception ex) {21 ex.printStackTrace();22 }23 }24 }25 26 //賣(mài)票27 public synchronized void consumer() throws Exception {28 if (queue.count > 0) {29 Object obj = queue.delete();30 int temp = Integer.parseInt(obj.toString());31 System.out.println("第" + (temp + 1) + "個(gè)客戶買(mǎi)到票離開(kāi)隊(duì)列！");32 //如果當(dāng)前隊(duì)列為空，并且賣(mài)出票的數(shù)量大于等于100，說(shuō)明賣(mài)票結(jié)束33 if (queue.isEmpty() && this.num >= 100) {34 this.isAlive = false;35 }36 this.notifyAll(); //喚醒排隊(duì)買(mǎi)票的線程。37 } else {38 try {39 System.out.println("隊(duì)列已空...請(qǐng)等待！");40 this.wait();//隊(duì)列空時(shí)，賣(mài)票線程等待。41 } catch (Exception ex) {42 ex.printStackTrace();43 }44 }45 }46 }
(4)Producer.java:
1 //買(mǎi)票者 2 public class Producer implements Runnable { 3 4 WindowQueue queue; 5 6 public Producer(WindowQueue queue) { 7 this.queue = queue; 8 } 9 10 @Override11 public void run() {12 // TODO Auto-generated method stub13 while (queue.num < 100) {14 try {15 queue.producer();16 } catch (Exception ex) {17 ex.printStackTrace();18 }19 }20 }21 22 }
(5)Consumer.java:
//賣(mài)票者public class Consumer implements Runnable { WindowQueue queue; public Consumer(WindowQueue queue) { this.queue = queue; } @Override public void run() { // TODO Auto-generated method stub while (queue.isAlive) { try { queue.consumer(); } catch (Exception ex) { ex.printStackTrace(); } } }}
(6)test.java:
1 public class Test { 2 3 public static void main(String[] args) throws Exception { 4 5 WindowQueue queue = new WindowQueue(); 6 7 Producer p = new Producer(queue);//注意一定要傳同一個(gè)窗口對(duì)象 8 Consumer c = new Consumer(queue); 9 10 //排隊(duì)買(mǎi)票線程11 Thread pThread = new Thread(p);12 //賣(mài)票線程13 Thread cThread = new Thread(c);14 15 pThread.start(); //開(kāi)始排隊(duì)買(mǎi)票16 cThread.start(); //開(kāi)始賣(mài)票17 }18 19 }
注意第07行的注釋。
運(yùn)行效果：
四、鏈?zhǔn)疥?duì)列：
鏈?zhǔn)疥?duì)列其實(shí)就是特殊的單鏈表，只不過(guò)它只能尾進(jìn)頭出而已。鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)如下圖所示：
1、鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)：
(1)Node.java:結(jié)點(diǎn)類(lèi)
1 //結(jié)點(diǎn)類(lèi) 2 public class Node { 3 4 Object element; //數(shù)據(jù)域 5 Node next; //指針域 6 7 //頭結(jié)點(diǎn)的構(gòu)造方法 8 public Node(Node nextval) { 9 this.next = nextval;10 }11 12 //非頭結(jié)點(diǎn)的構(gòu)造方法13 public Node(Object obj, Node nextval) {14 this.element = obj;15 this.next = nextval;16 }17 18 //獲得當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)19 public Node getNext() {20 return this.next;21 }22 23 //獲得當(dāng)前的數(shù)據(jù)域的值24 public Object getElement() {25 return this.element;26 }27 28 //設(shè)置當(dāng)前結(jié)點(diǎn)的指針域29 public void setNext(Node nextval) {30 this.next = nextval;31 }32 33 //設(shè)置當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域34 public void setElement(Object obj) {35 this.element = obj;36 }37 38 public String toString() {39 return this.element.toString();40 }41 }
(2)Queue.java:
1 //隊(duì)列接口 2 public interface Queue { 3 4 //入隊(duì) 5 public void append(Object obj) throws Exception; 6 7 //出隊(duì) 8 public Object delete() throws Exception; 9 10 //獲得隊(duì)頭元素11 public Object getFront() throws Exception;12 13 //判斷對(duì)列是否為空14 public boolean isEmpty();15 }
(3)LinkQueue.java:
1 public class LinkQueue implements Queue { 2 3 Node front; //隊(duì)頭 4 Node rear; //隊(duì)尾 5 int count; //計(jì)數(shù)器 6 7 public LinkQueue() { 8 init(); 9 }10 11 public void init() {12 front = rear = null;13 count = 0;14 }15 16 @Override17 public void append(Object obj) throws Exception {18 // TODO Auto-generated method stub19 Node node = new Node(obj, null);20 21 //如果當(dāng)前隊(duì)列不為空。22 if (rear != null) {23 rear.next = node; //隊(duì)尾結(jié)點(diǎn)指向新結(jié)點(diǎn)24 }25 26 rear = node; //設(shè)置隊(duì)尾結(jié)點(diǎn)為新結(jié)點(diǎn)27 28 //說(shuō)明要插入的結(jié)點(diǎn)是隊(duì)列的第一個(gè)結(jié)點(diǎn)29 if (front == null) {30 front = node;31 }32 count++;33 }34 35 @Override36 public Object delete() throws Exception {37 // TODO Auto-generated method stub38 if (isEmpty()) {39 new Exception("隊(duì)列已空！");40 }41 Node node = front;42 front = front.next;43 count--;44 return node.getElement();45 }46 47 @Override48 public Object getFront() throws Exception {49 // TODO Auto-generated method stub50 if (!isEmpty()) {51 return front.getElement();52 } else {53 return null;54 }55 }56 57 @Override58 public boolean isEmpty() {59 // TODO Auto-generated method stub60 return count == 0;61 }62 63 }
(4)Test.java:
1 public class Test { 2 3 public static void main(String[] args) throws Exception { 4 5 LinkQueue queue = new LinkQueue(); 6 queue.append("a"); 7 queue.append("b"); 8 queue.append("c"); 9 queue.append("d");10 queue.append("e");11 queue.append("f");12 13 queue.delete();14 queue.delete();15 16 queue.append("g");17 18 while (!queue.isEmpty()) {19 System.out.println(queue.delete());20 }21 }22 }
運(yùn)行效果：
2、鏈?zhǔn)疥?duì)列的應(yīng)用：
題目：
編寫(xiě)一個(gè)判斷一個(gè)字符串是否是回文的算法。
思路：
設(shè)字符數(shù)組str中存放了要判斷的字符串。把字符數(shù)組中的字符逐個(gè)分別存入一個(gè)隊(duì)列和棧中，然后逐個(gè)出隊(duì)和出棧比較出隊(duì)的字符與出棧的字符是否相同，若全部相等則該字符串為回文。
代碼實(shí)現(xiàn)：
這里面需要用到上面一段中的LinkQueue類(lèi)。代碼結(jié)構(gòu)如下：
(4)Stack.java:棧接口
1 //棧接口 2 public interface Stack { 3 4 //入棧 5 public void push(Object obj) throws Exception; 6 7 //出棧 8 public Object pop() throws Exception; 9 10 //獲得棧頂元素11 public Object getTop() throws Exception;12 13 //判斷棧是否為空14 public boolean isEmpty();15 }
(5)LinkStack.java:
1 public class LinkStack implements Stack { 2 3 Node head; //棧頂指針 4 int size; //結(jié)點(diǎn)的個(gè)數(shù) 5 6 public LinkStack() { 7 head = null; 8 size = 0; 9 }10 11 @Override12 public Object getTop() throws Exception {13 // TODO Auto-generated method stub14 return head.getElement();15 }16 17 @Override18 public boolean isEmpty() {19 // TODO Auto-generated method stub20 return head == null;21 }22 23 @Override24 public Object pop() throws Exception {25 // TODO Auto-generated method stub26 if (isEmpty()) {27 throw new Exception("棧為空！");28 }29 Object obj = head.getElement();30 head = head.getNext();31 size--;32 return obj;33 34 }35 36 @Override37 public void push(Object obj) throws Exception {38 // TODO Auto-generated method stub39 head = new Node(obj, head);40 size++;41 }42 43 }
(6)Test.java:測(cè)試類(lèi)
1 public class Test { 2 3 public static void main(String[] args) throws Exception { 4 5 String str1 = "ABCDCBA"; //是回文 6 String str2 = "ABCDECAB"; //不是回文 7 8 try { 9 if (Test.isHuiWen(str1)) {10 System.out.println(str2 + ":是回文！");11 } else {12 System.out.println(str2 + ":不是回文！");13 }14 } catch (Exception ex) {15 ex.printStackTrace();16 }17 }18 19 20 //方法：判斷字符串是否回文21 public static boolean isHuiWen(String str) throws Exception {22 int n = str.length();23 LinkStack stack = new LinkStack();//創(chuàng)建堆棧24 LinkQueue queue = new LinkQueue();//創(chuàng)建隊(duì)列25 for (int i = 0; i < n; i++) {26 stack.push(str.subSequence(i, i + 1)); //把字符串每個(gè)字符壓進(jìn)堆棧27 queue.append(str.subSequence(i, i + 1));//把字符串每個(gè)字符壓入隊(duì)列28 }29 while (!queue.isEmpty() && !stack.isEmpty()) {30 if (!queue.delete().equals(stack.pop())) { //出隊(duì)列，出棧，同時(shí)判斷是否相同31 return false;32 }33 }34 35 return true;36 }37 38 }
3、循環(huán)隊(duì)列和鏈?zhǔn)疥?duì)列的比較：
（1）從時(shí)間上看，它們的基本操作都是常數(shù)時(shí)間，即O(1)的。不過(guò)循環(huán)隊(duì)列是事先申請(qǐng)好空間，使用期間不釋放；而鏈?zhǔn)疥?duì)列，每次申請(qǐng)和釋放結(jié)點(diǎn)也會(huì)存在一定的時(shí)間開(kāi)銷(xiāo)，如果入棧和出棧比較頻繁，則兩者還是有細(xì)微的差別。
（2）從空間上看，循環(huán)隊(duì)列必須有一個(gè)固定的長(zhǎng)度，所以就有了存儲(chǔ)元素個(gè)數(shù)和空間浪費(fèi)的問(wèn)題。而鏈?zhǔn)疥?duì)列不存在這個(gè)問(wèn)題，盡管它需要一個(gè)指針域，會(huì)產(chǎn)生一些空間上的開(kāi)銷(xiāo)，但也可以接受。所以在空間上，鏈?zhǔn)疥?duì)列更加靈活。
總結(jié)：總的來(lái)說(shuō)，在可以確定隊(duì)列長(zhǎng)度的最大值的情況下，建議用循環(huán)隊(duì)列，如果你無(wú)法估計(jì)隊(duì)列的長(zhǎng)度，那就用鏈?zhǔn)疥?duì)列。
五、優(yōu)先級(jí)隊(duì)列：
優(yōu)先級(jí)隊(duì)列是帶有優(yōu)先級(jí)的隊(duì)列。
用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列稱(chēng)作順序優(yōu)先級(jí)隊(duì)列。
用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的優(yōu)先級(jí)隊(duì)列稱(chēng)作鏈?zhǔn)絻?yōu)先級(jí)隊(duì)列。
順序優(yōu)先級(jí)隊(duì)列和順序循環(huán)隊(duì)列相比主要有兩點(diǎn)不同：
（1）對(duì)于順序優(yōu)先級(jí)隊(duì)列來(lái)說(shuō)，出隊(duì)列操作不是把隊(duì)頭數(shù)據(jù)元素出隊(duì)列，而是把隊(duì)列中優(yōu)先級(jí)最高的數(shù)據(jù)元素出隊(duì)列。（入隊(duì)操作沒(méi)區(qū)別）
（2）對(duì)于順序優(yōu)先級(jí)隊(duì)列來(lái)說(shuō)，數(shù)據(jù)元素由兩部分組成，一部分是原先意義上的數(shù)據(jù)元素，另一部分是優(yōu)先級(jí)。通常設(shè)計(jì)優(yōu)先級(jí)為int類(lèi)型的數(shù)值，并規(guī)定數(shù)值越小優(yōu)先級(jí)越高。
1、順序優(yōu)先隊(duì)列的實(shí)現(xiàn)：
設(shè)計(jì)順序優(yōu)先級(jí)隊(duì)列分為兩個(gè)類(lèi)：
數(shù)據(jù)元素類(lèi)
優(yōu)先級(jí)隊(duì)列類(lèi)
代碼實(shí)現(xiàn)：
(1)Element.java:
1 //優(yōu)先級(jí)隊(duì)列元素類(lèi) 2 public class Element { 3 4 private Object element; // 數(shù)據(jù) 5 private int priority; // 優(yōu)先級(jí) 6 7 public Element(Object obj, int priority) { 8 this.element = obj; 9 this.priority = priority;10 }11 12 public Object getElement() {13 return element;14 }15 16 public void setElement(Object element) {17 this.element = element;18 }19 20 public int getPriority() {21 return priority;22 }23 24 public void setPriority(int priority) {25 this.priority = priority;26 }27 28 }
(2)Queue.java:
1 //隊(duì)列接口 2 public interface Queue { 3 4 //入隊(duì) 5 public void append(Object obj) throws Exception; 6 7 //出隊(duì) 8 public Object delete() throws Exception; 9 10 //獲得隊(duì)頭元素11 public Object getFront() throws Exception;12 13 //判斷對(duì)列是否為空14 public boolean isEmpty();15 }
(3)PrioritySequenceQueue.java:
1 //優(yōu)先級(jí)隊(duì)列 2 public class PrioritySequenceQueue implements Queue { 3 4 static final int defaultSize = 10; //默認(rèn)隊(duì)列長(zhǎng)度 5 int front; //隊(duì)頭 6 int rear; //隊(duì)尾 7 int count; //計(jì)數(shù)器 8 int maxSize; //隊(duì)列最大長(zhǎng)度 9 Element[] queue; //隊(duì)列10 11 public PrioritySequenceQueue() {12 init(defaultSize);13 }14 15 public PrioritySequenceQueue(int size) {16 init(size);17 }18 19 public void init(int size) {20 maxSize = size;21 front = rear = 0;22 count = 0;23 queue = new Element[size];24 }25 26 @Override27 public void append(Object obj) throws Exception {28 // TODO Auto-generated method stub29 //如果隊(duì)列已滿30 if (count >= maxSize) {31 throw new Exception("隊(duì)列已滿！");32 }33 queue[rear] = (Element) obj;34 rear++;35 count++;36 }37 38 @Override39 public Object delete() throws Exception {40 // TODO Auto-generated method stub41 if (isEmpty()) {42 throw new Exception("隊(duì)列為空！");43 }44 //默認(rèn)第一個(gè)元素為優(yōu)先級(jí)最高的。45 Element min = queue[0];46 int minIndex = 0;47 for (int i = 0; i < count; i++) {48 if (queue[i].getPriority() < min.getPriority()) {49 min = queue[i];50 minIndex = i;51 }52 }53 54 //找的優(yōu)先級(jí)別最高的元素后，把該元素后面的元素向前移動(dòng)。55 for (int i = minIndex + 1; i < count; i++) {56 queue[i - 1] = queue[i]; //移動(dòng)元素57 }58 rear--;59 count--;60 return min;61 }62 63 @Override64 public Object getFront() throws Exception {65 // TODO Auto-generated method stub66 if (isEmpty()) {67 throw new Exception("隊(duì)列為空！");68 }69 //默認(rèn)第一個(gè)元素為優(yōu)先級(jí)最高的。70 Element min = queue[0];71 int minIndex = 0;72 for (int i = 0; i < count; i++) {73 if (queue[i].getPriority() < min.getPriority()) {74 min = queue[i];75 minIndex = i;76 }77 }78 return min;79 }80 81 @Override82 public boolean isEmpty() {83 // TODO Auto-generated method stub84 return count == 0;85 }86 87 }
2、代碼測(cè)試：
設(shè)計(jì)一個(gè)程序模仿操作系統(tǒng)的進(jìn)程管理問(wèn)題。進(jìn)程服務(wù)按優(yōu)先級(jí)高的先服務(wù)，優(yōu)先級(jí)相同的先到先服務(wù)的原則管理。
模仿數(shù)據(jù)包含兩個(gè)部分：進(jìn)程編號(hào)和優(yōu)先級(jí)。如下有五個(gè)進(jìn)程：
1 30
2 20
3 40
4 20
5 0 ----------優(yōu)先級(jí)最高，先服務(wù)
(4)Test.java:
1 public class Test { 2 3 public static void main(String[] args) throws Exception { 4 5 PrioritySequenceQueue queue = new PrioritySequenceQueue(); 6 Element temp; 7 8 //五個(gè)進(jìn)程入隊(duì) 9 queue.append(new Element(1, 30));10 queue.append(new Element(2, 20));11 queue.append(new Element(3, 40));12 queue.append(new Element(4, 20));13 queue.append(new Element(5, 0));14 15 //按照優(yōu)先級(jí)出隊(duì)。16 System.out.println("編號(hào) 優(yōu)先級(jí)");17 while (!queue.isEmpty()) {18 temp = (Element) queue.delete();19 System.out.println(temp.getElement() + " " + temp.getPriority());20 }21 }22 }
運(yùn)行效果：
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
