c-數(shù)據(jù)結(jié)構(gòu)第3章棧和隊列

第3章棧和隊列《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT2引入《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT棧和隊列是軟件設(shè)計中常用的兩種數(shù)據(jù)結(jié)構(gòu)，它們的邏輯結(jié)構(gòu)和線性表相同。其不同之處在于，棧和隊列的相關(guān)操作具有特殊性，它們只是線性表相關(guān)操作的一個子集。更準(zhǔn)確地說，一般線性表上的插入、刪除操作不受限制，而棧和隊列上的插入、刪除操作均受某種特殊限制。因此，棧和隊列也稱作操作受限的線性表。

33.1棧（stack）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.1.1棧的概念及操作特征1棧是線性表的一個特例棧只能對線性表的固定一端進(jìn)行插入和刪除操作棧數(shù)據(jù)的主要特點是“后進(jìn)先出”（LastInFirstOut，LIFO）或“先進(jìn)后出”（FirstInLastOut，F(xiàn)ILO）的43.1棧（stack）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.1.1棧的概念及操作棧頂（Top）是棧中允許進(jìn)行數(shù)據(jù)插入和刪除的那一端。棧底（Bottom）是棧中無法進(jìn)行數(shù)據(jù)操作的那一端。棧上溢（Full）：在棧內(nèi)空間已存滿數(shù)據(jù)時，如果仍然希望能做壓棧動作，就會產(chǎn)生“上溢出”。棧下溢（Empty）：在棧內(nèi)空間已無數(shù)據(jù)時，如果仍然希望能做出棧動作，就會產(chǎn)生“下溢出”?；靖拍?棧頂壓棧an．．．a(chǎn)3a2a1出棧棧底53.1棧（stack）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.1.1棧的概念及操作基本操作3進(jìn)?；蛉霔＃≒ush）棧頂棧底ABCPush(A)Push(B)Push(C)63.1棧（stack）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.1.1棧的概念及操作基本操作3彈出或出棧（Pop）棧頂棧底ABCPop()Pop()Pop()73.1棧（stack）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.1.2System.Collections.Stack例3-1Stack.cs83.1棧（stack）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.1.3棧的應(yīng)用?？蓮V泛用于解決表達(dá)式求值、進(jìn)制轉(zhuǎn)換、括號匹配、迷宮、遞歸調(diào)用等滿足“先進(jìn)后出”原則的問題，這里僅介紹如何用棧解決進(jìn)制轉(zhuǎn)換問題?！纠?-1Demo3-1.cs】進(jìn)制轉(zhuǎn)換93.2隊列（Queue）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.2.1隊列的概念及操作隊列的定義1隊列（Queue）是只允許在一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表。它所有的插入均限定在表的一端進(jìn)行，該端稱為隊尾，所有的刪除則限定在表的另一端進(jìn)行，該端則稱為隊頭。

入隊出隊a1a2…an隊頭隊尾103.2隊列（Queue）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.2.1隊列的概念及操作隊頭（Head）是隊列中允許數(shù)據(jù)刪除的那一端。隊尾（Tail）是隊列中允許數(shù)據(jù)插入的那一端。隊上溢（Full）：在隊內(nèi)空間存滿數(shù)據(jù)時，如果仍然希望做入隊動作，就會產(chǎn)生“上溢出”，這是一種空間不足的出錯狀態(tài)。隊下溢（Empty）：在隊內(nèi)空間已無數(shù)據(jù)時，如果仍然希望做出隊動作，就會產(chǎn)生“下溢出”，這是一種數(shù)據(jù)不足的出錯狀態(tài)?；靖拍?入隊出隊a1a2…an隊頭隊尾113.2隊列（Queue）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.2.1隊列的概念及操作基本操作3入隊（Enqueue）隊頭隊尾ABCEnqueue(A)Enqueue(B)Enqueue(C)123.2隊列（Queue）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.2.1隊列的概念及操作基本操作3出隊（Dequeue）隊頭隊尾ABCDequeue()133.2隊列（Queue）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.2.2循環(huán)隊列由于數(shù)組在刪除元素時，需要花費大量時間移動大量元素，因此基于數(shù)組的隊列在隊頭數(shù)據(jù)執(zhí)行出隊操作時，速度較慢，很少有實際應(yīng)用，所以多采用循環(huán)隊列方式。為了避免大量的數(shù)據(jù)移動，通常將一維數(shù)組中的各個元素看成是一個首尾相接的封閉的圓環(huán)，即第一個元素是最后一個元素的下一個元素，這種形式的順序隊列稱為循環(huán)隊列

運行虛擬循環(huán)隊列演示程序143.2隊列（Queue）《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT3.2.3System.Collections.Queue153.3本章小結(jié)《數(shù)據(jù)結(jié)構(gòu)(C#語言描述)》配套PPT棧和隊列的基本操作都是單個元素的“進(jìn)”、“出”操作，棧的操作是進(jìn)棧和出棧，隊列的操作是進(jìn)隊和出隊。所不同的是棧是一種“先進(jìn)后出”的數(shù)據(jù)結(jié)構(gòu)而隊列是一種“先進(jìn)先出”的數(shù)據(jù)結(jié)構(gòu)。C#中實現(xiàn)了棧的集合類是Stack和Stack<T>兩種，實現(xiàn)了隊列的集合類是Queue和Queue<T>兩種。16順序表及其特點順序表及其特點順序表是指線性表的存儲結(jié)構(gòu)是連續(xù)的，用一塊地址連續(xù)的空間依次存儲線性表中的數(shù)據(jù)元素。順序表的特點是訪問速度快由于線性表中每個元素所占用的空間是相同的，只需按照公式計算便可以快速地訪問指定元素。假設(shè)順序表中第一個元素的位置是Loc，每個數(shù)據(jù)元素所占用的存儲空間為n：a1a2．．．a(chǎn)i．．．線性存儲空間下標(biāo)位置01i-1存儲地址LocLoc+nLoc+(i–1)*n17數(shù)組數(shù)組是最基本的線性表，在System命名空間中。C#中的數(shù)組一維數(shù)組多維數(shù)組參數(shù)數(shù)組鋸齒狀數(shù)組數(shù)組的缺點是不能動態(tài)改變集合的大小18動態(tài)數(shù)組ArrayList數(shù)組的集合大小可以改變，屬于System.Collections命名空間。ArrayList的Capacity屬性值是數(shù)組元素的數(shù)量，初始值是16，，如果不夠則加倍。ArrayList用Object存儲對象19ArrayList類中的成員Add():AddsanelementtotheArrayList.AddRange():AddstheelementsofacollectiontotheendoftheArrayList.Capacity:StoresthenumberofelementstheArrayListcanhold.Clear():RemovesallelementsfromtheArrayList.Contains():DeterminesifaspecifieditemisintheArrayList.CopyTo():CopiestheArrayListorasegmentofittoanarray.Count:ReturnsthenumberofelementscurrentlyintheArrayList.GetEnumerator():ReturnsanenumeratortoiterateovertheArrayList.GetRange():ReturnsasubsetoftheArrayListasanArrayList.20IndexOf():Returnstheindexofthefirstoccurrenceofthespecifieditem.Insert():InsertanelementintotheArrayListataspecifiedindex.InsertRange():InsertstheelementsofacollectionintotheArrayListstartingatthespecifiedindex.Item():Getsorsetsanelementatthespecifiedindex.Remove():Removesthefirstoccurrenceofthespecifieditem.RemoveAt():Removesanelementatthespecifiedindex.Reverse():ReversestheorderoftheelementsintheArrayList.Sort():Alphabetic