【正文】 棧時(shí)只能在棧頂進(jìn)行，所以 an先出棧， a1最后出棧。因此又稱棧為后進(jìn)先出（ Last In First Out，簡稱 LIFO）線性表。 ? 棧有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)設(shè)指針 top指示棧頂元素的當(dāng)前位置。空棧的棧頂指針值為零。棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)由其棧頂?shù)闹羔樜ㄒ淮_定。 Delphi程序設(shè)計(jì) 棧 1. 棧的基本操作 棧有許多操作，基本操作有入棧和出棧。 ? 入棧（ push） 入棧是在棧頂添加新的元素。 ? 出棧（ pop） 出棧是將棧頂?shù)脑匾谱卟⒎祷亟o用戶。 Delphi程序設(shè)計(jì) 入棧操作 棧 棧頂 棧 棧頂 數(shù)據(jù) 入棧操作 棧 Delphi程序設(shè)計(jì) 出棧操作 棧 棧頂 棧 棧頂 數(shù)據(jù) 出棧操作 出棧操作 棧 Delphi程序設(shè)計(jì) 棧 2. 棧的應(yīng)用 ? 倒轉(zhuǎn)數(shù)據(jù)是對(duì)一組給定的數(shù)據(jù)，對(duì)其中的數(shù)據(jù)元素重新排放位置，使得意向性元素互換，中間所有元素也相應(yīng)地進(jìn)行交換。 ? 回溯也是一種棧的重要應(yīng)用?；厮荩椿氐剑ɑ蚧謴?fù)到）前面的數(shù)據(jù)，在計(jì)算機(jī)游戲、決策分析和專家系統(tǒng)等應(yīng)用程序中經(jīng)常見到。 （ 具體見 “ 倒轉(zhuǎn)數(shù)據(jù)演示程序 ” ） Delphi程序設(shè)計(jì) 隊(duì)列 隊(duì)列也是線性列表的一種特殊情況，其所有的插入均限定在表的一端進(jìn)行，而所有的刪除則限定在表的另一端進(jìn)行。允許插入的一端稱隊(duì)尾，允許刪除的一端稱隊(duì)頭。隊(duì)列的結(jié)構(gòu)特點(diǎn)是先進(jìn)隊(duì)列的元素先出隊(duì)列。因此，通常把隊(duì)列叫做先進(jìn)先出（ First In First Out，簡稱 FIFO）線性表。 Delphi程序設(shè)計(jì) 本章小結(jié) ? 算法是為了求解某一問題在有限步驟內(nèi)、定義了具體操作序列的規(guī)則集合。一個(gè)算法應(yīng)該具有的五個(gè)重要特征是：確切性、輸入、輸出、可行性、有窮性。 ? 算法不依賴于具體的編程語言，它可以用偽代碼和圖形這兩種方式來描述。 ? 偽代碼是一種算法描述語言。使用偽代碼的目的是為了使被描述的算法可以容易地以任何一種編程語言實(shí)現(xiàn)。 Delphi程序設(shè)計(jì) 本章小結(jié) ? 程序設(shè)計(jì)中，能夠用來表示算法的圖主要有： PAD圖、 N\S盒圖、流程圖。 PAD的目的在于以圖表現(xiàn)程序的邏輯結(jié)構(gòu)，使程序易讀、易記、易理解。N/S圖是一種不需要有向線段，無需上下左右前后追蹤程序流程控制的程序流程圖，該圖非常適合描述結(jié)構(gòu)化程序或者算法的結(jié)構(gòu)化實(shí)現(xiàn)，能夠較好地反映算法和程序的層次結(jié)構(gòu)，具有自頂向下逐步求精的特征。流程圖則使用大圖的形式掩蓋了算法所有的細(xì)節(jié)方面，它只顯示算法從開始到結(jié)束的整個(gè)流程。適用于設(shè)計(jì)一個(gè)完整的程序或者部分程序。 Delphi程序設(shè)計(jì) 本章小結(jié) ? 常用算法包括基本算法、排序算法、查找算法、迭代和遞歸算法等。 ? 基本算法大都比較簡單，是其他算法的基礎(chǔ)。這類算法在程序中應(yīng)用非常普遍，如：累加求和、累乘求積、求最大和最小值等。 ? 排序算法根據(jù)數(shù)據(jù)的值對(duì)它們進(jìn)行排列。排序是為了把不規(guī)則的信息進(jìn)行整理，以提高查找效率。常用的排序方法包括：選擇排序、冒泡排序、插入排序、快速排序、合并排序、希爾排序、堆排序等。 Delphi程序設(shè)計(jì) 本章小結(jié) ? 查找是一種在列表中確定目標(biāo)所在位置的算法?；镜牟檎曳椒ㄓ许樞虿檎液驼郯氩檎?。 ? 迭代和遞歸是用于編寫解決問題的算法的兩種途徑。迭代就是反復(fù)替換的意思，它通過使用一個(gè)中間變量保存中間結(jié)果，不斷反復(fù)計(jì)算求解最終值。遞歸是一個(gè)算法自我調(diào)用的過程，用遞歸調(diào)用的算法就是遞歸算法。 ? 算法的復(fù)雜性是指在執(zhí)行時(shí)，算法所需要計(jì)算機(jī)資源的量。 Delphi程序設(shè)計(jì) 本章小結(jié) ? 集合類型是一群相同類型元素的組合，這些類型必須是有限類型。集合類型的定義是 set of BaseType，集合的操作包括：關(guān)系運(yùn)算、增刪元素、交集運(yùn)算。 ? 數(shù)組用于表示相同類型的元素的有序集合，數(shù)組中每個(gè)元素都有一個(gè)唯一的索引。根據(jù)數(shù)組的分配方式可將數(shù)組分為：靜態(tài)數(shù)組和動(dòng)態(tài)數(shù)組。其中，動(dòng)態(tài)數(shù)組可以使用不確定的數(shù)組長度，而在程序中動(dòng)態(tài)地分配數(shù)組的存儲(chǔ)空間。 Delphi程序設(shè)計(jì) ? 使用標(biāo)準(zhǔn)函數(shù) Low和 High可分別返回?cái)?shù)組中第一個(gè)索引類型其范圍的最低和最高值。還可用標(biāo)準(zhǔn)函數(shù) Length返回?cái)?shù)組中第一維的元素?cái)?shù)量。 ? 冒泡法的基本思想是，將待排序的元素看作是豎著排列的 “ 氣泡 ” ，較小的元素比較輕，從而要往上浮。一個(gè)含有 n個(gè)元素的列表，冒泡排序需要 n1次掃描來完成數(shù)據(jù)排序。 ? 快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是，通過一輪排序?qū)⒋判虻臄?shù)組元素分割成獨(dú)立的兩部分，其中一部分元素的關(guān)鍵字均比另一部分元素的關(guān)鍵字小，則分別可對(duì)這兩部分元素繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)數(shù)組序列有序。 本章小結(jié) Delphi程序設(shè)計(jì) ? 順序查找就是將要查找的數(shù)據(jù)的關(guān)鍵字按一定的順序挨個(gè)與列表中的數(shù)據(jù)進(jìn)行比較，相等時(shí)就找到了所要的數(shù)據(jù)。 ? 對(duì)有序的列表可以使用更有效率的折半查找。折半查找是從一個(gè)列表的中間的元素來測試的，這將能夠判別出目標(biāo)在列表里的前半部還是后半部分。如果在前半部分，就不需要查找后半部分。如果在后半部分，就不需要查找前半部分。換句話說，可以通過判斷排除一半的列表。重復(fù)這個(gè)過程直到找到目標(biāo)或是目標(biāo)不在這個(gè)列表里。 本章小結(jié) Delphi程序設(shè)計(jì) ? 開放式數(shù)組是指使用數(shù)組作為形參傳遞給過程或函數(shù)時(shí)，其長度是不確定的。因此，在調(diào)用這個(gè)過程或函數(shù)時(shí)，可以傳遞不同長度的數(shù)組作為實(shí)參。 ? 抽象數(shù)據(jù)類型（ ADT）就是與對(duì)該數(shù)據(jù)類型有意義的操作封裝在一起的數(shù)據(jù)聲明。它將數(shù)據(jù)和操作封裝起來，用戶可通過操作接口對(duì)數(shù)據(jù)進(jìn)行操作。常用的抽象數(shù)據(jù)類型有鏈表、棧、對(duì)列等 ? 鏈表是一組互相鏈接的元素序列，分為：單鏈表、循環(huán)鏈表、雙向鏈表等。 本章小結(jié) Delphi程序設(shè)計(jì) ? 在 Delphi的 VCL中，有一些現(xiàn)成的可以當(dāng)作鏈表使用的抽象數(shù)據(jù)類型，如： TList、 TStrings和TCollection。其中， TList是 Delphi中最基本的鏈表，它能實(shí)現(xiàn)鏈表常用的操作，包括：增加、刪除、定位、查找、遍歷等，這足夠解決一切關(guān)于有序列表的問題。 ? 棧是限定僅在一端進(jìn)行插入或刪除操作的線性表。棧又稱為后進(jìn)先出（ LIFO）線性表。 ? 棧的應(yīng)用非常廣泛，如：倒轉(zhuǎn)數(shù)據(jù)、回溯等。在Delphi的 VCL中，有現(xiàn)成的 TStack抽象數(shù)據(jù)類型可以使用。 本章小結(jié) Delphi程序設(shè)計(jì) ? 隊(duì)列是線性列表的一種特殊情況，其所有的插入均限定在表的一端進(jìn)行，而所有的刪除則限定在表的另一端進(jìn)行。隊(duì)列的結(jié)構(gòu)特點(diǎn)是先進(jìn)隊(duì)列的元素先出隊(duì)列。隊(duì)列又稱為先進(jìn)先出（ FIFO）線性表 . ? 對(duì)列主要應(yīng)用于排隊(duì)處理用戶請求、任務(wù)和指令。在計(jì)算機(jī)系統(tǒng)中，需要用隊(duì)列來完成對(duì)作業(yè)或?qū)ο到y(tǒng)設(shè)備如打印池的處理。同樣，在 Delphi的 VCL中，有現(xiàn)成的 TQueue抽象數(shù)據(jù)類型可以使用。 本章小結(jié)