棧的概念
棧是限制在表的一端進行插入和刪除運算的線性表脓恕，通常稱插入、刪除的這一端為棧頂，另一端為棧底拂苹。當表中沒有元素時成為空棧。
棧的進出順序判斷：
棧的基本操作：
順序棧
順序棧利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素痰洒，同時由于棧的操作的特殊性瓢棒，還必須附設一個位置指針top來動態(tài)地指示棧頂元素的順序棧中的位置。通常以top=0表示空棧丘喻。
順序棧的基本運算：
鏈棧：采用鏈表作為存儲結構實現(xiàn)的棧脯宿。為便于操作，采用帶頭結點的單鏈表實現(xiàn)棧泉粉。因為棧的插入和刪除操作僅限制在表頭位置進行连霉，所以鏈表的表頭指針就作為棧頂指針。
順序棧和鏈式棧的比較：實現(xiàn)鏈式棧和順序棧的操作都是需要常數(shù)時間嗡靡，即時間復雜度為O（1）跺撼，主要從空間和時間兩個方面考慮。初始時讨彼，順序堆棧必須說明一個固定的長度歉井，當堆棧不夠滿時，造成一些空間的浪費哈误，而鏈式堆棧的長度可變則使長度不需要預先設定哩至，相對比較節(jié)省空間，但是在每個節(jié)點中設置了一個指針域蜜自，從而產生了結構開銷菩貌。
