用循環(huán)數(shù)組實現(xiàn)隊列

用循環(huán)數(shù)組實現(xiàn)隊列我們可以將隊列當(dāng)作一般的表用數(shù)組加以實現(xiàn)，但這樣做的效果并不好。盡管我們可以用一個游標(biāo)last來指示隊尾，使得Enqueue運算可在0(1)時間內(nèi)完成，但是在執(zhí)行Dequeue時，為了刪除隊頭元素，必須將數(shù)組中其他所有元素都向前移動一個位置。這樣，當(dāng)隊列中有n個元素時，執(zhí)行Dequeue就需要0(n)時間。為了提高運算的效率，我們用另一種方法來表達(dá)數(shù)組中各單元的位置關(guān)系。設(shè)想數(shù)組Q[1..MaxLength]中的單元不是排成一行，而是圍成一個圓環(huán)，即Q[1]接在Q[MaxLength]的后面。這種意義下的數(shù)組稱為循環(huán)數(shù)組，如圖2所示。圖2用循環(huán)數(shù)組實現(xiàn)隊列用循環(huán)數(shù)組實現(xiàn)隊列時，我們將隊列中從隊頭到隊尾的元素按順時針方向存放在循環(huán)數(shù)組中一段連續(xù)的單元中。當(dāng)需要將新元素入隊時，可將隊尾游標(biāo)Q.rear按順時針方向移一位，并在新的隊尾游標(biāo)指示的單元中存入新元素。出隊操作也很簡單，只要將隊頭游標(biāo)Q.front依順時針方向移一位即可。容易看出，用循環(huán)數(shù)組來實現(xiàn)隊列可以在0(1)時間內(nèi)完成Enqueue和Dequeue運算。執(zhí)行一系列的入隊與出隊運算，將使整個隊列在循環(huán)數(shù)組中按順時針方向移動。在圖2中，我們直接用隊頭游標(biāo)Q.front指向隊頭元素所在的單元，用隊尾游標(biāo)Q.rear指向隊尾元素所在的單元。另外，我們也可以用隊頭游標(biāo)Q.front指向隊頭元素所在單元的前一個單元，或者用隊尾游標(biāo)Q.rear指向隊尾元素所在單元的下一個單元的方法來表示隊列在循環(huán)數(shù)組中的位置，如圖3所示。

圖3循環(huán)數(shù)組中的隊頭與隊尾游標(biāo)在循環(huán)數(shù)組中，不論用哪一種方式來指示隊頭與隊尾元素，我們都要解決一個細(xì)節(jié)問題，即如何表示滿隊列和空隊列。圖4給出一個例子，MaxLength=6，隊列中已有3個元素。我們用上述3種方法來指示隊頭和隊尾元素，分別如圖4(a)、(b)和?所示。(a)

(b)(b)(c)圖4循環(huán)數(shù)組中的隊列現(xiàn)在，有3現(xiàn)在，有3個元素a^a^相繼入隊(c)所示。使隊列呈"滿"的狀態(tài)，則如圖5相應(yīng)的0)0)和(a)

(a)(c)隊列滿的情形如果在圖4中,3個元素a1,a2,a3相繼出隊，使隊列呈"空"的狀態(tài)，則如圖6相應(yīng)的(a),(b)和(c)所示。(a)

(b)(c)圖6隊列空的情形比較圖5和圖6我們看到，不論采用哪一種方式指示隊頭和隊尾元素，都需要附加說明或約定才能區(qū)分滿隊列和空隊列。通常有兩種處理方法來解決這個問題。其一是另設(shè)一個布爾量來注明隊列是空還是滿。二是約定當(dāng)循環(huán)數(shù)組中元素個數(shù)達(dá)到MaxLength-1時隊列為“滿”，使得隊列滿和隊列空時的隊頭和隊尾游標(biāo)的相對位置不同，從而滿隊列和空隊列得以區(qū)分。例如，在圖4中，當(dāng)元素a4和a5相繼入隊后，就便隊列呈"的狀態(tài)，如圖7所示。比較圖7和圖6,顯然只要測試頭和隊尾游標(biāo)的相對位置便可區(qū)分出滿隊列和空隊列。

(a)(b)(c)圖7改進(jìn)后的隊列滿的情形為確定起見，這里采用圖2的方式定義Q.front和Q.rear,另采用上述的第二種處理法區(qū)分滿隊列和空隊列。這樣，隊列的類型QueueType說明為:typeTPosition=integer;QueueType=recordElements:array[1..MaxLength]ofElementType;front,rear:TPosition;end;那么，在用循環(huán)數(shù)組實現(xiàn)的隊列中，隊列的5種基本運算可實現(xiàn)如下。其中A表示空元素，要根據(jù)不同的元素類型來確定。函數(shù)Front(Q)功能這是一個函數(shù)，函數(shù)值返回隊列Q的隊頭元素。用一般的表運算可將Front(Q)表示為Retrieve(First(Q),Q)。如果隊列為空則返回空元素A。實現(xiàn)FunctionFront(varQ:QueueType):ElementType;beginifEmpty(Q)thenreturn(A)elsereturn(Q.Elements[Q.front]);end;說明顯然復(fù)雜性顯然為0(1)。函數(shù)Enqueue(x,Q)功能將元素x插入隊列Q的隊尾。此運算也常簡稱為將元素x入隊。也可用一般的表運算將Enqueue(x,Q)表示為Insert(x,End(Q),Q)。實現(xiàn)ProcedureEnqueue(x:ElementType;varQ:QueueType);beginifFull(Q)thenError('Thequeueisfull!')elsebeginQ.rear:=Q.rearmodMaxLength+1;Q.Elements[Q.rear]:=x;end;end;Full是一個函數(shù)，若隊列Q已滿，則函數(shù)值為true,否則為false。FunctionFull(varQ:QueueType):Boolean;beginReturn((Q.front+MaxLength-Q.rear=2)or(Q.front-Q.rear=2));end;說明注意在計算隊尾的位置時，如果用Q.rear:=(Q.rear+1)modMaxLength,當(dāng)Q.rear=MaxLength-1時就會出錯，因此應(yīng)該用Q.rear:=Q.rearmodMaxLength+1。如圖7(a)所示，隊列滿有兩種情況，一種是Q.front>Q.rear且Q.front-Q.rear=2，一種是Q.frontvQ.rear且Q.front+MaxLength-Q.rear=2，根據(jù)這點可以實現(xiàn)Full函數(shù)。復(fù)雜性顯然為0(1)。函數(shù)Dequeue(Q)功能將Q的隊頭元素刪除，簡稱為出隊。用一般的表運算可將Dequeue(Q)表示為Delete(First(Q),Q)。實現(xiàn)ProcedureDequeue(varQ:QueueType);beginifEmpty(Q)thenError('Thequeueisempty!')elseQ.front:=Q.frontmodMaxLength+1;end;說明顯然。復(fù)雜性顯然為0(1)。函數(shù)Empty(Q)功能這是一個函數(shù)，若Q是一個空隊列，則函數(shù)值為true，否則為false。實現(xiàn)FunctionEmpty(varQ:QueueType):Boolean;beginreturn((Q.front-Q.rear=1)or(Q.front+MaxLength-Q.rear=1));end;說明根據(jù)圖6(a)知，隊列空有兩種情況，一種是Q.front>Q.rear且Q.front-Q.rear=1，一種是Q.frontvQ.rear且Q.front+MaxLength-Q.rear=1。復(fù)雜性顯然為0(1)。函數(shù)MakeNull(Q)功能