棧和隊列是兩種特殊的線性表它們的邏輯結構和線性表相同只是其運算規則較線性表有更多的限制故又稱它們為運算受限的線性表棧和隊列被廣泛應用於各種程序設計中
棧的定義及基本運算
棧的定義
棧(Stack)是限制僅在表的一端進行插入和刪除運算的線性表
()通常稱插入刪除的這一端為棧頂(Top)另一端稱為棧底(Bottom)
()當表中沒有元素時稱為空棧
()棧為後進先出(Last In First Out)的線性表簡稱為LIFO表
棧的修改是按後進先出的原則進行每次刪除(退棧)的總是當前棧中最新的元素即最後插入(進棧)的元素而最先插入的是被放在棧的底部要到最後才能刪除
【示例】元素是以aa…an的順序進棧退棧的次序卻是anan…a
棧的基本運算
()InitStack(S)
構造一個空棧S
()StackEmpty(S)
判棧空若S為空棧則返回TRUE否則返回FALSE
()StackFull(S)
判棧滿若S為滿棧則返回TRUE否則返回FALSE
注意
該運算只適用於棧的順序存儲結構
()Push(Sx)
進棧若棧S不滿則將元素x插入S的棧頂
()Pop(S)
退棧若棧S非空則將S的棧頂元素刪去並返回該元素
()StackTop(S)
取棧頂元素若棧S非空則返回棧頂元素但不改變棧的狀態
From:http://tw.wingwit.com/Article/program/sjjg/201311/22855.html