數(shù)據(jù)結(jié)構(gòu)與算法-棧與隊(duì)列

數(shù)據(jù)結(jié)構(gòu)與算法

(C#語(yǔ)言版)

DataStructure&AlgorithminC#第三章棧與隊(duì)列電子信息學(xué)院IPLTableofContents第1章緒論第2章線性表第3章棧與隊(duì)列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章排序電子信息學(xué)院本章位置TableofContents電子信息學(xué)院3.0簡(jiǎn)介3.1棧的概念及類型定義3.2棧的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)3.3隊(duì)列的概念及類型定義3.4隊(duì)列的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)3.5遞歸3.0Introduction棧和隊(duì)列是兩種特殊的線性結(jié)構(gòu)。它們的數(shù)據(jù)元素之間具有順序的邏輯關(guān)系，都可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。線性表的插入和刪除操作不受限制，可以在任意位置進(jìn)行。棧的插入和刪除操作只允許在表的一端進(jìn)行。隊(duì)列的插入和刪除操作則分別在表的兩端進(jìn)行。棧的特點(diǎn)是后進(jìn)先出(LIFO)

，隊(duì)列的特點(diǎn)是先進(jìn)先出(FIFO)

。3.1棧的概念及類型定義棧是一種“后進(jìn)先出”（LastInFirstOut，LIFO）的線性結(jié)構(gòu)。棧就像某種只有單個(gè)出入口的倉(cāng)庫(kù)，每次只允許一件件地往里面堆貨物（入棧），然后一件件地往外取貨物（出棧），不允許從中間放入或抽出貨物。3.1.1棧的基本概念3.1.2棧的抽象數(shù)據(jù)類型3.1.3C#中的棧類3.1.1棧的定義棧（stack）是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，其插入和刪除操作只允許在數(shù)據(jù)結(jié)構(gòu)的一端進(jìn)行。LIFO。棧中插入數(shù)據(jù)元素的過(guò)程稱為入棧(push)，刪除數(shù)據(jù)元素的過(guò)程稱為出棧(pop)。允許操作的一端稱為棧頂（top），不允許操作的一端稱為棧底（bottom）。棧頂指針：標(biāo)識(shí)棧頂?shù)漠?dāng)前位置（動(dòng)態(tài)）。3.1.2棧的抽象數(shù)據(jù)類型棧的數(shù)據(jù)元素是由n(n≥0)個(gè)數(shù)據(jù)元素a0，a1，a2，…，an-1組成的有限序列。棧記作：Stack={a0，a1，a2，…，an-1}棧中的數(shù)據(jù)元素至少具有一種相同的屬性，屬于同一種抽象數(shù)據(jù)類型。n表示棧中數(shù)據(jù)元素的個(gè)數(shù)，稱為棧的長(zhǎng)度。若n=0，則稱為空棧。棧的基本操作Initialize:棧的初始化。創(chuàng)建一個(gè)棧，并進(jìn)行初始化操作，例如設(shè)置棧狀態(tài)為空。Count:返回棧中元素個(gè)數(shù)。Empty/Full:判斷棧的狀態(tài)是否為空或滿。Push:入棧。該操作將數(shù)據(jù)元素插入棧中作為新的棧頂元素。Pop:出棧。該操作取出當(dāng)前棧頂數(shù)據(jù)元素，下一個(gè)數(shù)據(jù)元素成為新的棧頂元素。Peek:獲得但不移除棧頂數(shù)據(jù)元素。棧頂指針不變。3.1.3C#中的棧類在System.Collections名字空間中定義了一個(gè)棧類Stack，提供一種數(shù)據(jù)后進(jìn)先出的集合，其數(shù)據(jù)元素的類型是object類。Stack類的屬性和方法：

公共構(gòu)造函數(shù)Stack();

//初始化Stack類的新實(shí)例Stack(ICollectionc);Stack(intcapacity);virtualintCount{get;}

//獲取包含在棧中的元素?cái)?shù)公共屬性Stacks1=newStack();Stacks2=newStack(30);1.非泛型棧類StackStack的公共方法virtualvoidPush(objectobj);

//將對(duì)象插入棧的頂部virtualobjectPop();

//移除并返回位于棧頂部的對(duì)象virtualobjectPeek();

//返回棧頂?shù)膶?duì)象，但不將其移除virtualboolContains(objectobj);

//確定某個(gè)元素是否在棧中2.泛型棧類Stack<T>2.0版C#語(yǔ)言增加了泛型（Generics）。泛型通常與集合一起使用。

新的命名空間System.Collections.Generic，它包含定義泛型集合的接口和類，泛型集合允許用戶創(chuàng)建強(qiáng)類型集合，它能提供比非泛型集合更好的類型安全性和性能?！纠?.1】創(chuàng)建Stack對(duì)象，向其添加值以及打印出其值usingSystem;using

System.Collections;StackmyStack=newStack();myStack.Push("Hello");myStack.Push("World");myStack.Push("!");Console.WriteLine("myStack");Console.WriteLine("\tCount:{0}", myStack.Count);Console.Write("\tValues:\n");foreach(objectoinmyStack)Console.WriteLine("\t{0}",o);程序運(yùn)行結(jié)果

myStackCount:3Values:!WorldHello

【例3.2】利用棧進(jìn)行數(shù)制轉(zhuǎn)換N=an×dn+an-1×dn-1

+...+a1×d1

+a0N=(N/d)×d+N%d例如：（2468)10

轉(zhuǎn)換成(4644)8

的運(yùn)算過(guò)程如下：NN/8N%8計(jì)算順序輸出順序24683084

308384

3846

404usingSystem;usingSystem.Collections.Generic;namespacestackqueuetest{public

class

DecOctConversion{

public

static

voidMain(string[]args){

intn=2468;Stack<int>s=new

Stack<int>(20);

Console.Write("十進(jìn)制數(shù):{0}->八進(jìn)制:",n);

while(n!=0){ s.Push(n%8); n=n/8; }

inti=s.Count;

while(i>0){

Console.Write(s.Pop());i--; }

Console.WriteLine(); }}}3.2棧的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)棧作為一種特殊的線性結(jié)構(gòu)，可以如同一般線性表一樣采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)。順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧（SequencedStack），鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈?zhǔn)綏＃↙inkedStack）。3.2.1棧的順序存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)3.2.2棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)3.2.3棧的應(yīng)用舉例3.2.1棧的順序存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)public

class

SequencedStack<T>{

privateT[]items;

private

const

intempty=-1;

private

inttop=empty;

……}SequencedStack類的對(duì)象就是一個(gè)棧實(shí)例。通過(guò)對(duì)這個(gè)對(duì)象調(diào)用公有的屬性和方法訪問(wèn)類中成員或進(jìn)行相應(yīng)的操作。成員變量items用數(shù)組存儲(chǔ)棧的數(shù)據(jù)元素，成員變量top指示當(dāng)前棧頂數(shù)據(jù)元素的下標(biāo)。順序棧的操作棧的初始化返回棧的元素個(gè)數(shù)判斷棧的空與滿狀態(tài)入棧：當(dāng)棧不滿時(shí)，棧頂元素下標(biāo)top加1，將k放入top位置，作為新的棧頂數(shù)據(jù)元素。出棧：當(dāng)棧不空時(shí)，取走top處的元素，top減1，下一位置的數(shù)據(jù)元素作為新的棧頂元素。獲得棧頂數(shù)據(jù)元素的值。當(dāng)棧非空時(shí)，獲得top位置處的數(shù)據(jù)元素，此時(shí)該數(shù)據(jù)元素未出棧，top值不變。1）棧的初始化構(gòu)造方法初始化一個(gè)棧對(duì)象，它申請(qǐng)items數(shù)組的存儲(chǔ)空間來(lái)存放棧的數(shù)據(jù)元素，設(shè)置棧初始狀態(tài)為空。publicSequencedStack(intn){items=newT[n];top=empty;}publicSequencedStack():this(16){}2）返回棧的元素個(gè)數(shù)將返回棧的元素個(gè)數(shù)的成員定義為屬性，相對(duì)于成員方法顯得更簡(jiǎn)潔。public

intCount{

get{returntop+1; }}

3）判斷棧的空與滿狀態(tài)當(dāng)top==empty時(shí)，棧為空狀態(tài)；當(dāng)top≥items.Length-1時(shí)，棧為滿狀態(tài)。public

bool

Empty{

get{

returntop==empty;

}}public

bool

Full{

get{return

top>=items.Length-1;

}}4）入棧當(dāng)棧不滿時(shí)，棧頂元素下標(biāo)top加1，將k放入top位置，作為新的棧頂元素。入棧的數(shù)據(jù)是T類型，在調(diào)用該操作時(shí)，參數(shù)的類型要與棧定義時(shí)聲明的類型保持一致。當(dāng)棧當(dāng)前分配的存儲(chǔ)空間已裝滿數(shù)據(jù)元素，在進(jìn)行后續(xù)的操作前，需要調(diào)用DoubleCapacity方法重新分配存儲(chǔ)空間，并將原數(shù)組中的數(shù)據(jù)元素逐個(gè)拷貝到新數(shù)組。

public

voidPush(Tk){

if(Full)DoubleCapacity();top++;items[top]=k;}重新分配存儲(chǔ)空間private

voidDoubleCapacity(){

intcount=Count;

intcapacity=2*items.Length;T[]copy=newT[capacity];

for(inti=0;i<count;i++)copy[i]=items[i];items=copy;}當(dāng)棧不滿時(shí)，Push操作的時(shí)間復(fù)雜度為O(1)。如果需要增加容量以容納新元素，則Push操作的時(shí)間復(fù)雜度成為O(n)。5）出棧當(dāng)棧不空時(shí)，取走top位置處的元素，top減1，下一位置上的元素成為新的棧頂元素。出棧的數(shù)據(jù)元素具有類型T，在調(diào)用該操作時(shí)，將與棧定義時(shí)聲明的類型保持一致。此方法的運(yùn)算復(fù)雜度是O(1)。publicTPop(){Tk=default(T);

if(!Empty){ //棧不空k=items[top]; //取得棧頂元素top--;

returnk;}else

//棧空時(shí)產(chǎn)生異常

throw

new

InvalidOperationException();}6）獲得棧頂數(shù)據(jù)元素的值當(dāng)棧非空時(shí)，獲得top位置處的元素，此時(shí)該數(shù)據(jù)未出棧，top值不變。public

TPeek(){

if(!Empty)

returnitems[top];

else

newInvalidOperationException();}

7）輸出棧中每個(gè)數(shù)據(jù)元素的值當(dāng)棧非空時(shí)，從棧頂結(jié)點(diǎn)開始，直至棧底結(jié)點(diǎn)，依次輸出結(jié)點(diǎn)值。public

voidShow(boolshowTypeName){if(showTypeName)Console.Write(“Stack:”);if(!Empty){for(inti=this.top;i>=0;i--){Console.Write(items[i]+“”);}Console.WriteLine();}}【例3.3】使用順序棧的基本操作編譯并運(yùn)行SequencedStackTest.cs，運(yùn)行時(shí)從命令行輸入?yún)?shù)：

>cscSequencedStackTest.cs/r:..\stackqueue\bin\Debug\stackqueue.dll

>SequencedStackTestabc運(yùn)行結(jié)果如下：Push:abcstack:cbaPush:12stack:21cbaPop:21stack:cbaPush:34stack:43cbaPop:43stack:cbaPop:cba

3.2.2棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)usinglists;public

class

LinkedStack<T>:

SingleLinkedList<T>{private

SingleLinkedNode<T>top;……}

鏈?zhǔn)綏５牟僮鳁５某跏蓟袛鄺５目张c滿狀態(tài)返回棧的元素個(gè)數(shù)入棧出棧獲得棧頂數(shù)據(jù)元素的值，該數(shù)據(jù)元素未出棧。LinkedStack類的一個(gè)對(duì)象就是一個(gè)棧。成員變量top指向棧頂數(shù)據(jù)元素結(jié)點(diǎn)，結(jié)點(diǎn)類型為單向鏈表的結(jié)點(diǎn)類SingleLinkedNode，結(jié)點(diǎn)數(shù)據(jù)域的類型為泛型T。1）棧的初始化用構(gòu)造方法創(chuàng)建一個(gè)棧，它用基類（SingleLinkedList類）的構(gòu)造方法創(chuàng)建一條單向鏈表，棧的狀態(tài)初始為空。publicLinkedStack():base(){top=base.Head.Next;}2）返回棧的元素個(gè)數(shù)由基類SingleLinkedList繼承的公共屬性Count即可完成返回棧的元素個(gè)數(shù)的功能。3）判斷棧的空與滿狀態(tài)當(dāng)top==null時(shí)，棧為空；動(dòng)態(tài)向系統(tǒng)申請(qǐng)存儲(chǔ)空間，不必判斷棧是否已滿。public

override

boolEmpty{

get{returntop==null;}}

與前面比較，可以體會(huì)到面向?qū)ο蟪绦蛟O(shè)計(jì)帶來(lái)的便利。導(dǎo)出類既可以直接繼承基類的屬性和方法（子類與父類有相同的行為），也可以重寫基類的屬性和方法（子類有與父類不同的行為，但行為的命名是相同的）4）入棧在棧頂結(jié)點(diǎn)top之前插入一個(gè)結(jié)點(diǎn)來(lái)存放數(shù)據(jù)k，并使top指向新的棧頂結(jié)點(diǎn)。public

voidPush(Tk){

SingleLinkedNode<T>q=new

SingleLinkedNode<T>(k);q.Next=top;//q結(jié)點(diǎn)作為新的棧頂結(jié)點(diǎn)top=q;

base.Head.Next=top;}5）出棧當(dāng)棧不為空時(shí)，取走top指向的棧頂結(jié)點(diǎn)的值，刪除該結(jié)點(diǎn)，使top指向新的棧頂結(jié)點(diǎn)。publicTPop(){Tk=default(T);if(!Empty){//棧不空k=top.Item;//取得棧頂數(shù)據(jù)元素值top=top.Next;//刪除棧頂結(jié)點(diǎn)base.Head.Next=top;

returnk;}else

//?？諘r(shí)產(chǎn)生異常throw

new

InvalidOperationException();}6）獲得棧頂數(shù)據(jù)元素的值當(dāng)棧非空時(shí)，獲得棧頂top的數(shù)據(jù)，此時(shí)該數(shù)據(jù)元素未出棧，top值不變。public

intPeek(){if(!Empty)return

top.Item;else

thrownewInvalidOperationException();}

鏈?zhǔn)綏５幕静僮?.2.3棧的應(yīng)用舉例基于棧結(jié)構(gòu)的方法嵌套調(diào)用判斷表達(dá)式中括號(hào)是否匹配使用棧計(jì)算表達(dá)式的值1）基于棧結(jié)構(gòu)的方法嵌套調(diào)用程序中方法的嵌套調(diào)用是指在程序運(yùn)行時(shí)，一個(gè)方法中可以調(diào)用另一個(gè)方法，每個(gè)方法在執(zhí)行完后應(yīng)返回到調(diào)用它的方法中。系統(tǒng)建立一個(gè)棧結(jié)構(gòu)可以實(shí)現(xiàn)這種函數(shù)嵌套調(diào)用機(jī)制。執(zhí)行方法A時(shí)，A中的某語(yǔ)句又調(diào)用方法B，系統(tǒng)要做一系列的入棧操作：將調(diào)用語(yǔ)句后的下一條語(yǔ)句作為返回地址信息保存在棧中，該過(guò)程稱為保護(hù)現(xiàn)場(chǎng)；將A調(diào)用方法B的實(shí)參保存在棧中，該過(guò)程稱為實(shí)參壓棧；在棧中分配方法B的局部變量。子過(guò)程返回B方法執(zhí)行完成時(shí)，系統(tǒng)則要做一系列的出棧操作才能保證將系統(tǒng)控制返回調(diào)用B的方法A中退回棧中為方法B的局部變量分配的空間；退回棧中為方法B的參數(shù)分配的空間；取出保存在棧中的返回地址信息，該過(guò)程稱為恢復(fù)現(xiàn)場(chǎng)，程序繼續(xù)運(yùn)行A方法。方法調(diào)用的次序與返回的次序正好相反。可見，系統(tǒng)棧結(jié)構(gòu)是實(shí)現(xiàn)嵌套調(diào)用或遞歸調(diào)用的基礎(chǔ)。方法嵌套調(diào)用時(shí)的系統(tǒng)棧2）判斷表達(dá)式中括號(hào)是否匹配如表達(dá)式中

（［］（））或［（［］［］）］等為正確的匹配，

［（］）或（［（）]

或

[()])均為不正確的匹配。檢驗(yàn)括弧匹配的方法可用“按期待的急迫程度進(jìn)行處理”描述之。括弧匹配遵循后進(jìn)先出規(guī)律如何表示下列“不匹配”

的情況？到來(lái)的右括弧非是所“期待”的;來(lái)了一個(gè)“不速之客”;直到結(jié)束，也沒(méi)有等到“期待”的匹配;括弧匹配算法的設(shè)計(jì)思想1）凡出現(xiàn)左括弧(，則進(jìn)棧；2）凡出現(xiàn)右括弧)，首先檢查棧是否空？若?？眨瑒t表明該“右括弧)”多余否則和棧頂元素比較，若相匹配，則“左括弧(出?！狈駝t表明不匹配3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，若?？?，則表明表達(dá)式中匹配正確否則表明“左括弧(”有余。public

static

stringMatchingBracket(stringexpstr){

SequencedStack<char>s1=new

SequencedStack<char>(30);//創(chuàng)建空棧charNextToken,OutToken;inti=0;boolLlrR=true;while(LlrR&&i<expstr.Length){NextToken=expstr[i];i++;switch(NextToken){case‘('://遇見左括號(hào)時(shí),入棧s1.Push(NextToken);break;case

‘)’://遇見右括號(hào)時(shí),出棧if(s1.Empty)LlrR=false;else{OutToken=s1.Pop();if(!OutToken.Equals(‘(’))LlrR=false;//判斷出棧的是否為左括號(hào)}break;}}if(LlrR)if(s1.Empty)return

“OK!”;elsereturn

“期望)!”;elsereturn

“期望(!”;}3）表達(dá)式求值設(shè)Exp=S1+OP+S2則稱OP+S1+S2

為前綴表示法S1+OP+S2

為中綴表示法

S1+S2+OP

為后綴表示法3）中綴式丟失了括弧信息，致使運(yùn)算的次序被改變;4)前綴式的運(yùn)算規(guī)則為:

連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;5)后綴式的運(yùn)算規(guī)則為:運(yùn)算符出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式;例如:

Exp=a

b

+

(c

d/e)

f前綴式:

+

ab

c/def中綴式:

a

b

+

c

d/e

f后綴式:

ab

cde/

f

+結(jié)論:1）操作數(shù)之間的相對(duì)次序不變;2）運(yùn)算符的相對(duì)次序不同;如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

f如何從原表達(dá)式求得后綴式？

在后綴式中，優(yōu)先權(quán)高的運(yùn)算符領(lǐng)先于優(yōu)先權(quán)低的運(yùn)算符出現(xiàn)。分析“原表達(dá)式”和“后綴式”中的運(yùn)算符:原表達(dá)式:

a+b

c

d/e

f

后綴式:

abc

+de/f

每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來(lái)定。從原表達(dá)式求得后綴式的規(guī)律1)設(shè)立暫存運(yùn)算符的棧OPTR和暫存操作數(shù)的棧OPND2)設(shè)表達(dá)式的結(jié)束符為“#”,

予設(shè)運(yùn)算符棧的棧底為“#”3)若當(dāng)前字符是操作數(shù)，則進(jìn)入棧OPND;4)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧;5)否則，退出棧頂運(yùn)算符發(fā)送給后綴式;6)“(”對(duì)它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。a(b(c+d/e)-f)##a

(b

(c+d

/e

/

/++

-f-

#3.3隊(duì)列的概念及類型定義3.3.1隊(duì)列的基本概念3.3.2隊(duì)列的抽象數(shù)據(jù)類型3.3.3C#中的隊(duì)列類3.3.1隊(duì)列的基本概念隊(duì)列(queue)是一種特殊的線性表，其插入和刪除操作分別在表的兩端進(jìn)行。“先進(jìn)先出”（FirstInFirstOut，F(xiàn)IFO）的線性結(jié)構(gòu)。向隊(duì)列中插入元素的過(guò)程稱為入隊(duì)(enqueue)，刪除元素的過(guò)程稱為出隊(duì)（dequeue）。允許入隊(duì)的一端為隊(duì)尾（rear），允許出隊(duì)的一端為隊(duì)頭（front）。3.3.2隊(duì)列的抽象數(shù)據(jù)類型隊(duì)列的數(shù)據(jù)元素是由n(n≥0)個(gè)相同抽象類型的數(shù)據(jù)元素a0，a1，a2，…，an-1組成的有限序列。隊(duì)列記為：

Queue={a0，a1，a2，…，an-1}n表示隊(duì)列的元素個(gè)數(shù)，稱為隊(duì)列的長(zhǎng)度，若n=0，則稱為空隊(duì)列。隊(duì)列的基本操作Initialize:隊(duì)列的初始化。創(chuàng)建一個(gè)隊(duì)列，并進(jìn)行初始化操作。Count:返回隊(duì)列中元素個(gè)數(shù)。Empty: 判斷隊(duì)列的狀態(tài)是否為空。Full:判斷隊(duì)列的狀態(tài)是否已滿。Enqueue:入隊(duì)。該操作將數(shù)據(jù)加入隊(duì)列隊(duì)尾處。在入隊(duì)前須判斷隊(duì)列的狀態(tài)是否已滿。Dequeue:出隊(duì)。該操作取出隊(duì)頭元素。在出隊(duì)前，須判斷隊(duì)列的狀態(tài)是否為空。Peek:獲得但不移除隊(duì)首數(shù)據(jù)元素。3.3.3C#中的隊(duì)列類在System.Collections名字空間中定義了一個(gè)隊(duì)列類Queue，提供了一種數(shù)據(jù)先進(jìn)先出的集合，其數(shù)據(jù)元素的類型是object類。Queue類的屬性和方法：

公共構(gòu)造函數(shù)Queue();

//初始化Queue類的新實(shí)例Queue(ICollectionc);Queue(intcapacity);virtualintCount{get;}

//獲取包含在隊(duì)列中的元素?cái)?shù)公共屬性Queueq=newQueue();1.非泛型隊(duì)列類QueueQueue的公共方法virtualvoidEnqueue(objectobj);

//將對(duì)象添加到Queue的結(jié)尾virtualobjectDequeue();

//移除并返回位于Queue開始處的對(duì)象virtualobjectPeek();

//返回隊(duì)頭處的對(duì)象但不將其移除。virtualboolContains(objectobj);

//確定某個(gè)元素是否在隊(duì)列中【例3.5】創(chuàng)建Queue對(duì)象，向其添加值并打印出其值usingSystem;using

System.Collections;QueuemyQ=newQueue();myQ.Enqueue("Hello");myQ.Enqueue("World");myQ.Enqueue("!");Console.WriteLine("myQ");Console.WriteLine("\tCount:{0}",myQ.Count);Console.Write("\tValues:");foreach(objectoinmyQ)Console.Write("{0}\t",o);Console.WriteLine();myQCount:3Values:HelloWorld!

程序運(yùn)行結(jié)果：2.泛型隊(duì)列類Queue<T>2.0版C#語(yǔ)言增加了泛型（Generics）。泛型通常與集合一起使用。

新的命名空間System.Collections.Generic，它包含定義泛型集合的接口和類，泛型集合允許用戶創(chuàng)建強(qiáng)類型集合，它能提供比非泛型集合更好的類型安全性和性能。Queue<int>q=newQueue<int>();q.Enqueue(14);3.4隊(duì)列的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列作為一種特殊的線性表，可以如同棧和一般線性表一樣采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)。順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列稱為順序隊(duì)列，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列稱為鏈?zhǔn)疥?duì)列。3.4.1隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)3.4.2隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)3.4.3隊(duì)列的應(yīng)用舉例3.4.1隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)public

class

SequencedQueue<T>{

privateT[]items;

private

intfront,rear;……}隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)用一組連續(xù)的存儲(chǔ)空間存放隊(duì)列的數(shù)據(jù)元素。成員變量items用數(shù)組存儲(chǔ)隊(duì)列的數(shù)據(jù)元素，成員變量front和rear分別作為隊(duì)頭元素下標(biāo)和下一個(gè)入隊(duì)數(shù)據(jù)元素位置的下標(biāo)，構(gòu)成隊(duì)頭指針和隊(duì)尾指針。順序隊(duì)列“假溢出”設(shè)先有(a，b，c)入隊(duì)，那么front=0，rear=3。接著a和b出隊(duì)，d和e入隊(duì)，front=2，rear=5。如果再有數(shù)據(jù)入隊(duì)，應(yīng)存放于rear=5位置處，數(shù)組下標(biāo)溢出。順序隊(duì)列因多次入隊(duì)和出隊(duì)操作后出現(xiàn)的有存儲(chǔ)空間但不能進(jìn)行入隊(duì)操作的溢出稱為假溢出。假溢出缺陷是因?yàn)轫樞蜿?duì)列沒(méi)有重復(fù)使用存儲(chǔ)單元的機(jī)制。解決辦法是將順序隊(duì)列設(shè)計(jì)成“環(huán)形”結(jié)構(gòu)。順序循環(huán)隊(duì)列front=(front+1)%items.Length；rear=(rear+1)%items.Length；

順序循環(huán)隊(duì)列的操作隊(duì)列的初始化返回隊(duì)列的元素個(gè)數(shù)判斷隊(duì)列的空與滿狀態(tài)入隊(duì)出隊(duì)獲得隊(duì)首對(duì)象，但不將其移除1）隊(duì)列的初始化構(gòu)造方法初始化一個(gè)隊(duì)列對(duì)象，它申請(qǐng)items數(shù)組的存儲(chǔ)空間準(zhǔn)備存放隊(duì)列的數(shù)據(jù)元素，設(shè)置隊(duì)列初始狀態(tài)為空。publicSequencedQueue(intn){items=newT[n+1];front=rear=0;}publicSequencedQueue():this(16){}2）返回隊(duì)列中元素的個(gè)數(shù)public

intCount{

get{

return

(rear-front

+

items.Length)

%

items.Length;} }

3）判斷隊(duì)列的空與滿狀態(tài)當(dāng)front==rear時(shí)，隊(duì)列為空；當(dāng)front==(rear+1)%items.Length時(shí)，隊(duì)列已滿，此時(shí)items數(shù)組中仍有一個(gè)空位置。public

boolEmpty{

get{returnfront==rear;}}

public

boolFull{

get{return

front==(rear+1)%items.Length;}}

4）入隊(duì)當(dāng)隊(duì)列不滿時(shí)，將對(duì)象k存放在rear位置，作為新的隊(duì)尾數(shù)據(jù)元素，rear循環(huán)加1。入隊(duì)的數(shù)據(jù)元素是T類型，在調(diào)用該操作時(shí)，參數(shù)的類型要與隊(duì)列定義時(shí)聲明的類型保持一致。當(dāng)隊(duì)列當(dāng)前分配的存儲(chǔ)空間已裝滿數(shù)據(jù)元素，在進(jìn)行后續(xù)的操作前，需要重新分配存儲(chǔ)空間，將原數(shù)組中的數(shù)據(jù)元素逐個(gè)拷貝到新數(shù)組，并相應(yīng)調(diào)整隊(duì)首與隊(duì)尾指針。public

voidEnqueue(Tk){

if(Full)DoubleCapacity();items[rear]=k;rear=(rear+1)%items.Length;}重新分配存儲(chǔ)空間private

voidDoubleCapacity(){

inti,j,count=Count;

intcapacity=2*items.Length-1;

T[]copy=newT[capacity];

for(i=0;i<count;i++){

j=(i+front)%items.Length;copy[i]=items[j];}front=0;

rear=count;

items=copy;

}當(dāng)隊(duì)列不滿時(shí)，Enqueue方法為O(1)操作。如果需要重新分配內(nèi)部數(shù)組以容納新元素，則此方法成為O(n)操作。5）出隊(duì)當(dāng)隊(duì)列不空時(shí)，取走front位置上的隊(duì)首元素，front循環(huán)加1，指向新的隊(duì)首元素。運(yùn)算復(fù)雜度是O(1)。publicTDequeue(){Tk=default(T);

if(!Empty){//隊(duì)列不空k=items[front];front=(front+1)%items.Length;returnk;}else//?？諘r(shí)產(chǎn)生異常throw

newInvalidOperationException();}6）獲得隊(duì)首對(duì)象獲得但不移除隊(duì)首對(duì)象。當(dāng)隊(duì)列不為空時(shí)，取走front位置上的隊(duì)首數(shù)據(jù)，front不變。publicTPeek(){if(!Empty)returnitems[front];else

throw

new

InvalidOperationException();}順序循環(huán)隊(duì)列小結(jié)入隊(duì)時(shí)只改變下標(biāo)rear，出隊(duì)時(shí)只改變下標(biāo)front，它們都做循環(huán)移動(dòng)，取值范圍是0~items.Length-1，這使得存儲(chǔ)單元可以重復(fù)使用，避免“假溢出”現(xiàn)象。在隊(duì)列中設(shè)立一個(gè)空位置。如果不設(shè)立一個(gè)空位置，則隊(duì)列滿的條件也是front==rear，那么就無(wú)法與隊(duì)列空的條件（front==rear）相區(qū)別。而設(shè)立一個(gè)空位置，則隊(duì)列滿的條件是

front==(rear+1)%items.Length3.4.2隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)public

class

LinkedQueue<T>{

private

SingleLinkedList<T>items;

private

SingleLinkedNode<T>front,rear;}

LinkedQueue類的一個(gè)對(duì)象就是一個(gè)隊(duì)列。成員變量front和rear分別指向隊(duì)頭和隊(duì)尾結(jié)點(diǎn)，結(jié)點(diǎn)類型為單鏈表節(jié)點(diǎn)類SingleLinkedNode<T>。鏈?zhǔn)疥?duì)列隊(duì)列的操作隊(duì)列的初始化返回隊(duì)列的元素個(gè)數(shù)判斷隊(duì)列的空與滿狀態(tài)入隊(duì)出隊(duì)獲得隊(duì)首對(duì)象1）隊(duì)列的初始化構(gòu)造方法創(chuàng)建一條單向鏈表用作隊(duì)列，設(shè)置初始狀態(tài)為空。publicLinkedQueue(){items=new

SingleLinkedList<T>();front=items.Head.Next;

rear=items.Head;}2）返回隊(duì)列中元素的個(gè)數(shù)public

intCount{

get{

returnitems.Count;}}

3）判斷隊(duì)列的空與滿狀態(tài)當(dāng)front==null且rear==items.Head時(shí)，隊(duì)列為空；不需要判斷隊(duì)列是否已滿。public

boolEmpty{

get{return(front==null)&&(rear==items.Head);}}4）入隊(duì)在rear指向的隊(duì)尾結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)存放k，并使rear指向新的隊(duì)尾結(jié)點(diǎn)。此時(shí)入隊(duì)的數(shù)據(jù)元素是T類型，在調(diào)用該操作時(shí)，參數(shù)的類型要與隊(duì)列定義時(shí)聲明的類型保持一致。此方法的運(yùn)算復(fù)雜度是O(1)。public

voidEnqueue(Tk){

SingleLinkedNode<T>q=new

SingleLinkedNode<T>(k);rear.Next=q;front=items.Head.Next;rear=q;}5）出隊(duì)當(dāng)隊(duì)列不為空時(shí)，取走front指向的隊(duì)首結(jié)點(diǎn)的數(shù)據(jù)元素，并刪除該結(jié)點(diǎn)，使front指向新的隊(duì)首結(jié)點(diǎn)。此時(shí)出隊(duì)的數(shù)據(jù)元素具有類型T，在調(diào)用該操作時(shí)，將與隊(duì)列定義時(shí)聲明的類型保持一致。此方法的運(yùn)算復(fù)雜度是O(1)。publicTDequeue(){Tk=default(T);if(!Empty){//隊(duì)列不空k=front.Item;//取得隊(duì)頭結(jié)點(diǎn)數(shù)據(jù)元素front=front.Next;//刪除隊(duì)頭結(jié)點(diǎn)items.Head.Next=front;if(front==null)

rear=items.Head;returnk;}elsethrow

new

Invali