鏈式棧

鏈式棧是一種數據存儲結構,可以通過單鍊表的方式來實現,使用鏈式棧的優點在於它能夠克服用數組實現的順序棧空間利用率不高的特點,但是需要為每個棧元素分配額外的指針空間用來存放指針域。

介紹

棧是只能在某一端插入和刪除的特殊線性表。它按照後進先出的原則存儲數據,先進入的數據被壓入棧底(push),最後的數據在棧頂(top),需要讀數據的時候從棧頂開始彈出數據(top)最後一個數據被第一個讀出來。鏈式棧中的元素以Node的形式存儲,節點Node中存有此節點存於棧中的元素以及指向下個節點的指針。鏈式棧的數據成員只用保存指向棧頂節點的指針 *top_node。

順序棧的實現在於使用了數組這個基本數據結構,數組中的元素在記憶體中的存儲位置是連續的,且編譯器要求我們在編譯期就要確定數組的大小,這樣對記憶體的使用效率並不高,一來無法避免因數組空間用光而引起的溢出問題,二在系統將記憶體分配給數組後,則這些記憶體對於其他任務就不可用;而對於鏈棧而言,使用了鍊表來實現棧,鍊表中的元素存儲在不連續的地址,由於是動態申請記憶體,所以我們可以以非常小的記憶體空間開始,另外當某個項不使用時也可將記憶體返還給系統。

代碼

1、鏈式棧的類型定義

2、判斷空棧

3、取棧頂元素

4、入棧

5、出棧

相關詞條

相關搜尋

熱門詞條

聯絡我們