棧和隊(duì)列是兩種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu),它們都來自線性表數(shù)據(jù)結(jié)構(gòu)纽窟,都是“操作受限”的線性表填具。
棧
棧(Stack):是限制在表的一端進(jìn)行插入和刪除操作的線性表。又稱為后進(jìn)先出LIFO (Last In First Out)或先進(jìn)后出FILO (First In Last Out)線性表艰额。
棧頂(Top):允許進(jìn)行插入澄港、刪除操作的一端,又稱為表尾柄沮。用棧頂指針(top)來指示棧頂元素回梧。
棧底(Bottom):是固定端,又稱為表頭祖搓。
空棧:當(dāng)表中沒有元素時(shí)稱為空棧狱意。
設(shè)棧S=(a1,a2拯欧,…an)详囤,則a1稱為棧底元素,an為棧頂元素镐作,如圖1-1所示藏姐。
棧中元素按a1,a2该贾,…an的次序進(jìn)棧羔杨,退棧的第一個(gè)元素應(yīng)為棧頂元素。即棧的修改是按后進(jìn)先出的原則進(jìn)行的杨蛋。
棧的順序存儲(chǔ)表示
棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧兜材,和線性表相類似,用一維數(shù)組來存儲(chǔ)棧六荒。根據(jù)數(shù)組是否可以根據(jù)需要增大护姆,又可分為靜態(tài)順序棧和動(dòng)態(tài)順序棧。
棧的動(dòng)態(tài)順序存儲(chǔ)表示
采用動(dòng)態(tài)一維數(shù)組來存儲(chǔ)棧掏击。所謂動(dòng)態(tài)卵皂,指的是棧的大小可以根據(jù)需要增加。
- 用bottom表示棧底指針砚亭,棧底固定不變的灯变;棧頂則隨著進(jìn)棧和退棧操作而變化殴玛。用top(稱為棧頂指針)指示當(dāng)前棧頂位置。
- 用top=bottom作為椞砘觯空的標(biāo)記滚粟,每次top指向棧頂數(shù)組中的下一個(gè)存儲(chǔ)位置。
- 結(jié)點(diǎn)進(jìn)棧:首先將數(shù)據(jù)元素保存到棧頂(top所指的當(dāng)前位置)刃泌,然后執(zhí)行top加1凡壤,使top指向棧頂?shù)南乱粋€(gè)存儲(chǔ)位置;
棧的靜態(tài)順序存儲(chǔ)表示
采用靜態(tài)一維數(shù)組來存儲(chǔ)棧。
- 棧底固定不變的耙替;棧頂則隨著進(jìn)棧和退棧操作而變化亚侠,用一個(gè)整型變量top(稱為棧頂指針)來指示當(dāng)前棧頂位置。
- 用top=0表示椝咨龋空的初始狀態(tài)硝烂,每次top指向棧頂在數(shù)組中的存儲(chǔ)位置。
- 結(jié)點(diǎn)進(jìn)棧:首先執(zhí)行top加1铜幽,使top指向新的棧頂位置滞谢,然后將數(shù)據(jù)元素保存到棧頂(top所指的當(dāng)前位置)。
當(dāng)棧滿時(shí)做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出除抛,簡(jiǎn)稱“上溢”狮杨。上溢是一種出錯(cuò)狀態(tài),應(yīng)設(shè)法避免到忽。
當(dāng)椇探矗空時(shí)做退棧運(yùn)算也將產(chǎn)生溢出,簡(jiǎn)稱“下溢”绘趋。下溢則可能是正巢眨現(xiàn)象,因?yàn)闂T谑褂脮r(shí)陷遮,其初態(tài)或終態(tài)都是空棧滓走,所以下溢常用來作為控制轉(zhuǎn)移的條件。
棧的鏈?zhǔn)酱鎯?chǔ)表示
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧帽馋,是運(yùn)算受限的單鏈表搅方。其插入和刪除操作只能在表頭位置上進(jìn)行。因此绽族,鏈棧沒有必要像單鏈表那樣附加頭結(jié)點(diǎn)姨涡,棧頂指針top就是鏈表的頭指針。圖1-2是棧的鏈?zhǔn)酱鎯?chǔ)表示形式吧慢。
隊(duì)列
隊(duì)列(Queue):也是運(yùn)算受限的線性表涛漂。是一種先進(jìn)先出(First In First Out ,簡(jiǎn)稱FIFO)的線性表。只允許在表的一端進(jìn)行插入匈仗,而在另一端進(jìn)行刪除瓢剿。
隊(duì)首(front) :允許進(jìn)行刪除的一端稱為隊(duì)首。
隊(duì)尾(rear) :允許進(jìn)行插入的一端稱為隊(duì)尾悠轩。
例如:排隊(duì)購(gòu)物间狂。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列的成員總是先離開隊(duì)列火架。
隊(duì)列的順序表示
利用一組連續(xù)的存儲(chǔ)單元(一維數(shù)組) 依次存放從隊(duì)首到隊(duì)尾的各個(gè)元素鉴象,稱為順序隊(duì)列。
對(duì)于隊(duì)列何鸡,和順序棧相類似炼列,也有動(dòng)態(tài)和靜態(tài)之分
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列,它是限制僅在表頭進(jìn)行刪除操作和表尾進(jìn)行插入操作的單鏈表音比。
需要兩類不同的結(jié)點(diǎn):數(shù)據(jù)元素結(jié)點(diǎn),隊(duì)列的隊(duì)首指針和隊(duì)尾指針的結(jié)點(diǎn)氢惋,如圖1-3所示洞翩。