介紹
棧是只能在某一端插入和刪除的特殊線性表。它按照後進先出的原則存儲數據,先進入的數據被壓入棧底(push),最後的數據在棧頂(top),需要讀數據的時候從棧頂開始彈出數據(top)最後一個數據被第一個讀出來。鏈式棧中的元素以Node的形式存儲,節點Node中存有此節點存於棧中的元素以及指向下個節點的指針。鏈式棧的數據成員只用保存指向棧頂節點的指針 *top_node。
順序棧的實現在於使用了數組這個基本數據結構,數組中的元素在記憶體中的存儲位置是連續的,且編譯器要求我們在編譯期就要確定數組的大小,這樣對記憶體的使用效率並不高,一來無法避免因數組空間用光而引起的溢出問題,二在系統將記憶體分配給數組後,則這些記憶體對於其他任務就不可用;而對於鏈棧而言,使用了鍊表來實現棧,鍊表中的元素存儲在不連續的地址,由於是動態申請記憶體,所以我們可以以非常小的記憶體空間開始,另外當某個項不使用時也可將記憶體返還給系統。
代碼
1、鏈式棧的類型定義
2、判斷空棧
3、取棧頂元素
4、入棧
5、出棧