棧的基本概念

講基本概念還是回到數(shù)據(jù)結(jié)構(gòu)的三要素：邏輯結(jié)構(gòu)，物理結(jié)構(gòu)和數(shù)據(jù)運(yùn)算。

• 從邏輯結(jié)構(gòu)來(lái)講，棧的各個(gè)數(shù)據(jù)元素之間是通過(guò)是一對(duì)一的線性連接，因此棧也是屬于線性表的一種
• 從物理結(jié)構(gòu)來(lái)說(shuō)，?？梢允琼樞虼鎯?chǔ)和順序表一樣，也可以是鏈?zhǔn)酱鎯?chǔ)和鏈表一樣，但棧的主要特點(diǎn)不是存儲(chǔ)的位置關(guān)系，而是操作限制：棧的插入或刪除都只可以在其一端進(jìn)行。
• 從數(shù)據(jù)運(yùn)算來(lái)講，棧的插入和刪除都只能在一端進(jìn)行，因此其基本操作沒(méi)有刪除和插入一說(shuō)，而是講進(jìn)棧和出棧；除了這兩個(gè)基本操作外，棧還包括初始化棧，銷毀棧，讀棧頂元素等操作。
  棧的基本術(shù)語(yǔ)
  我們可以將棧視為一個(gè)長(zhǎng)形的桶，把數(shù)據(jù)元素看成一個(gè)個(gè)小球，然后一個(gè)個(gè)將球放進(jìn)桶里的過(guò)程。
• 棧底元素：最先放進(jìn)去的小球在桶的最下面，我們叫它棧底元素；
• 棧頂元素：最后放進(jìn)去的小球在桶的最上面，我們叫它棧頂元素；
• 棧頂：所以我們把能插入和刪除的那一端稱為棧頂，棧頂是可變的
• 棧底：不能插入和刪除的呢一段稱為棧底，棧底是固定的
• 空棧：棧里面沒(méi)有一個(gè)元素稱為空棧
  
  數(shù)據(jù)元素進(jìn)棧順序：1->2->3
  數(shù)據(jù)元素出棧順序：3->2->1
  棧的特點(diǎn)是先進(jìn)后出(LIFO)
  棧的基本操作
• 創(chuàng)建棧：構(gòu)建一個(gè)空棧S，分配內(nèi)存空間
• 銷毀棧：釋放棧內(nèi)元素及其內(nèi)存空間
• 進(jìn)棧：在棧未滿時(shí)，將元素x從棧頂壓入棧稱為新棧頂
• 出棧：在棧不是空棧時(shí)，彈出棧頂元素，下一個(gè)元素稱為新棧頂元素
• 查棧頂元素
• 判別棧是否為空棧
  棧操作的常見錯(cuò)誤
• 棧下溢(underflow) top=0 即為空棧 empty 時(shí)執(zhí)行出棧
• 棧上溢(overflow) top>n n為棧的長(zhǎng)度