招代理網(wǎng)站建設(shè)公司如何推廣網(wǎng)上國(guó)網(wǎng)
棧的基本概念
講基本概念還是回到數(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)度