跳至內容

NOIP初賽指南/棧

維基教科書,自由的教學讀本

在計算機科學中,棧(英語:stack)是一種特殊的串列形式的數據結構,它的特殊之處在於只能允許在鏈結串列或陣列的一端(稱為堆疊頂端指標,英語:top)進行加入數據(英語:push)和輸出數據(英語:pop)的運算。另外棧也可以用一維數組或連結串列的形式來完成。堆疊的另外一個相對的操作方式稱為佇列。

由於堆疊資料結構只允許在一端進行操作,因而按照後進先出(LIFO, Last In First Out)的原理運作。

在NOIP中,可以通過C++的類「stack」(需要引入「stack」頭文件)或者使用數組進行模擬。使用數組進行模擬時需要使用一個int類型的模擬「指針」代表棧頂,常用0(或1)為棧底。