資源簡(jiǎn)介

(共55張PPT)
第3章 棧與隊(duì)列
棧的概念
棧的順序存儲(chǔ)
棧的鏈?zhǔn)酱鎯?chǔ)
隊(duì)列的概念
隊(duì)列的順序存儲(chǔ)
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)
棧的概念
棧的鏈?zhǔn)酱鎯?chǔ)
3.2
3.3
3.1
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
隊(duì)列的概念
3.4
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
隊(duì)列的順序存儲(chǔ)
3.5
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
隊(duì)列的鏈?zhǔn)酱鎯?chǔ)
3.6
點(diǎn)擊查看本小節(jié)知識(shí)架構(gòu)
棧的順序存儲(chǔ)
學(xué)習(xí)目標(biāo)
了解
掌握
掌握
掌握
了解棧與隊(duì)列的基本概念
1
掌握順序隊(duì)列的定義與代碼編寫(xiě)方法
4
2
掌握順序棧的定義與代碼編寫(xiě)方法
3
掌握鏈?zhǔn)綏５亩x與代碼編寫(xiě)方法
本章將主要介紹兩種典型的數(shù)據(jù)結(jié)構(gòu)——棧與隊(duì)列，棧與隊(duì)列都是基于線性表的數(shù)據(jù)結(jié)構(gòu)類型，其數(shù)據(jù)元素之間仍然滿足線性結(jié)構(gòu)。棧與隊(duì)列可以通過(guò)不同的物理結(jié)構(gòu)實(shí)現(xiàn)，如順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)。因此，棧又可以分為順序棧與鏈?zhǔn)綏＃?duì)列同樣可以分為順序隊(duì)列與鏈?zhǔn)疥?duì)列。本章將從棧與隊(duì)列的數(shù)據(jù)操作分析入手，詳細(xì)介紹代碼的編寫(xiě)方法。
3.1 棧的概念
3.1.1
棧的定義
返回目錄
3.1.2
棧的運(yùn)算
3.1.1 棧的定義
棧是一種運(yùn)算受限制的線性表，其只允許在表的一端進(jìn)行插入和刪除操作，俗稱堆棧。允許進(jìn)行操作的一端稱為“棧頂”，另一個(gè)固定端稱為“棧底”，當(dāng)棧中沒(méi)有元素時(shí)稱為“空棧”。
例如，棧(a 1 ,a 2 ,a 3 ,… ,a i )，其中 a 1為棧底結(jié)點(diǎn)，而a i 為棧頂結(jié)點(diǎn)。如果需要插入或刪除結(jié)點(diǎn)，只能從棧頂操作，插入結(jié)點(diǎn)稱為入棧，刪除結(jié)點(diǎn)稱為出棧，如圖所示。
由圖可知，棧中的數(shù)據(jù)在入棧和出棧時(shí)，遵循后進(jìn)先出的原則。這類似于手槍的子彈夾，最先裝入的子彈，最后出膛擊發(fā)。
3.1.2 棧的運(yùn)算
棧的運(yùn)算指的是對(duì)棧中的數(shù)據(jù)進(jìn)行操作，其具體實(shí)現(xiàn)與棧的物理結(jié)構(gòu)有關(guān)。棧常見(jiàn)的幾種運(yùn)算如下。
（1）判棧空：判斷棧是否為空。
（2）取棧頂：獲取棧頂結(jié)點(diǎn)的數(shù)據(jù)。
（3）入棧：將結(jié)點(diǎn)壓入棧的頂部。
（4）出棧：移出棧頂結(jié)點(diǎn)。
3.2 棧的順序存儲(chǔ)
3.2.1
順序棧的定義
返回目錄
3.2.2
順序棧的創(chuàng)建
3.2.3
入棧
3.2.4
出棧
3.2 棧的順序存儲(chǔ)
3.2.5
顯示結(jié)點(diǎn)數(shù)據(jù)
返回目錄
3.2.6
整體測(cè)試
3.2 棧的順序存儲(chǔ)
棧采用順序存儲(chǔ)稱為順序棧，順序棧是順序表的一種，是運(yùn)算受限制的順序表，具有與順序表相同的存儲(chǔ)結(jié)構(gòu)。
3.2.1 順序棧的定義
在C語(yǔ)言程序中，棧用數(shù)組表示，配合數(shù)組下標(biāo)表示的棧頂指針完成各種操作。代碼如下所示。
由以上代碼可知，結(jié)構(gòu)體中的第1個(gè)成員為一維數(shù)組，使用該數(shù)組表示棧，數(shù)組中保存的元素為棧的數(shù)據(jù)結(jié)點(diǎn)；結(jié)構(gòu)體中的第2個(gè)成員top表示棧頂指針，其初始值為0，表示棧中沒(méi)有數(shù)據(jù)結(jié)點(diǎn)，每壓入一個(gè)數(shù)據(jù)結(jié)點(diǎn)，top的值加1。如圖所示。
3.2.2 順序棧的創(chuàng)建
在對(duì)棧中的數(shù)據(jù)結(jié)點(diǎn)進(jìn)行操作之前，需要先創(chuàng)建一個(gè)空棧。假設(shè)一個(gè)結(jié)點(diǎn)所占的空間大小為L(zhǎng)，棧中的結(jié)點(diǎn)有n個(gè)，則棧所占的空間為n*L。但實(shí)際的情況是棧中的結(jié)點(diǎn)數(shù)是不確定的，其占有的內(nèi)存空間也是不確定的，因此需要先分配max*L個(gè)連續(xù)的內(nèi)存空間，使其能存儲(chǔ)max個(gè)結(jié)點(diǎn)。
通過(guò)代碼實(shí)現(xiàn)創(chuàng)建空棧，示例代碼參考教材3.2.2節(jié)。
如例所示，創(chuàng)建空棧只需為結(jié)構(gòu)體在內(nèi)存上申請(qǐng)一塊連續(xù)的空間，并將表示棧頂指針的top置為0，表示棧中沒(méi)有任何結(jié)點(diǎn)。
3.2.3 入棧
3.2.2節(jié)已經(jīng)完成了創(chuàng)建空棧的操作，接下來(lái)將通過(guò)代碼展示如何向棧中壓入數(shù)據(jù)結(jié)點(diǎn)。在壓入數(shù)據(jù)結(jié)點(diǎn)之前，需要判斷棧是否為滿，如果為滿則不允許入棧，否則會(huì)造成數(shù)據(jù)在內(nèi)存上越界。
壓入數(shù)據(jù)結(jié)點(diǎn)需要先判斷棧是否為滿，代碼如下所示。（變量定義與例3-1一致）。
棧未滿即可進(jìn)行入棧操作，代碼如下所示。（變量定義與例3-1一致）。
3.2.3 入棧
由以上述代碼可知，入棧只需要將新壓入的數(shù)據(jù)保存至表示順序棧的數(shù)組中即可。
3.2.4 出棧
在移出數(shù)據(jù)結(jié)點(diǎn)之前，需要判斷棧是否為空，如果為空，表示沒(méi)有數(shù)據(jù)可以移出。代碼如下所示。（變量定義與例3-1一致）。
棧非空即可執(zhí)行出棧操作，代碼如下所示。（變量定義與例3-1一致）。
3.2.4 出棧
由上述代碼可知，出棧只需要將棧頂top值減1即可。
執(zhí)行入棧或出棧時(shí)，都可以通過(guò)當(dāng)前top值及時(shí)獲取棧頂結(jié)點(diǎn)的數(shù)據(jù)，代碼如下所示。（變量定義與例3-1一致）。
3.2.5 顯示結(jié)點(diǎn)數(shù)據(jù)
顯示棧中所有結(jié)點(diǎn)的數(shù)據(jù)，代碼實(shí)現(xiàn)如下所示。（變量定義與例3-1一致）。
3.2.6 整體測(cè)試
將3.2.3節(jié)、3.2.4節(jié)、3.2.5節(jié)的功能代碼與例3-1結(jié)合，測(cè)試數(shù)據(jù)操作是否成功，具體示例點(diǎn)參考教材3.2.6節(jié)。
例中，主函數(shù)主要用于測(cè)試子函數(shù)是否正確。首先執(zhí)行入棧操作，并通過(guò)顯示數(shù)據(jù)判斷入棧是否成功；然后執(zhí)行出棧操作并顯示出棧數(shù)據(jù)。輸出結(jié)果如下所示。
由輸出結(jié)果可以看出，數(shù)據(jù)入棧成功，數(shù)據(jù)出棧成功。
3.3 棧的鏈?zhǔn)酱鎯?chǔ)
3.3.1
鏈?zhǔn)綏５亩x
返回目錄
3.3.2
鏈?zhǔn)綏５膭?chuàng)建
3.3.3
入棧
3.3.4
出棧
3.3 棧的鏈?zhǔn)酱鎯?chǔ)
3.3.5
顯示結(jié)點(diǎn)數(shù)據(jù)
返回目錄
3.3.6
整體測(cè)試
3.3 棧的鏈?zhǔn)酱鎯?chǔ)
棧采用鏈?zhǔn)酱鎯?chǔ)稱為鏈?zhǔn)綏＃準(zhǔn)綏Ｊ菃捂湵淼囊环N，是運(yùn)算受限制的單鏈表，具有與單鏈表相同的存儲(chǔ)結(jié)構(gòu)。
3.3.1 鏈?zhǔn)綏５亩x
鏈?zhǔn)綏Ｗ鳛閱捂湵淼囊环N，其插入操作與刪除操作均在鏈表頭部進(jìn)行，鏈表尾部就是棧底，頭指針就是棧頂指針，如圖所示。
由圖可知，鏈?zhǔn)綏Ｖ械慕Y(jié)點(diǎn)結(jié)構(gòu)與單鏈表一致，代碼如下所示。
3.3.2 鏈?zhǔn)綏５膭?chuàng)建
在對(duì)鏈?zhǔn)綏Ｖ械臄?shù)據(jù)進(jìn)行操作之前，需要先創(chuàng)建一個(gè)空的鏈?zhǔn)綏！Ｍㄟ^(guò)代碼實(shí)現(xiàn)創(chuàng)建一個(gè)空的鏈?zhǔn)綏＃缋尽?br/>3.3.2 鏈?zhǔn)綏５膭?chuàng)建
由以上述代碼可知，創(chuàng)建空棧與創(chuàng)建單鏈表一致，都是為頭結(jié)點(diǎn)申請(qǐng)內(nèi)存空間。
3.3.3 入棧
3.3.2節(jié)已經(jīng)完成了創(chuàng)建空棧的操作，接下來(lái)將通過(guò)代碼展示如何向棧中壓入數(shù)據(jù)結(jié)點(diǎn)。鏈?zhǔn)綏２煌陧樞驐＃恍枰O(shè)定棧的大小，因此也不需要判斷棧是否為滿。
入棧采用單鏈表操作中的頭插法，最先插入的數(shù)據(jù)結(jié)點(diǎn)成為棧底。代碼如下所示。（變量定義與例3-3一致）。
3.3.4 出棧
在移出數(shù)據(jù)結(jié)點(diǎn)之前，需要判斷棧是否為空，如果為空，則沒(méi)有數(shù)據(jù)可以移出。代碼如下所示。（變量定義與例3-3一致）。
棧非空即可執(zhí)行出棧操作，出棧采用單鏈表操作中的頭刪法，最后刪除的數(shù)據(jù)結(jié)點(diǎn)為棧底。代碼如下所示。（變量定義與例3-3一致）。
3.3.5 顯示結(jié)點(diǎn)數(shù)據(jù)
顯示棧中所有的結(jié)點(diǎn)數(shù)據(jù)，代碼如下所示。（變量定義與例3-3一致）。
3.3.6 整體測(cè)試
將3.3.3節(jié)、3.3.4節(jié)、3.3.5節(jié)的功能代碼與例3-3結(jié)合，測(cè)試數(shù)據(jù)操作是否成功，示例代碼參考教材3.3.6節(jié)。
例中，主函數(shù)主要用于測(cè)試子函數(shù)是否正確。首先執(zhí)行入棧操作，并通過(guò)顯示數(shù)據(jù)判斷入棧是否成功；然后執(zhí)行出棧操作并顯示出棧數(shù)據(jù)。輸出結(jié)果如下所示。
由輸出結(jié)果可以看出，數(shù)據(jù)入棧成功，數(shù)據(jù)出棧成功。
3.4 隊(duì)列的概念
3.4.1
隊(duì)列的定義
返回目錄
3.4.2
隊(duì)列的運(yùn)算
3.4.1 隊(duì)列的定義
隊(duì)列同樣是一種運(yùn)算受限制的線性表，是只能在兩端進(jìn)行插入和刪除操作的線性表。允許進(jìn)行插入操作的一端稱為“隊(duì)尾”，允許進(jìn)行刪除操作的一端稱為“隊(duì)頭”，當(dāng)隊(duì)列中沒(méi)有元素時(shí)，隊(duì)列稱為“空隊(duì)”。
例如，隊(duì)列(a 1 ,a 2 ,a 3 ,… ,a i )，其中 a 1 為隊(duì)頭，而a i 為隊(duì)尾。如果需要?jiǎng)h除結(jié)點(diǎn)，只能從隊(duì)頭操作；如果需要插入結(jié)點(diǎn)，只能從隊(duì)尾操作。如圖所示。
由圖可知，隊(duì)列中的數(shù)據(jù)在進(jìn)行入隊(duì)和出隊(duì)時(shí)，遵循先進(jìn)先出的原則。這類似于生活中排隊(duì)辦理業(yè)務(wù)，站在隊(duì)頭的人最先辦理業(yè)務(wù)。
3.4.2 隊(duì)列的運(yùn)算
隊(duì)列的運(yùn)算指的是對(duì)隊(duì)列中的數(shù)據(jù)進(jìn)行操作，其具體實(shí)現(xiàn)與隊(duì)列的物理結(jié)構(gòu)有關(guān)。隊(duì)列常見(jiàn)的幾種運(yùn)算如下。
（1）判隊(duì)空：判斷隊(duì)列是否為空。
（2）取頭結(jié)點(diǎn)：獲取隊(duì)列頭結(jié)點(diǎn)的數(shù)據(jù)。
（3）入隊(duì)：將結(jié)點(diǎn)插入隊(duì)列的尾部。
（4）出隊(duì)：刪除隊(duì)列頭結(jié)點(diǎn)。
3.5 隊(duì)列的順序存儲(chǔ)
3.5.1
順序隊(duì)列的定義
返回目錄
3.5.2
順序隊(duì)列的創(chuàng)建
3.5.3
入隊(duì)
3.5.4
出隊(duì)
3.5.5
整體測(cè)試
3.5 隊(duì)列的順序存儲(chǔ)
隊(duì)列采用順序存儲(chǔ)稱為順序隊(duì)列，順序隊(duì)列是順序表的一種，是運(yùn)算受限制的順序表，具有與順序表相同的存儲(chǔ)結(jié)構(gòu)。
3.5.1 順序隊(duì)列的定義
在C語(yǔ)言程序中，順序隊(duì)列使用一維數(shù)組表示。隊(duì)列的操作只能在隊(duì)頭與隊(duì)尾進(jìn)行，且不移動(dòng)隊(duì)列中的結(jié)點(diǎn)。代碼如下所示。
3.5.1 順序隊(duì)列的定義
由以上代碼可知，結(jié)構(gòu)體中的第1個(gè)成員為一維數(shù)組，使用該數(shù)組表示隊(duì)列，數(shù)組中保存的元素為隊(duì)列的數(shù)據(jù)結(jié)點(diǎn)；結(jié)構(gòu)體中的第2個(gè)成員front表示當(dāng)前隊(duì)頭結(jié)點(diǎn)的數(shù)組下標(biāo)，第3個(gè)成員rear表示當(dāng)前隊(duì)尾結(jié)點(diǎn)的數(shù)組下標(biāo)。如圖所示。
3.5.2 順序隊(duì)列的創(chuàng)建
在對(duì)隊(duì)列中的數(shù)據(jù)結(jié)點(diǎn)進(jìn)行操作之前，需要先創(chuàng)建一個(gè)空隊(duì)列。假設(shè)一個(gè)結(jié)點(diǎn)所占的空間大小為L(zhǎng)，隊(duì)列中的結(jié)點(diǎn)有n個(gè)，則隊(duì)列所占的空間為n*L。但實(shí)際的情況是隊(duì)列中的結(jié)點(diǎn)數(shù)是不確定的，其占有的空間大小也是不確定的，因此需要先分配max*L個(gè)連續(xù)的內(nèi)存空間，使其能存儲(chǔ)max個(gè)結(jié)點(diǎn)。
通過(guò)代碼實(shí)現(xiàn)創(chuàng)建空隊(duì)列，示例代碼參考教材3.5.2節(jié)。
由例可知，創(chuàng)建空順序隊(duì)列只需為結(jié)構(gòu)體在內(nèi)存上申請(qǐng)一塊連續(xù)的空間，并將表示隊(duì)頭和隊(duì)尾結(jié)點(diǎn)的數(shù)組下標(biāo)置為0，表示順序隊(duì)列中沒(méi)有任何結(jié)點(diǎn)。
3.5.3 入隊(duì)
3.5.2節(jié)已經(jīng)完成了創(chuàng)建空順序隊(duì)列的操作，接下來(lái)將通過(guò)代碼展示如何向隊(duì)列中添加數(shù)據(jù)結(jié)點(diǎn)。在添加數(shù)據(jù)結(jié)點(diǎn)之前，需要判斷順序隊(duì)列是否為滿，如果為滿則不允許加入添加結(jié)點(diǎn)，否則會(huì)造成數(shù)據(jù)在內(nèi)存上越界。
順序隊(duì)列的數(shù)據(jù)結(jié)點(diǎn)處理比較特殊，如圖所示。
3.5.3 入隊(duì)
圖中，初始時(shí)順序隊(duì)列為空，front與rear初始值為0；當(dāng)順序隊(duì)列為滿時(shí)，front值不變，rear值為6；刪除兩個(gè)結(jié)點(diǎn)后，front值為2，rear值不變。
由圖可知，刪除前兩個(gè)結(jié)點(diǎn)后，順序隊(duì)列未滿，可以選擇繼續(xù)添加數(shù)據(jù)結(jié)點(diǎn)。添加數(shù)據(jù)結(jié)點(diǎn)意味著rear值繼續(xù)增大，但此時(shí)rear值已經(jīng)為最大值，無(wú)法繼續(xù)增大，這導(dǎo)致存儲(chǔ)前兩個(gè)結(jié)點(diǎn)的空間將無(wú)法繼續(xù)使用，這種情況稱為“溢出”。
針對(duì)上述情況，為了滿足隊(duì)列未滿即可插入以及隊(duì)列未空即可刪除的需求，需要將順序隊(duì)列抽象為一個(gè)循環(huán)的表，這種意義下的順序隊(duì)列稱為循環(huán)隊(duì)列，如圖所示。
3.5.3 入隊(duì)
為了實(shí)現(xiàn)循環(huán)并且能夠判斷隊(duì)列的狀態(tài)是空或滿，隊(duì)列中必須預(yù)留一個(gè)結(jié)點(diǎn)的空間，即這一個(gè)結(jié)點(diǎn)的空間不用來(lái)存儲(chǔ)數(shù)據(jù)。圖所示的循環(huán)隊(duì)列只是一種邏輯上的抽象，為了達(dá)到這一效果，只需要讓front與rear值執(zhí)行循環(huán)。簡(jiǎn)單地說(shuō)，即front與rear的值增加到最大后，可以從0開(kāi)始繼續(xù)增加。
將上述思想應(yīng)用到實(shí)際的隊(duì)列，如圖所示。
3.5.3 入隊(duì)
假設(shè)隊(duì)列最多可存儲(chǔ)的結(jié)點(diǎn)數(shù)N為4（數(shù)組大小為5）。如圖（a）所示，初始隊(duì)列為空時(shí)，front、rear初始值都為0。如圖（b）所示，1個(gè)結(jié)點(diǎn)入隊(duì)后，front值不變，rear值加1。如圖（c）所示，4個(gè)結(jié)點(diǎn)入隊(duì)后，隊(duì)列狀態(tài)為滿，front值不變，rear值加4，最后一個(gè)結(jié)點(diǎn)空間不存儲(chǔ)數(shù)據(jù)。如圖（d），2個(gè)結(jié)點(diǎn)出隊(duì)后，front值加2，rear值不變。如圖（e）所示，再次插入2個(gè)結(jié)點(diǎn)后，front值不變，rear值加2后變?yōu)?。
綜上所述，在rear值加到最大值N后，再添加結(jié)點(diǎn)，rear值會(huì)重新變?yōu)?。同理，在front值加到最大值N后，再刪除結(jié)點(diǎn)，front值會(huì)重新變?yōu)?。
從圖中可以得到的規(guī)律是，rear值在任何時(shí)刻都等于留空結(jié)點(diǎn)的數(shù)組下標(biāo)值。
添加數(shù)據(jù)結(jié)點(diǎn)需要先判斷隊(duì)列是否為滿，代碼如下所示。（變量定義與例3-5一致）。
3.5.3 入隊(duì)
圖（c）與圖（e）所示的隊(duì)列都為滿，且front值等于rear值加1。以上代碼中rear值加1對(duì)N取余，使得rear值可以無(wú)限次增加，實(shí)現(xiàn)循環(huán)。
隊(duì)列未滿即可進(jìn)行入隊(duì)操作，代碼如下所示。（變量定義與例3-5一致）。
3.5.4 出隊(duì)
在執(zhí)行出隊(duì)之前，需要判斷順序隊(duì)列是否為空，如果為空，沒(méi)有數(shù)據(jù)可以移出。代碼如下所示。（變量定義與例3-5一致）。
由圖（a）可知，當(dāng)front值與rear值相等時(shí)，順序隊(duì)列為空。除此之外，順序隊(duì)列在經(jīng)歷多次入隊(duì)、出隊(duì)（front、rear值多次增加、取余）后，也可能會(huì)出現(xiàn)兩個(gè)值相等情況，如圖所示。
3.5.4 出隊(duì)
隊(duì)列非空即可執(zhí)行出隊(duì)操作，代碼如下所示。（變量定義與例3-5一致）。
3.5.5 整體測(cè)試
將3.5.3、3.5.4節(jié)的功能代碼與例3-5結(jié)合，測(cè)試數(shù)據(jù)操作是否成功，示例代碼參考教材3.5.5節(jié)。
例中，主函數(shù)主要用于測(cè)試子函數(shù)是否正確。首先執(zhí)行入隊(duì)操作，然后執(zhí)行出隊(duì)操作，并通過(guò)顯示出隊(duì)數(shù)據(jù)，判斷順序隊(duì)列是否遵循先進(jìn)先出的規(guī)則。輸出結(jié)果如下所示。
由輸出結(jié)果可知，數(shù)據(jù)入隊(duì)成功，出隊(duì)時(shí)，最早入隊(duì)的數(shù)據(jù)先出隊(duì)。
3.6 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)
3.6.1
鏈?zhǔn)疥?duì)列的定義
返回目錄
3.6.2
鏈?zhǔn)疥?duì)列的創(chuàng)建
3.6.3
入隊(duì)
3.6.4
出隊(duì)
3.6.5
整體測(cè)試
3.6 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)
隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)稱為鏈?zhǔn)疥?duì)列，鏈?zhǔn)疥?duì)列是單鏈表的一種，是運(yùn)算受限制的單鏈表，具有與單鏈表相同的存儲(chǔ)結(jié)構(gòu)。
3.6.1 鏈?zhǔn)疥?duì)列的定義
鏈?zhǔn)疥?duì)列作為單鏈表的一種，其插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)頭進(jìn)行。通過(guò)指向隊(duì)列頭部的指針與指向隊(duì)列尾部的指針控制隊(duì)列的操作，如圖所示。
3.6.1 鏈?zhǔn)疥?duì)列的定義
由圖可知，front指針與rear指針用來(lái)完成隊(duì)列的數(shù)據(jù)操作，代碼定義如下所示。
以上代碼中，第一個(gè)封裝結(jié)構(gòu)體表示鏈?zhǔn)疥?duì)列中的數(shù)據(jù)結(jié)點(diǎn)，第二個(gè)封裝結(jié)構(gòu)體存放指向鏈?zhǔn)疥?duì)列頭尾結(jié)點(diǎn)的指針。
3.6.2 鏈?zhǔn)疥?duì)列的創(chuàng)建
在對(duì)鏈?zhǔn)疥?duì)列中的數(shù)據(jù)進(jìn)行操作之前，需要先創(chuàng)建一個(gè)空的鏈?zhǔn)疥?duì)列。通過(guò)代碼實(shí)現(xiàn)創(chuàng)建一個(gè)空的鏈?zhǔn)疥?duì)列，示例代碼參考教材3.6.2節(jié)。
3.6.3 入隊(duì)
3.6.2節(jié)已經(jīng)完成了創(chuàng)建空鏈隊(duì)列的操作，接下來(lái)將通過(guò)代碼展示如何向鏈?zhǔn)疥?duì)列中加入數(shù)據(jù)結(jié)點(diǎn)。鏈?zhǔn)疥?duì)列不同于順序隊(duì)列，不需要設(shè)定隊(duì)列的大小，因此也不需要判斷隊(duì)列是否為滿。
入隊(duì)采用單鏈表操作中的尾插法，代碼如下所示。（變量定義與例3-7一致）。
3.6.4 出隊(duì)
在出隊(duì)之前，需要判斷隊(duì)列是否為空，如果為空，沒(méi)有數(shù)據(jù)可以移出。代碼如下所示。（變量定義與例3-7一致）。
3.6.4 出隊(duì)
隊(duì)列非空即可執(zhí)行出隊(duì)操作，出隊(duì)采用單鏈表操作中的頭刪法。代碼如下所示。（變量定義與例3-7一致）。
3.6.5 整體測(cè)試隊(duì)
將3.6.3節(jié)和3.6.4節(jié)的功能代碼與例3-7結(jié)合，測(cè)試數(shù)據(jù)操作是否成功，示例代碼參考教材3.6.5節(jié)。
例中，主函數(shù)主要用于測(cè)試子函數(shù)是否正確。首先執(zhí)行入隊(duì)操作；然后執(zhí)行出隊(duì)操作，并通過(guò)顯示出隊(duì)數(shù)據(jù)，判斷鏈?zhǔn)疥?duì)列是否遵循先進(jìn)先出的規(guī)則。輸出結(jié)果如下所示。
由輸出結(jié)果可知，數(shù)據(jù)入隊(duì)成功，出隊(duì)時(shí)，最早入隊(duì)的數(shù)據(jù)先出隊(duì)。
本章小結(jié)
本章主要介紹了兩種特殊的線性表結(jié)構(gòu)——棧與隊(duì)列，分別討論了二者在順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)下數(shù)據(jù)結(jié)點(diǎn)的基本操作。棧與隊(duì)列的數(shù)據(jù)操作類似于順序表和單鏈表。望讀者能在理解操作原理的前提下熟練編程操作，為后續(xù)結(jié)合算法思想解決實(shí)際問(wèn)題奠定基礎(chǔ)。

展開(kāi)更多......

收起↑