棧和隊(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所示藏姐。
棧中元素按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)闂Ｔ谑褂脮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就是鏈表的頭指針。圖１-２是棧的鏈?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)氢惋，如圖１-３所示洞翩。
