Java基礎(chǔ)復(fù)習(xí)筆記06數(shù)據(jù)結(jié)構(gòu)隊(duì)列

1、Java基礎(chǔ)復(fù)習(xí)筆記06數(shù)據(jù)結(jié)構(gòu)-隊(duì)列劉巖Email:suhuanzheng77848771.隊(duì)列隊(duì)列又是一種比較特殊的線性表，和棧一樣在線性表的基礎(chǔ)上進(jìn)行了一些限制操作。就是隊(duì)列了。顧名思義，隊(duì)列就是咱們排隊(duì)買(mǎi)火車(chē)票一樣，排在最前面的先買(mǎi)到，排到后隊(duì)列的操作一般包括：進(jìn)隊(duì)列、出隊(duì)列，訪問(wèn)隊(duì)列頭元素、刪除隊(duì)列頭元素、判斷隊(duì)列是否為空、獲得隊(duì)列大小這些核心操作。Sun為Java的隊(duì)列規(guī)定了一個(gè)規(guī)范、反映出來(lái)的的就是java.util.Queue,實(shí)現(xiàn)了此接口的所有方法，相當(dāng)于"你按照Sun的Java規(guī)范為自己寫(xiě)了一個(gè)符合規(guī)范的隊(duì)列實(shí)現(xiàn)類(lèi)”。3 .隊(duì)列的使用場(chǎng)景隊(duì)列的使用場(chǎng)景其實(shí)個(gè)人感覺(jué)

2、比棧要廣泛一些，比如開(kāi)發(fā)網(wǎng)絡(luò)服務(wù)中間件，處理并發(fā)消息的時(shí)候就需要將這些消息組成隊(duì)列的方式一個(gè)一個(gè)處理，再比如對(duì)象池的應(yīng)用，底層完全可以做成一個(gè)對(duì)象隊(duì)列，將一個(gè)用完的對(duì)象放回池中后，就是放到等待隊(duì)列中，先歸還的對(duì)象，下次再使用的時(shí)候就比后放入的對(duì)象優(yōu)先調(diào)用，因?yàn)橄葰w還的對(duì)象肯定是休息了很久了，該對(duì)象應(yīng)當(dāng)回收的資源也都回收了。4 .隊(duì)列的順序?qū)崿F(xiàn)和棧結(jié)構(gòu)一樣隊(duì)列也有兩種實(shí)現(xiàn)方式，先來(lái)看順序的實(shí)現(xiàn)方式，順序?qū)崿F(xiàn)方式就是利用數(shù)組，記錄當(dāng)前隊(duì)列頭標(biāo)記nowTopIndex以及下一個(gè)、新的隊(duì)列結(jié)尾元素的標(biāo)記newTaillndex。程序如下：packagedateStructer.queue;/*順序隊(duì)列

3、authorliuyanparam<E>*/publicclassMyArrayQueue<E>implementsQueue<E>/默認(rèn)大小privatefinalstaticintDefSize=32;/臨時(shí)數(shù)組privateObjectobjects;/當(dāng)前隊(duì)列頭元素索引privateintnowTopIndex;/下一個(gè)隊(duì)列新元素的索引privateintnewTailIndex;publicMyArrayQueue()objects=newObjectDefSize;/* 添加元素* /Overridepublicbooleanadd(Ee)int

4、elementSize=newTailIndex-nowTopIndexif(elementSize=0&&newTailIndex=0)objects0=e;nowTopIndex=0;newTailIndex=1;returntrue;objectsnewTailIndex+=e;returntrue;/* 獲取隊(duì)頭元素* /OverridepublicEelement()return(E)objectsnowTopIndex;/* 返回頭元素，不刪除頭元素* /OverridepublicEpeek()return(E)objectsnowTopIndex;/* 返回頭元

5、素，刪除頭元素* /OverridepublicE poll() if ( objects nowTopIndex = null ) return null ;E date = (E) objects nowTopIndex ; objects nowTopIndex + = null ;return date;Overridepublic E remove() if ( nowTopIndex = 0) return null ;E date = (E) objects nowTopIndex ; objects nowTopIndex - = null ; return date;Over

6、ride public void clear() Arrays. f川 (objects nowTopIndex = 0; newTailIndex = 0;null );Overridepublic boolean contains(Object object) for ( int i = 0; i <objects . lengthif (object = objects i) return true ;i+) returnfalse;OverridepublicbooleanisEmpty()intelementSize=newTaillndex-nowTopIndex;retur

7、nelementSize=0;Overridepublicintsize()returnnewTailIndex-nowTopIndex;OverridepublicStringtoString()StringBufferstr=newStringBuffer("");intelementSize=newTailIndex-nowTopIndex;for(inti=nowTopIndex;i<newTailIndex;i+)str.append(""+objectsi.toString()+",");if(elementSize

8、>0)returnstr.substring(0,str.lastIndexOf(",")+""returnstr.append("").toString();測(cè)試代碼如下publicstaticvoidmain(String口args)MyArrayQueue<String>myQueue=newMyArrayQueue<String>();myQueue.add("1");myQueue.add("2");myQueue.add("3");S

9、ystem.out.println(myQueue.toString();Stringe=myQueue.poll();System.out.println(e);System.out.println(myQueue.toString();myQueue.add("4");e=myQueue.peek();System.out.println("是否為空隊(duì)列"+myQueue.isEmpty();System.out.println("隊(duì)列大小"+myQueue.size();System.out.println(e);System.

10、out.println(myQueue.toString();System.out.println("是否包含相關(guān)元素"+myQueue.contains("1");System.out.println("是否包含相關(guān)元素"+myQueue.contains("2");myQueue.clear();System.out.println("是否為空隊(duì)列"+myQueue.isEmpty();運(yùn)行后效果如下1,2,312,3是否為空隊(duì)列false隊(duì)列大小322,3,4是否包含相關(guān)元素false是否

11、包含相關(guān)元素true是否為空隊(duì)列true5.隊(duì)列的鏈表實(shí)現(xiàn)相對(duì)于順序?qū)崿F(xiàn)方式，鏈?zhǔn)綄?shí)現(xiàn)相對(duì)比較簡(jiǎn)單，只需要利用Node結(jié)構(gòu)，記錄下隊(duì)列的/*頭Node和尾巴Node,在記錄下元素個(gè)數(shù)就可以了。算法如下packagedateStructer.queue;實(shí)現(xiàn)自己的隊(duì)列authorliuyanparam<E>*/publicclassMyQueue<E>implementsQueue<E>/*雙向鏈表結(jié)構(gòu)*/publicclassLinkNode/真正的數(shù)據(jù)域privateEdate;/記錄上一個(gè)節(jié)點(diǎn)privateLinkNodeprevLinkNode;/記錄

12、下一個(gè)節(jié)點(diǎn)privateLinkNodenextLinkNode;publicLinkNode()publicLinkNode(Edate,LinkNodeprevLinkNode,LinkNodenextLinkNode)this.date=date;this.prevLinkNode=prevLinkNode;this.nextLinkNode=nextLinkNode;/結(jié)點(diǎn)個(gè)數(shù)private int nodeSize ;/頭結(jié)點(diǎn)privateLinkNodeheadNode/尾巴節(jié)點(diǎn)privateLinkNodetailNodepublic MyQueue()null ;null ;h

13、eadNode = tailNode =/* 添加元素*/Overridepublic booleanif ( nodeSize headNode else add(Eelement)=0)=newLinkNode(element,null,tailNode);if(tailNode=null)tailNode=newLinkNode(element,headNode,null);headNode.nextLinkNode=tailNode;nodeSize+;returntruenull );LinkNodelinkNode=tailNode;tailNode=newLinkNode(ele

14、ment,linkNode,linkNode.nextLinkNode=tailNode;nodeSize+;returntrue/*訪問(wèn)隊(duì)列頭元素*/OverridepublicEelement。returnheadNode.date/*返回頭元素，不刪除頭元素*/OverridepublicEpeek()returnheadNode.date/*返回頭元素，刪除頭元素*/OverridepublicEpoll()LinkNodeheadNodeTemp=headNode;Edate=headNodeTemp.date;if(headNode.nextLinkNode=null)headNo

15、de.date=null;headNode=null;nodeSize-;returndate;elseheadNode=headNode.nextLinkNodeif(headNode=tailNode)tailNode=null;nodeSize-;returnheadNodeTemp.date;/* 清除所有元素* /Overridepublicvoidclear()LinkNodelinkNodeNowTemp=headNodefor(inti=0;i<nodeSize;i+)if(linkNodeNowTemp!=tailNode&&linkNodeNowTem

16、p!=headNode)linkNodeNowTemp=linkNodeNowTempnextLinkNode;linkNodeNowTemp.prevLinkNode.nextLinkNode=nulllinkNodeNowTemp.prevLinkNode.prevLinkNode=nulllinkNodeNowTemp.prevLinkNode.date=null;linkNodeNowTemp.prevLinkNode=null;elseif(linkNodeNowTemp=tailNode)linkNodeNowTemp.prevLinkNode=null;elseif(linkNo

17、deNowTemp=headNode)linkNodeNowTemp.nextLinkNode=null;headNode=nulltailNode=nullnodeSize=0;/* 判斷是否存在* /Overridepublicbooleancontains(Objectobject)headNode ;LinkNodelinkNodeNowTemp=/*/for (ifint i = 0; i <nodeSize ; i+) (object = linkNodeNowTemp. return true ;linkNodeNowTemp = linkNodeNowTemp. retu

18、rn false ;隊(duì)列是否為空Overridepublic boolean isEmpty() / TODO Auto-generated method stub return nodeSize = 0;Overridepublic int size() /TODO Auto-generated method stubreturn nodeSize ;/*根據(jù)索引號(hào)查找節(jié)點(diǎn)param index return*/public LinkNode findLinkNodeByIndex(LinkNode linkNodeNowTemp =for (int i = 0; i <nodeSizedate ) nextLinkNode ;int index) headNode ;i+) if(i=index)returnlinkNodeNowTemp;linkNodeNowTemp=linkNodeNowTemp.nextLinkNodereturnnull;OverridepublicStringtoString()StringBuffer str = LinkNode linkNode = for ( in