堆棧指針總是指向棧頂位置。一般堆棧的棧底不能動(dòng),所以數(shù)據(jù)入棧前要先修改堆棧指針,使它指向新的空余空間然后再把數(shù)據(jù)存進(jìn)去,出棧的時(shí)候相反。堆棧指針,隨時(shí)跟蹤棧頂?shù)刂罚础跋冗M(jìn)后出”的原則存取數(shù)據(jù)。
堆棧指針是什么
棧是一種特殊的線性表,是一種只允許在表的一端進(jìn)行插入或刪除操作的線性表。表中允許進(jìn)行插入、刪除操作的一端稱為棧頂。表的另一端稱為棧底。棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)的,對(duì)棧頂當(dāng)前位置的標(biāo)記稱為棧頂指針。當(dāng)棧中沒(méi)有數(shù)據(jù)元素時(shí),稱之為空棧。棧的插入操作通常稱為進(jìn)?;蛉霔?,棧的刪除操作通常稱為退?;虺鰲?。
計(jì)算機(jī)中的堆棧主要用來(lái)保存臨時(shí)數(shù)據(jù),局部變量和中斷/調(diào)用子程序程序的返回地址。
堆棧指針是在棧操作過(guò)程中,有一個(gè)專門的棧指針(習(xí)慣上稱它為TOP),指出棧頂元素所在的位置。
堆棧指針總是指向棧頂元素。
堆??梢允瓜蛳律L(zhǎng)的(向低地址),也可以是向上生長(zhǎng)的。
如果堆棧是向上生長(zhǎng)的,數(shù)據(jù)入棧的時(shí)候,堆棧指針先加1,再壓棧。出棧的時(shí)候先彈出數(shù)據(jù),堆棧指針再減1。如果堆棧是向下生長(zhǎng)的,數(shù)據(jù)入棧時(shí)指針將減1,數(shù)據(jù)出棧時(shí)指針將加1。
堆棧指針有什么作用?
堆棧指針SP在片內(nèi)RAM128B中開(kāi)辟棧區(qū),并隨時(shí)跟蹤棧頂?shù)刂?。它是按“先進(jìn)后出”的原則存取數(shù)據(jù)。開(kāi)機(jī)復(fù)位后,單片機(jī)棧底地址為07H。
主要用來(lái)保存臨時(shí)數(shù)據(jù),局部變量和中斷/ 自程序的返回地址。堆棧指針總是指向棧頂元素。所以數(shù)據(jù)入棧的時(shí)候,堆棧指針先加1,再壓棧。向上增長(zhǎng)方式與計(jì)算機(jī)的方式一樣。
出棧的時(shí)候先彈出數(shù)據(jù),堆棧指針再減1。
如果堆棧的實(shí)現(xiàn)是往上長(zhǎng)的(就是說(shuō)往頂?shù)姆较蜷L(zhǎng),其實(shí)質(zhì)是棧底是定死的不能動(dòng),入棧的東西只能不斷往上疊,這就像在書(shū)桌上放書(shū)一樣; 桌底是定死的,所以書(shū)只能一本一本地往上堆,往上長(zhǎng)),計(jì)算機(jī)內(nèi)部的堆棧的實(shí)現(xiàn)采取的就是這種模式,所以就得像你說(shuō)的那樣,“先修改指針,然后插入數(shù)據(jù),出棧時(shí)剛好相反“,因?yàn)槎褩V羔樦赶虻目偸菞m斣?,棧底不能?dòng),所以數(shù)據(jù)入棧前要先修改指針使它指向新的空余空間然后再把數(shù)據(jù)存進(jìn)去,出棧的時(shí)候自然相反。
然而,如果堆棧的實(shí)現(xiàn)是往下長(zhǎng)的(就是說(shuō)每壓一個(gè)元素入棧,棧底就自動(dòng)下移一個(gè)元素的位置,其實(shí)質(zhì)就是這種堆棧模型是一個(gè)“無(wú)底洞”型),這個(gè)時(shí)候,棧頂就變成了定死的,就可以先壓入元素,然后再修改指針。因?yàn)闂5资菬o(wú)限的,壓入一個(gè)元素,新的元素就取代先前的棧頂元素占據(jù)棧頂?shù)奈恢?,那么先前的指向棧頂元素的指針這個(gè)時(shí)候就該修改讓它指向這個(gè)新的棧頂元素了。
下面的就是對(duì)“無(wú)底洞“型堆棧的一種實(shí)現(xiàn)的描述:
壓棧(入棧) :將對(duì)象或者數(shù)據(jù)壓入棧中,更新棧頂指針,使其指向最后入棧的對(duì)象或數(shù)據(jù)。
彈棧(出棧) :返回棧頂指向的對(duì)象或數(shù)據(jù),并從棧中刪除該對(duì)象或數(shù)據(jù),更新棧頂。
話說(shuō)回來(lái),計(jì)算機(jī)內(nèi)部肯定選第一種模型,不會(huì)選第二種,因?yàn)榈诙N模型,每壓入一個(gè)新的元素,都需要把之前堆棧里的所有元素整體下移動(dòng)一個(gè)元素的位置,騰出棧頂元素的位置讓新的元素進(jìn)來(lái),這種平移可是一筆不小的開(kāi)銷啊! 但是 并不是說(shuō)“無(wú)底洞”模型就沒(méi)辦法實(shí)現(xiàn)了,其實(shí)它可以通 過(guò)第一種模型來(lái)模擬的,每需要壓入一個(gè)新的元素的時(shí)候,就先開(kāi)辟一個(gè)空間,數(shù)據(jù)存入這個(gè)空間,然后再修改棧頂元素指針使其指向這個(gè)新的棧頂元素。
這就意味著,如果使用的是鏈表的話,只要有足夠的空間可開(kāi)辟出來(lái)作為一個(gè)節(jié)點(diǎn),那么兩種堆棧模型都能實(shí)現(xiàn)(當(dāng)然“無(wú)底洞“型還是如我上面說(shuō)的那樣用第一種模擬出來(lái)的,否則平移的工作量相當(dāng)可觀),如果用數(shù)組,由于數(shù)組在內(nèi)存中是連續(xù)分配出來(lái)的空間,用第一種模型更自然一些。
評(píng)論
查看更多