java數(shù)據(jù)結(jié)構(gòu)與算法之（Queue）隊(duì)列設(shè)計(jì)與實(shí)現(xiàn)

java數(shù)據(jù)結(jié)構(gòu)與算法之（Queue）隊(duì)列設(shè)計(jì)與實(shí)現(xiàn)隊(duì)列的抽象數(shù)據(jù)類型??隊(duì)列同樣是一種特殊的線性表，其插入和刪除的操作分別在表的兩端進(jìn)行，隊(duì)列的特點(diǎn)就是先進(jìn)先出(FirstInFirstOut)。我們把向隊(duì)列中插入元素的過程稱為入隊(duì)(Enqueue)，刪除元素的過程稱為出隊(duì)(Dequeue)并把允許入隊(duì)的一端稱為隊(duì)尾，允許出的的一端稱為隊(duì)頭，沒有任何元素的隊(duì)列則稱為空隊(duì)。其一般結(jié)構(gòu)如下：關(guān)于隊(duì)列的操作，我們這里主要實(shí)現(xiàn)入隊(duì)，出隊(duì)，判斷空隊(duì)列和清空隊(duì)列等操作，聲明隊(duì)列接口Queue（隊(duì)列抽象數(shù)據(jù)類型）如下：packagecom.zejian.structures.Queue;/***Createdbyzejianon2016/11/28.*Blog:/javazejian/article/details/53375004[原文地址,請(qǐng)尊重原創(chuàng)]*隊(duì)列抽象數(shù)據(jù)類型*/publicinterfaceQueue<T>{/***返回隊(duì)列長(zhǎng)度*@return*/intsize();/***判斷隊(duì)列是否為空*@return*/booleanisEmpty();/***data入隊(duì),添加成功返回true,否則返回false,可擴(kuò)容*@paramdata*@return*/booleanadd(Tdata);/***offer方法可插入一個(gè)元素,這與add方法不同，*該方法只能通過拋出未經(jīng)檢查的異常使添加元素失敗。*而不是出現(xiàn)異常的情況，例如在容量固定（有界）的隊(duì)列中*NullPointerException:data==null時(shí)拋出*@paramdata*@return*/booleanoffer(Tdata);/***返回隊(duì)頭元素,不執(zhí)行刪除操作,若隊(duì)列為空,返回null*@return*/Tpeek();/***返回隊(duì)頭元素,不執(zhí)行刪除操作,若隊(duì)列為空,拋出異常:NoSuchElementException*@return*/Telement();/***出隊(duì),執(zhí)行刪除操作,返回隊(duì)頭元素,若隊(duì)列為空,返回null*@return*/Tpoll();/***出隊(duì),執(zhí)行刪除操作,若隊(duì)列為空,拋出異常:NoSuchElementException*@return*/Tremove();/***清空隊(duì)列*/voidclearQueue();}下面我們就來分別實(shí)現(xiàn)順序隊(duì)列和鏈?zhǔn)疥?duì)列順序隊(duì)列的設(shè)計(jì)與實(shí)現(xiàn)??關(guān)于順序隊(duì)列（底層都是利用數(shù)組作為容器）的實(shí)現(xiàn)，我們將采用順序循環(huán)隊(duì)列的結(jié)構(gòu)來實(shí)現(xiàn)，在給出實(shí)現(xiàn)方案前先來分析一下為什么不直接使用順序表作為底層容器來實(shí)現(xiàn)。實(shí)際上采用順序表實(shí)現(xiàn)隊(duì)列時(shí)，入隊(duì)操作直接執(zhí)行順序表尾部插入操作，其時(shí)間復(fù)雜度為O(1)，出隊(duì)操作直接執(zhí)行順序表頭部刪除操作，其時(shí)間復(fù)雜度為O(n)，主要用于移動(dòng)元素，效率低，既然如此，我們就把出隊(duì)的時(shí)間復(fù)雜度降為O(1)即可，為此在順序表中添加一個(gè)頭指向下標(biāo)front和尾指向下標(biāo)，出隊(duì)和入隊(duì)時(shí)只要改變front、rear的下標(biāo)指向取值即可，此時(shí)無需移動(dòng)元素，因此出隊(duì)的時(shí)間復(fù)雜度也就變?yōu)镺(1)。其過程如下圖所示從圖的演示過程，（a）操作時(shí)，是空隊(duì)列此時(shí)front和rear都為-1，同時(shí)可以發(fā)現(xiàn)雖然我們通過給順序表添加front和rear變量記錄下標(biāo)后使用得出隊(duì)操作的時(shí)間復(fù)雜度降為O(1)，但是卻出現(xiàn)了另外一個(gè)嚴(yán)重的問題，那就是空間浪費(fèi)，從圖中的（d）和（e）操作可以發(fā)現(xiàn)，20和30出隊(duì)后，遺留下來的空間并沒有被重新利用，反而是空著，所以導(dǎo)致執(zhí)行（f）操作時(shí)，出現(xiàn)隊(duì)列已滿的假現(xiàn)象，這種假現(xiàn)象我們稱之為假溢出，之所以出現(xiàn)這樣假溢出的現(xiàn)象是因?yàn)轫樞虮黻?duì)列的存儲(chǔ)單元沒有重復(fù)利用機(jī)制，而解決該問題的最合適的方式就是將順序隊(duì)列設(shè)計(jì)為循環(huán)結(jié)構(gòu)，接下來我們就通過循環(huán)順序表來實(shí)現(xiàn)順序隊(duì)列。??順序循環(huán)隊(duì)列就是將順序隊(duì)列設(shè)計(jì)為在邏輯結(jié)構(gòu)上收尾相接的循環(huán)結(jié)構(gòu)，這樣我們就可以重復(fù)利用存儲(chǔ)單元，其過程如下所示：簡(jiǎn)單分析一下：其中采用循環(huán)結(jié)構(gòu)的順序表，可以循環(huán)利用存儲(chǔ)單元，因此有如下計(jì)算關(guān)系(其中size為隊(duì)列長(zhǎng)度)：//其中front、rear的下標(biāo)的取值范圍是0~size-1，不會(huì)造成假溢出。front=(front+1)%size;//隊(duì)頭下標(biāo)rear=(rear+1)%size;front為隊(duì)頭元素的下標(biāo)，rear則指向下一個(gè)入隊(duì)元素的下標(biāo)當(dāng)front=rear時(shí)，我們約定隊(duì)列為空。出隊(duì)操作改變front下標(biāo)指向，入隊(duì)操作改變r(jià)ear下標(biāo)指向，size代表隊(duì)列容量。約定隊(duì)列滿的條件為front=(rear+1)%size,注意此時(shí)隊(duì)列中仍有一個(gè)空的位置，此處留一個(gè)空位主要用于避免與隊(duì)列空的條件front=rear相同。隊(duì)列內(nèi)部的數(shù)組可擴(kuò)容，并按照原來隊(duì)列的次序復(fù)制元素?cái)?shù)組了解了隊(duì)列的實(shí)現(xiàn)規(guī)則后，我們重點(diǎn)分析一下入隊(duì)add方法和出隊(duì)poll方法，其中入隊(duì)add方法實(shí)現(xiàn)如下：/***data入隊(duì),添加成功返回true,否則返回false,可擴(kuò)容*@paramdata*@return*/@Overridepublicbooleanadd(Tdata){//判斷是否滿隊(duì)if(this.front==(this.rear+1)%this.elementData.length){ensureCapacity(elementData.length*2+1);}//添加dataelementData[this.rear]=data;//更新rear指向下一個(gè)空元素的位置this.rear=(this.rear+1)%elementData.length;size++;returntrue;}在add方法中我們先通過this.front==(this.rear+1)%this.elementData.length判斷隊(duì)列是否滿，在前面我們約定過隊(duì)列滿的條件為front=(rear+1)%size,如果隊(duì)列滿，則先通過ensureCapacity(elementData.length*2+1)擴(kuò)容，該方法實(shí)現(xiàn)如下：/***擴(kuò)容的方法*@paramcapacity*/publicvoidensureCapacity(intcapacity){//如果需要拓展的容量比現(xiàn)在數(shù)組的容量還小,則無需擴(kuò)容if(capacity<size)return;T[]old=elementData;elementData=(T[])newObject[capacity];intj=0;//復(fù)制元素for(inti=this.front;i!=this.rear;i=(i+1)%old.length){elementData[j++]=old[i];}//恢復(fù)front,rear指向this.front=0;this.rear=j;}這個(gè)方法比較簡(jiǎn)單，主要?jiǎng)?chuàng)建一個(gè)新容量的數(shù)組，并把舊數(shù)組中的元素復(fù)制到新的數(shù)組中，這里唯一的要注意的是，判斷久數(shù)組是否復(fù)制完成的條件為i!=this.rear，同時(shí)循環(huán)的自增條件為i=(i+1)%old.length。擴(kuò)容后直接通過rear添加新元素，最后更新rear指向下一個(gè)入隊(duì)新元素。對(duì)于出隊(duì)操作poll的實(shí)現(xiàn)如下：/***出隊(duì),執(zhí)行刪除操作,返回隊(duì)頭元素,若隊(duì)列為空,返回null*@return*/@OverridepublicTpoll(){Ttemp=this.elementData[this.front];this.front=(this.front+1)%this.elementData.length;size--;returntemp;}出隊(duì)操作相對(duì)簡(jiǎn)單些，直接存儲(chǔ)要?jiǎng)h除元素的數(shù)據(jù)，并更新隊(duì)頭front的值，最后返回刪除元素的數(shù)據(jù)。ok~，關(guān)于循環(huán)結(jié)構(gòu)的順序隊(duì)列，我們就分析到此，最后給出循環(huán)順序隊(duì)列的實(shí)現(xiàn)源碼，其他方法比較簡(jiǎn)單，注釋也很清楚，就不過多分析了：packagecom.zejian.structures.Queue;importjava.io.Serializable;importjava.util.NoSuchElementException;/***Createdbyzejianon2016/11/28.*Blog:/javazejian[原文地址,請(qǐng)尊重原創(chuàng)]*順序隊(duì)列的實(shí)現(xiàn)*/publicclassSeqQueue<T>implementsQueue<T>,Serializable{privatestaticfinallongserialVersionUID=-1664818681270068094L;privatestaticfinalintDEFAULT_SIZE=10;privateTelementData[];privateintfront,rear;privateintsize;publicSeqQueue(){elementData=(T[])newObject[DEFAULT_SIZE];front=rear=0;}publicSeqQueue(intcapacity){elementData=(T[])newObject[capacity];front=rear=0;}@Overridepublicintsize(){//LinkedListreturnsize;}@OverridepublicbooleanisEmpty(){returnfront==rear;}/***data入隊(duì),添加成功返回true,否則返回false,可擴(kuò)容*@paramdata*@return*/@Overridepublicbooleanadd(Tdata){//判斷是否滿隊(duì)if(this.front==(this.rear+1)%this.elementData.length){ensureCapacity(elementData.length*2+1);}//添加dataelementData[this.rear]=data;//更新rear指向下一個(gè)空元素的位置this.rear=(this.rear+1)%elementData.length;size++;returntrue;}/***offer方法可插入一個(gè)元素,這與add方法不同，*該方法只能通過拋出未經(jīng)檢查的異常使添加元素失敗。*而不是出現(xiàn)異常的情況，例如在容量固定（有界）的隊(duì)列中*NullPointerException:data==null時(shí)拋出*IllegalArgumentException:隊(duì)滿,使用該方法可以使Queue的容量固定*@paramdata*@return*/@Overridepublicbooleanoffer(Tdata){if(data==null)thrownewNullPointerException("Thedatacan\'tbenull");//隊(duì)滿拋出異常if(this.front==(this.rear+1)%this.elementData.length){thrownewIllegalArgumentException("ThecapacityofSeqQueuehasreacheditsmaximum");}//添加dataelementData[this.rear]=data;//更新rear指向下一個(gè)空元素的位置this.rear=(this.rear+1)%elementData.length;size++;returntrue;}/***返回隊(duì)頭元素,不執(zhí)行刪除操作,若隊(duì)列為空,返回null*@return*/@OverridepublicTpeek(){returnelementData[front];}/***返回隊(duì)頭元素,不執(zhí)行刪除操作,若隊(duì)列為空,拋出異常:NoSuchElementException*@return*/@OverridepublicTelement(){if(isEmpty()){thrownewNoSuchElementException("TheSeqQueueisempty");}returnpeek();}/***出隊(duì),執(zhí)行刪除操作,返回隊(duì)頭元素,若隊(duì)列為空,返回null*@return*/@OverridepublicTpoll(){Ttemp=this.elementData[this.front];this.front=(this.front+1)%this.elementData.length;size--;returntemp;}/***出隊(duì),執(zhí)行刪除操作,若隊(duì)列為空,拋出異常:NoSuchElementException*@return*/@OverridepublicTremove(){if(isEmpty()){thrownewNoSuchElementException("TheSeqQueueisempty");}returnpoll();}@OverridepublicvoidclearQueue(){for(inti=this.front;i!=this.rear;i=(i+1)%elementData.length){elementData[i]=null;}//復(fù)位this.front=this.rear=0;size=0;}/***擴(kuò)容的方法*@paramcapacity*/publicvoidensureCapacity(intcapacity){//如果需要拓展的容量比現(xiàn)在數(shù)組的容量還小,則無需擴(kuò)容if(capacity<size)return;T[]old=elementData;elementData=(T[])newObject[capacity];intj=0;//復(fù)制元素for(inti=this.front;i!=this.rear;i=(i+1)%old.length){elementData[j++]=old[i];}//恢復(fù)front,rear指向this.front=0;this.rear=j;}}鏈?zhǔn)疥?duì)列的設(shè)計(jì)與實(shí)現(xiàn)??分析完順序隊(duì)列，我們接著看看鏈?zhǔn)疥?duì)列的設(shè)計(jì)與實(shí)現(xiàn)，對(duì)于鏈?zhǔn)疥?duì)列，將使用帶頭指針front和尾指針rear的單鏈表實(shí)現(xiàn)，front直接指向隊(duì)頭的第一個(gè)元素，rear指向隊(duì)尾的最后一個(gè)元素，其結(jié)構(gòu)如下：之所以選擇單鏈表（帶頭尾指針）而不采用循環(huán)雙鏈表或者雙鏈表主要是雙鏈表的空間開銷（空間復(fù)雜度，多前繼指針）相對(duì)單鏈表來說大了不少，而單鏈表只要新增頭指針和尾指針就可以輕松實(shí)現(xiàn)常數(shù)時(shí)間內(nèi)（時(shí)間復(fù)雜度為O(1)）訪問頭尾結(jié)點(diǎn)。下面我們來看看如何設(shè)計(jì)鏈?zhǔn)疥?duì)列：以上述的圖為例分別設(shè)置front和rear指向隊(duì)頭結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)，使用單鏈表的頭尾訪問時(shí)間復(fù)雜度為O(1)。設(shè)置初始化空隊(duì)列，使用front=rear=null，并且約定條件front==null&&rear==null成立時(shí)，隊(duì)列為空。出隊(duì)操作時(shí)，若隊(duì)列不為空獲取隊(duì)頭結(jié)點(diǎn)元素，并刪除隊(duì)頭結(jié)點(diǎn)元素，更新front指針的指向?yàn)閒ront=front.next入隊(duì)操作時(shí)，使插入元素的結(jié)點(diǎn)在rear之后并更新rear指針指向新插入元素。當(dāng)?shù)谝粋€(gè)元素入隊(duì)或者最后一個(gè)元素出隊(duì)時(shí)，同時(shí)更新front指針和rear指針的指向。這一系列過程如下圖所示：ok~，關(guān)于鏈?zhǔn)疥?duì)列的設(shè)計(jì)都分析完，至于實(shí)現(xiàn)就比較簡(jiǎn)單了，和之前分析過的單鏈表區(qū)別不大，因此這里我們直接給出實(shí)現(xiàn)代碼即可：packagecom.zejian.structures.Queue;importcom.zejian.structures.LinkedList.singleLinked.Node;importjava.io.Serializable;importjava.util.*;/***Createdbyzejianon2016/11/28.*Blog:/javazejian/article/details/53375004[原文地址,請(qǐng)尊重原創(chuàng)]*鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)*/publicclassLinkedQueue<T>implementsQueue<T>,Serializable{privatestaticfinallongserialVersionUID=1406881264853111039L;/***指向隊(duì)頭和隊(duì)尾的結(jié)點(diǎn)*front==null&&rear==null時(shí),隊(duì)列為空*/privateNode<T>front,rear;privateintsize;/***用于控制最大容量,默認(rèn)128,offer方法使用*/privateintmaxSize=128;publicLinkedQueue(){//初始化隊(duì)列this.front=this.rear=null;}@Overridepublicintsize(){returnsize;}publicvoidsetMaxSize(intmaxSize){this.maxSize=maxSize;}@OverridepublicbooleanisEmpty(){returnfront==null&&rear==null;}/***data入隊(duì),添加成功返回true,否則返回false,可擴(kuò)容*@paramdata*@return*/@Overridepublicbooleanadd(Tdata){Node<T>q=newNode<>(data,null);if(this.front==null){//空隊(duì)列插入this.front=q;}else{//非空隊(duì)列,尾部插入this.rear.next=q;}this.rear=q;size++;returntrue;}/***offer方法可插入一個(gè)元素,這與add方法不同，*該方法只能通過拋出未經(jīng)檢查的異常使添加元素失敗。*而不是出現(xiàn)異常的情況，例如在容量固定（有界）的隊(duì)列中*NullPointerException:data==null時(shí)拋出*IllegalArgumentException:隊(duì)滿,使用該方法可以使Queue的容量固定*@paramdata*@return*/@Overridepublicbooleanoffer(Tdata){if(data==null)thrownewNullPointerException("Thedatacan\'tbenull");if(size>=maxSize)thrownewIllegalArgumentException("ThecapacityofLinkedQueuehasreacheditsmaxSize:128");Node<T>q=newNode<>(data,null);if(this.front==null){//空隊(duì)列插入this.front=q;}else{//非空隊(duì)列,尾部插入this.rear.next=q;}this.rear=q;size++;returnfalse;}/***返回隊(duì)頭元素,不執(zhí)行刪除操作,若隊(duì)列為空,返回null*@return*/@OverridepublicTpeek(){returnthis.isEmpty()?null:this.front.data;}/***返回隊(duì)頭元素,不執(zhí)行刪除操作,若隊(duì)列為空,拋出異常:NoSuchElementException*@return*/@OverridepublicTelement(){if(isEmpty()){thrownewNoSuchElementException("TheLinkedQueueisempty");}returnthis.front.data;}/***出隊(duì),執(zhí)行刪除操作,返回隊(duì)頭元素,若隊(duì)列為空,返回null*@return*/@OverridepublicTpoll(){if(this.isEmpty())returnnull;Tx=this.front.data;this.front=this.front.next;if(this.front==null)this.rear=null;size--;returnx;}/***出隊(duì),執(zhí)行刪除操作,若隊(duì)列為空,拋出異常:NoSuchElementException*@return*/@OverridepublicTremove(){if(isEmpty()){thrownewNoSuchElementException("TheLinkedQueueisempty");}Tx=this.front.data;this.front=this.front.next;if(this.front==null)this.rear=null;size--;returnx;}@OverridepublicvoidclearQueue(){this.front=this.rear=null;size=0;}}隊(duì)列應(yīng)用的簡(jiǎn)單舉例模擬現(xiàn)實(shí)世界中的隊(duì)列，如售票柜臺(tái)的隊(duì)列以及其他先到先服務(wù)的場(chǎng)景。計(jì)算客戶在呼叫中心等待的時(shí)間。異步數(shù)據(jù)的傳輸（文件輸入輸出、管道、嵌套字）。操作系統(tǒng)中的優(yōu)先級(jí)任務(wù)執(zhí)行。短信群體發(fā)送應(yīng)用的發(fā)布訂閱模式優(yōu)先隊(duì)列的設(shè)置與實(shí)現(xiàn)（雙鏈表實(shí)現(xiàn)）??了解完循環(huán)順序隊(duì)列和鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)后，我們最后再來了解一個(gè)特殊的隊(duì)列，也就是優(yōu)先隊(duì)列，在某些情況下，有些應(yīng)用系統(tǒng)要求不僅需要按照“先來先服務(wù)”的原則進(jìn)行，而且還需按照任務(wù)的重要或緊急程度進(jìn)行排隊(duì)處理，此時(shí)就需要使用到優(yōu)先隊(duì)列。比如在操作系統(tǒng)中進(jìn)行進(jìn)程調(diào)度管理，每個(gè)進(jìn)程都具備一個(gè)優(yōu)先級(jí)值以表示進(jìn)程的緊急程度，優(yōu)先級(jí)高的進(jìn)行先執(zhí)行，同等級(jí)進(jìn)程按照先進(jìn)先出的原則排隊(duì)處理，此時(shí)操作系統(tǒng)使用的便是優(yōu)先隊(duì)列管理和調(diào)度進(jìn)程。??優(yōu)先級(jí)隊(duì)列也是一種特殊的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列中的每個(gè)元素都有一個(gè)優(yōu)先級(jí)，若每次出隊(duì)的是具有最高優(yōu)先級(jí)的元素，則稱為降序優(yōu)先級(jí)隊(duì)列(總是先刪除最大的元素)。若每次出隊(duì)的是值最小的元素，則稱為升序優(yōu)先級(jí)隊(duì)列(總是先刪除最小的元素)，通常情況下我們所說的優(yōu)先隊(duì)列，一般是指降序優(yōu)先級(jí)隊(duì)列。關(guān)于優(yōu)先隊(duì)列的實(shí)現(xiàn)，可以使用有序數(shù)組或者有序鏈表，也可以使用二叉樹（二叉堆）實(shí)現(xiàn)，這里我們僅給出有序鏈表的簡(jiǎn)單實(shí)現(xiàn)方案。而二叉樹的實(shí)現(xiàn)，留著后面我們分析完樹時(shí)再給出。好~，這里使用之前分析過的MyLikedList作為基底，實(shí)現(xiàn)一個(gè)排序的SortLinkedList繼承自MyLinkedList，這里需要注意的是排序鏈表中的T類型必須是實(shí)現(xiàn)了Comparable接口的類型，在SortLinkedList中主要重寫添加的add方法，插入邏輯是，通過比較元素的大小加入，而非簡(jiǎn)單下標(biāo)或尾部插入，其實(shí)現(xiàn)如下：packagecom.zejian.structures.LinkedList.MyCollection;importjava.io.Serializable;importjava.util.Iterator;importjava.util.ListIterator;/***Createdbyzejianon2016/12/3.*Blog:/javazejian[原文地址,請(qǐng)尊重原創(chuàng)]*排序list的簡(jiǎn)單實(shí)現(xiàn)*/publicclassSortMyLinkedList<TextendsComparable<?extendsT>>extendsMylinkeList<T>implementsSerializable{privatestaticfinallongserialVersionUID=-4783131709270334156L;@Overridepublicbooleanadd(Tdata){if(data==null)thrownewNullPointerException("datacan\'tbenull");Comparablecmp=data;//這里需要轉(zhuǎn)一下類型,否則idea編輯器上檢驗(yàn)不通過.if(this.isEmpty()||pareTo(this.last.prev.data)>0){returnsuper.add(data);//直接尾部添加,last不帶數(shù)據(jù)的尾結(jié)點(diǎn)}Node<T>p=this.first.next;//查找插入點(diǎn)while(p!=null&&pareTo(p.data)>0)p=p.next;Node<T>q=newNode<>(p.prev,data,p);p.prev.next=q;p.prev=q;size++;//記錄修改modCount++;returntrue;}/***不根據(jù)下標(biāo)插入,只根據(jù)比較大小插入*@paramindex*@paramdata*/@Overridepublicvoidadd(intindex,Tdata){this.add(data);}/***未實(shí)現(xiàn)*@paramindex*@return*/@OverridepublicListIterator<T>listIterator(intindex){returnnull;}/***未實(shí)現(xiàn)*@return*/@OverridepublicIterator<T>iterator(){returnnull;}//測(cè)試publicstaticvoidmain(String[]args){SortMyLinkedList<Integer>list=newSortMyLinkedList<>();list.add(50);list.add(40);list.add(80);list.add(20);print(list);}publicstaticvoidprint(SortMyLinkedListmylinkeList){for(inti=0;i<mylinkeList.size();i++){System.out.println("i->"+mylinkeList.get(i));}}}接著以SortMyLinkedList為基底實(shí)現(xiàn)優(yōu)先隊(duì)列PriorityQueue，實(shí)現(xiàn)源碼如下，實(shí)現(xiàn)比較簡(jiǎn)單，感覺沒啥好說的：packagecom.zejian.structures.Queue;importcom.zejian.structures.LinkedList.MyCollection.SortMyLinkedList;importjava.io.Serializable;importjava.util.NoSuchElementException;/***Createdbyzejianon2016/11/30.*Blog:/javazejian[原文地址,請(qǐng)尊重原創(chuàng)]*優(yōu)先隊(duì)列的簡(jiǎn)單實(shí)現(xiàn),采用排序雙鏈表,T必須實(shí)現(xiàn)Comparable接口*/publicclassPriorityQueue<TextendsComparable<?extendsT>>implementsQueue<T>,Serializable{privatestaticfinallongserialVersionUID=8050142086009260625L;privateSortMyLinkedList<T>list;//排序循環(huán)雙鏈表privatebooleanasc;//true表示升序,false表示降序/***用于控制最大容量,默認(rèn)128,offer方法使用*/privateintmaxSize=128;/***初始化隊(duì)列*@paramasc*/publicPriorityQueue(booleanasc){this.list=newSortMyLinkedList<>();this.asc=asc;//默認(rèn)升序}publicintgetMaxSize(){returnmaxSize;}publicvoidsetMaxSize(intmaxSize){this.maxSize=maxSize;}@Overridepublicintsize(){returnlist.size();}@OverridepublicbooleanisEmpty(){returnlist.isEmpty();}/***data入隊(duì),添加成功返回true,否則返回false*@paramdata*@return*/@Overridepublicbooleanadd(Tdata){returnlist.add(data);}/***offer方法可插入一個(gè)元素,這與add方法不同，*該方法只能通過拋出未經(jīng)檢查的異常使添加元素失敗。*而不是出現(xiàn)異常的情況，例如在容量固定（有界）的隊(duì)列中*NullPointerException:data==null時(shí)拋出*IllegalArgumentException:隊(duì)滿,使用該方法可以使Queue的容量固定*@paramdata*@return*/@Overridepublicbooleanoffer(Tdata){if(data==null)thrownewNullPointerException("Thedatacan\'tbenull");if(list.size()>=maxSize)thrownewIllegalArgumentException("The