常用數(shù)據(jù)結構和算法5

深入Java編程專業(yè)教程理論講解部分Ver3.11第022課算法及數(shù)據(jù)結構概述：

隊列的概念隊列的實現(xiàn)重點：難點：

隊列的實現(xiàn)

隊列的實現(xiàn)25隊列隊列提供了一種“先入先出”的一種數(shù)據(jù)結構

隊列是一塊連續(xù)的(物理的或者邏輯的)存儲區(qū)域.有兩個標識標志出棧的兩個端點–頭和尾.堆棧需要提供2個最基本的操作入隊(offer)和出隊(poll)第022課算法及數(shù)據(jù)結構3第022課算法及數(shù)據(jù)結構下面我們以一個數(shù)組實現(xiàn)的循環(huán)隊列為例,進行隊列的講解.什么是循環(huán)隊列循環(huán)隊列就是反復的利用同一塊存儲空間進行隊列的移動.這種隊列的好處,是不需要隊列的整理.可以提高隊列效率.

是將數(shù)組的首尾相連,使移動到末端的隊列仍舊可以繼續(xù)爬行到數(shù)組的頭部.5隊列45.1隊列的初始化

在進行具體的初始化之前,我們需要明確,如何實現(xiàn)隊列在存儲空間尾部可以自然的移動到存儲空間頭部.

隊列的移動主要依靠兩個變量來指示,headend.隊列的移動方向定義為正方向.當head向正方向移動時,隊列向著正方向減少.當end向正方向移動時,隊列向著正方向增長.endheadendheadendhead第022課算法及數(shù)據(jù)結構初始狀態(tài)入隊出隊5隊列5當隊列移動到存儲空間邊緣時會發(fā)生什么?endhead此時end將增加到什么地方?endhead第022課算法及數(shù)據(jù)結構將end移動到數(shù)組頭部.head也是同樣的道理5.1隊列的初始化5隊列6第022課算法及數(shù)據(jù)結構

因為headend都需要有這樣的移動規(guī)則,所以給出一個next()方法來取得移動后的位置.privateintnext(inti){ return(i+1)%SIZE;}5.1隊列的初始化5隊列7下面我們來實現(xiàn)一個最簡單的循環(huán)隊列.privatefinalintSIZE;privateint[]queue;privateinthead;privateintend;

其中,SIZE是數(shù)組得大小.當這個隊列被創(chuàng)建后其大小不會改變,所以我們定義它為final(不會改變得變量).queue[]是存儲數(shù)據(jù)的數(shù)組.head標識著隊列的隊首,也就是隊列中的第一個元素.end標識著隊列尾部,它是第一個未被使用的空間.第022課算法及數(shù)據(jù)結構5.1隊列的初始化5隊列8當這個隊列被初始化之后,如圖SIZE=size;queue=newint[SIZE];head=0;end=0;初始化代碼如下:其中,size為初始化參數(shù).可以當作已知量.第022課算法及數(shù)據(jù)結構endhead0SIZE5.1隊列的初始化5隊列9一個棧被建立,我們需要在任意時刻需要了解到它得情況,比如是否為空.隊列是否為空主要依靠head與end的位置關系.publicbooleanisEmpty(){ returnend==head;}無論head與end在什么位置,當head==end時,此時隊列為空,否則隊列非空.第022課算法及數(shù)據(jù)結構5.2隊列空的判斷5隊列10第022課算法及數(shù)據(jù)結構endhead0SIZE空棧非空棧endhead0SIZE5.2隊列空的判斷5隊列11同樣,我們還需要在任何時刻需要判斷棧是否為滿棧.publicbooleanisFull(){ returnnext(end)==head;}當head前進的速度大于end的前進速度,直到head如果再前進就把end覆蓋的時候,此時隊列就滿了.當next(end)==head時,此時棧為滿,否則棧不滿.第022課算法及數(shù)據(jù)結構5.3隊列滿的判斷5隊列12第022課算法及數(shù)據(jù)結構endhead0SIZE滿棧非滿棧endhead0SIZE5.3隊列滿的判斷5隊列13將數(shù)據(jù)存儲到隊列中叫入隊.入隊的數(shù)據(jù)只能在當前的隊尾之后添加.下面我們來看看入隊的實現(xiàn).publicvoidoffer(intdata)throwsException{ if(isFull()){ thrownewException("queueisfull"); }else{ queue[end]=data; end=next(end); }}第022課算法及數(shù)據(jù)結構5.4入隊5隊列14這里我們要注意入隊的步驟:1.需要判斷棧是否是滿隊,如果隊滿,那么返回一個異常說明隊已經(jīng)滿了.無法在使其它元素入隊.如果棧非滿,那么繼續(xù).2.將數(shù)據(jù)存儲到end指向的空間.由于end始終指向第一個未使用的空間.所以可以將數(shù)據(jù)存儲進去.3.調(diào)用next()得到end的下一個位置并賦值.注意,第2步與第3步千萬不能顛倒.否則會引起棧的存儲異常.第022課算法及數(shù)據(jù)結構5.4入隊5隊列15第022課算法及數(shù)據(jù)結構endhead0SIZEendhead0SIZEendhead0SIZE1.檢查是否是滿隊2.數(shù)據(jù)加入到end所指向的位置3.將end向正方向移動5.4入隊5隊列16當需要從隊列中取出數(shù)據(jù)時,只能從隊列首部取出,這個動作叫出隊.我們來看看poll如何實現(xiàn).publicintpoll()throwsException{ if(isEmpty()){ thrownewException("queueisempty"); }else{ intresult=queue[head]; head=next(head); returnresult; }}第022課算法及數(shù)據(jù)結構5.5出隊5隊列17這里我們要注意出隊的步驟:1.需要判斷隊是否是空隊,如果隊空,那么返回一個異常說明隊已經(jīng)空了.無法彈出.如果隊非空,那么繼續(xù).3.調(diào)用next()求出head得下一個位置然后移動.2.將head指向元素保存等待返回.注意,第2步與第3步千萬不能顛倒.否則會引起隊列的存儲異常.第022課算法及數(shù)據(jù)結構4.返回保存元素.5.5出隊5隊列18第022課算法及數(shù)據(jù)結構endhead0SIZEendhead0SIZEendhead0SIZE1.檢查是否是空隊2.將head指向元素保存3.head向正方向移動5.5出隊5隊列19下面給出程序的完整代碼,及必要注釋.第022課算法及數(shù)據(jù)結構publicclassMyQueue{ privatefinalintSIZE; privateint[]queue; privateinthead; privateintend; publicMyQueue(intsize){ super(); SIZE=size; queue=newint[SIZE]; head=0; end=0; }隊列所需要的空間及標志構造函數(shù),當該類被實例化后,一個隊列就創(chuàng)建了.5隊列20privateintnext(inti){ return(i+1)%SIZE;}publicbooleanisFull(){ returnnext(end)==head;}publicvoidoffer(intdata)throwsException{ if(isFull()){ thrownewException("queueisfull"); }else{ queue[end]=data; end=next(end); }}第022課算法及數(shù)據(jù)結構5隊列21publicintpoll()throwsException{ if(isEmpty()){ thrownewException("queueisempty"); }else{ intresult=queue[head]; head=next(head); returnresult; }}publicintsize(){ return((end+SIZE)-head)%SIZE;}publicbooleanisEmpty(){ returnend==head;}第022課算法及數(shù)據(jù)結構求出隊列得大小5隊列22小結：

隊列的定義滿隊的條件空隊的條件入隊的操作順序出隊的操作順序第022課算法及數(shù)據(jù)結構231、隊列是一種()的存儲結構

A)先進先出B)后進先出C)先進后出D)任意進出2、判斷隊列空的條件是()A)head==endB)head==next(end)C)head==SIZED)end==03、判斷隊列滿的條件是()

A)head==endB)head==next(end)C)head==SIZED)end==04、入隊的順序()A)next(end)B)判斷隊空C)判斷隊滿D)數(shù)據(jù)寫入end指向的位置5、出隊的順序()A)next(head)B)判斷隊空C)判斷隊滿D)讀出head指向的位置小測驗（單選題）：第022課算法及數(shù)據(jù)結構241、隊列是一種(a)的存儲結構

A)先進先出B)后進先出C)先進后出D)任意進出2、判斷隊列空的條件是(A)A)head==endB)head==next(end)C)head==SIZED)end==03、判斷隊列滿的條件是(B)

A)head==endB)head==next(end)C)head==SIZED)end==04、入隊的順序(CDA)A)next(