合工大數(shù)據(jù)結(jié)構(gòu)03-隊(duì)列

1、1數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)（第三章第三章 隊(duì)隊(duì) 列列 ） Data Structures張晶張晶計(jì)算機(jī)與信息學(xué)院計(jì)算機(jī)與信息學(xué)院 2022-6-272022-6-272第三章第三章 隊(duì)隊(duì) 列列 第三章 隊(duì)列（queue） 3.1 隊(duì)列的定義和運(yùn)算 3.2 順序隊(duì)列與循環(huán)隊(duì)列 3.3 隊(duì)列的應(yīng)用 3第三章第三章 隊(duì)隊(duì) 列列隊(duì)列是軟件設(shè)計(jì)中最基本的數(shù)據(jù)結(jié)構(gòu)之一，對(duì)隊(duì)列結(jié)構(gòu)的理解，同樣需要參照前面所介紹的數(shù)據(jù)結(jié)構(gòu)的組成部分。邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)分析分析 運(yùn)算實(shí)現(xiàn)（算法）運(yùn)算實(shí)現(xiàn)（算法） 運(yùn)算定義運(yùn)算定義 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的組成數(shù)據(jù)結(jié)構(gòu)的組成43.1 隊(duì)列的定義和運(yùn)算3.1.1隊(duì)列的定義隊(duì)列的定義n

2、隊(duì)列是只能隊(duì)列是只能在一端插入在一端插入，另一端刪除另一端刪除元素的線性表。元素的線性表。 術(shù)語(yǔ)術(shù)語(yǔ)：隊(duì)頭隊(duì)頭, 隊(duì)尾，隊(duì)尾， 入隊(duì)入隊(duì), 出隊(duì)出隊(duì) 邏輯結(jié)構(gòu)和運(yùn)算邏輯結(jié)構(gòu)和運(yùn)算a1 a2 an 特性：先進(jìn)先出特性：先進(jìn)先出（FIFO：first in first out）a1a2anana2a1a1a2an隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾出隊(duì)出隊(duì)入隊(duì)入隊(duì)53.1 隊(duì)列的定義和運(yùn)算3.1.23.1.2隊(duì)列的運(yùn)算隊(duì)列的運(yùn)算o 1.1.隊(duì)列的基本運(yùn)算定義隊(duì)列的基本運(yùn)算定義對(duì)隊(duì)列的基本運(yùn)算有如下幾個(gè)：對(duì)隊(duì)列的基本運(yùn)算有如下幾個(gè)：(1)(1)初始化初始化 ：設(shè)置隊(duì)列為空。：設(shè)置隊(duì)列為空。 (2)(2)判斷隊(duì)列為空：判

3、斷隊(duì)列為空： 若為空，則返回若為空，則返回TRUETRUE，否則返回，否則返回FALSE. FALSE. (3)(3)判斷隊(duì)列為滿：判斷隊(duì)列為滿： 若為滿，則返回若為滿，則返回TRUETRUE，否則返回，否則返回FALSE. FALSE. (4)(4)取隊(duì)頭元素：取出隊(duì)頭元素。取隊(duì)頭元素：取出隊(duì)頭元素。 條件：隊(duì)列不空。條件：隊(duì)列不空。 否則，應(yīng)能明確給出標(biāo)識(shí)，以便程序的處理。否則，應(yīng)能明確給出標(biāo)識(shí)，以便程序的處理。(5)(5)入隊(duì)：將元素入隊(duì)，即放到隊(duì)列的尾部。入隊(duì)：將元素入隊(duì)，即放到隊(duì)列的尾部。 如果隊(duì)列滿，怎樣處理？如果隊(duì)列滿，怎樣處理？ (6)(6)出棧：刪除當(dāng)前隊(duì)頭的元素。出棧：刪除

4、當(dāng)前隊(duì)頭的元素。 如因?yàn)殛?duì)列空而不能進(jìn)行，如因?yàn)殛?duì)列空而不能進(jìn)行，應(yīng)怎樣處理？應(yīng)怎樣處理？ 運(yùn)算定義運(yùn)算定義63.1.2 隊(duì)列的運(yùn)算o 2.隊(duì)列的運(yùn)算的隊(duì)列的運(yùn)算的C+描述描述如何用如何用C+描述隊(duì)列的內(nèi)容和運(yùn)算？描述隊(duì)列的內(nèi)容和運(yùn)算？參照棧結(jié)構(gòu)的做法，即參照棧結(jié)構(gòu)的做法，即n 將隊(duì)列的有關(guān)將隊(duì)列的有關(guān)數(shù)據(jù)數(shù)據(jù)和和運(yùn)算運(yùn)算封裝在一起，封裝在一起，n 以以C+的的類類的形式來(lái)封裝描述。的形式來(lái)封裝描述。n 封裝的封裝的數(shù)據(jù)數(shù)據(jù)和和運(yùn)算運(yùn)算要便于被有關(guān)程序來(lái)要便于被有關(guān)程序來(lái)合理調(diào)用合理調(diào)用和和引用引用。o 因此，隊(duì)列的因此，隊(duì)列的C+描述的框架如下所示：描述的框架如下所示：class queue

5、 ;類的名稱類的名稱類的框架類的框架運(yùn)算描述部分運(yùn)算描述部分?jǐn)?shù)據(jù)描述部分?jǐn)?shù)據(jù)描述部分73.1.2 隊(duì)列的運(yùn)算o隊(duì)列的運(yùn)算的隊(duì)列的運(yùn)算的C+描述的細(xì)節(jié)，與棧的運(yùn)算的相對(duì)應(yīng)：描述的細(xì)節(jié)，與棧的運(yùn)算的相對(duì)應(yīng)：n初始化函數(shù)的描述初始化函數(shù)的描述隊(duì)列的隊(duì)列的C+類描述：類描述： class queue queue(); 隊(duì)列的數(shù)據(jù)成員隊(duì)列的數(shù)據(jù)成員 ;隊(duì)列的運(yùn)算隊(duì)列的運(yùn)算(1)(1)初始化初始化 ：設(shè)置隊(duì)列為空。：設(shè)置隊(duì)列為空。 (2)(2)判斷隊(duì)列為空：判斷隊(duì)列為空： 若為空，則返回若為空，則返回TRUETRUE，否則返回，否則返回FALSE. FALSE. (3)(3)判斷隊(duì)列為滿：判斷隊(duì)列為滿：

6、若為滿，則返回若為滿，則返回TRUETRUE，否則返回，否則返回FALSE. FALSE. (4)(4)取隊(duì)頭元素：取出隊(duì)頭元素。取隊(duì)頭元素：取出隊(duì)頭元素。 條件：隊(duì)列不空。條件：隊(duì)列不空。 否則，應(yīng)能明確給出標(biāo)識(shí)，以便程序的處理。否則，應(yīng)能明確給出標(biāo)識(shí)，以便程序的處理。(5)(5)入隊(duì)：將元素入隊(duì)，即放到隊(duì)列的尾部。入隊(duì)：將元素入隊(duì)，即放到隊(duì)列的尾部。 如果隊(duì)列滿，怎樣處理？如果隊(duì)列滿，怎樣處理？ (6)(6)出棧：刪除當(dāng)前隊(duì)頭的元素。出棧：刪除當(dāng)前隊(duì)頭的元素。 如因?yàn)殛?duì)列空而不能進(jìn)行，如因?yàn)殛?duì)列空而不能進(jìn)行，應(yīng)怎樣處理？應(yīng)怎樣處理？采用采用C+的的構(gòu)造函數(shù)構(gòu)造函數(shù)83.1.2 隊(duì)列的運(yùn)算o

7、 判斷函數(shù)的對(duì)應(yīng)判斷函數(shù)的對(duì)應(yīng)隊(duì)列的隊(duì)列的C+類描述：類描述： class queue queue(); 隊(duì)列的數(shù)據(jù)成員隊(duì)列的數(shù)據(jù)成員 ; 隊(duì)列的運(yùn)算隊(duì)列的運(yùn)算(1)(1)初始化初始化 ：設(shè)置隊(duì)列為空。：設(shè)置隊(duì)列為空。 (2)(2)判斷隊(duì)列為空：判斷隊(duì)列為空： 若為空，則返回若為空，則返回TRUETRUE，否則返回，否則返回FALSE. FALSE. (3)(3)判斷隊(duì)列為滿：判斷隊(duì)列為滿： 若為滿，則返回若為滿，則返回TRUETRUE，否則返回，否則返回FALSE. FALSE. (4)(4)取隊(duì)頭元素：取出隊(duì)頭元素。取隊(duì)頭元素：取出隊(duì)頭元素。 條件：隊(duì)列不空。條件：隊(duì)列不空。 否則，應(yīng)能明

8、確給出標(biāo)識(shí)，以便程序的處理。否則，應(yīng)能明確給出標(biāo)識(shí)，以便程序的處理。(5)(5)入隊(duì)：將元素入隊(duì)，即放到隊(duì)列的尾部。入隊(duì)：將元素入隊(duì)，即放到隊(duì)列的尾部。 如果隊(duì)列滿，怎樣處理？如果隊(duì)列滿，怎樣處理？ (6)(6)出棧：刪除當(dāng)前隊(duì)頭的元素。出棧：刪除當(dāng)前隊(duì)頭的元素。 如因?yàn)殛?duì)列空而不能進(jìn)行，應(yīng)怎樣處理？如因?yàn)殛?duì)列空而不能進(jìn)行，應(yīng)怎樣處理？判斷為空的函數(shù)判斷為空的函數(shù)判斷為滿的函數(shù)判斷為滿的函數(shù)const;const;Bool empty( )Bool full( )93.1.2 隊(duì)列的運(yùn)算o 其他幾個(gè)函數(shù)的對(duì)應(yīng)描述：與棧結(jié)構(gòu)類似，其他幾個(gè)函數(shù)的對(duì)應(yīng)描述：與棧結(jié)構(gòu)類似，n 幾個(gè)運(yùn)算的條件也可能有不

9、成立的情況，幾個(gè)運(yùn)算的條件也可能有不成立的情況， 因此，需要給與明確的反映。因此，需要給與明確的反映。n 設(shè)立運(yùn)算是否正常的類型設(shè)立運(yùn)算是否正常的類型error_code，o 正常時(shí)返回正常時(shí)返回success,o 否則返回錯(cuò)誤類型，如否則返回錯(cuò)誤類型，如overflow, underflow等。等。n 將這幾個(gè)函數(shù)的類型設(shè)置為將這幾個(gè)函數(shù)的類型設(shè)置為error_code；n 如果需要返回其他的值，可以作為參數(shù)來(lái)返回。如果需要返回其他的值，可以作為參數(shù)來(lái)返回。o 由上述討論可得到其他幾個(gè)函數(shù)的功能描述：由上述討論可得到其他幾個(gè)函數(shù)的功能描述：103.1.2 隊(duì)列的運(yùn)算（4)4)取隊(duì)頭元素取隊(duì)頭

10、元素的運(yùn)算功能描述：的運(yùn)算功能描述： 如果隊(duì)列不空，則取出隊(duì)頭元素到參數(shù)如果隊(duì)列不空，則取出隊(duì)頭元素到參數(shù)x x中，并返回中，并返回successsuccess。 否則，返回否則，返回underflowunderflow。 對(duì)應(yīng)的運(yùn)算函數(shù)為：對(duì)應(yīng)的運(yùn)算函數(shù)為： error_code get_front(elementtype &x) const;(5)(5)入隊(duì)入隊(duì)的運(yùn)算功能描述：的運(yùn)算功能描述： 如果隊(duì)列不滿，則將元素入隊(duì)，并返回如果隊(duì)列不滿，則將元素入隊(duì)，并返回successsuccess。 否則，返回否則，返回overflowoverflow。 對(duì)應(yīng)的運(yùn)算函數(shù)為：對(duì)應(yīng)的運(yùn)算函數(shù)為

11、： error_code append(const elementtype x);(6)(6)出隊(duì)出隊(duì)的運(yùn)算功能描述：的運(yùn)算功能描述： 如果隊(duì)列不空，刪除當(dāng)前隊(duì)頭的元素，并返回如果隊(duì)列不空，刪除當(dāng)前隊(duì)頭的元素，并返回successsuccess。 否則，返回否則，返回underflowunderflow。 對(duì)應(yīng)的運(yùn)算函數(shù)為：對(duì)應(yīng)的運(yùn)算函數(shù)為： error_code serve();113.1.2 隊(duì)列的運(yùn)算o由此得到隊(duì)列的類由此得到隊(duì)列的類queue的函數(shù)成員列表如下：的函數(shù)成員列表如下：class queue public: queue(); / 初始化初始化 Bool empty( ) c

12、onst; / 判斷空判斷空 Bool full( ) const; / 判斷滿判斷滿 error_code get_front(elementtype &x) const; / 取隊(duì)頭元素取隊(duì)頭元素 error_code append(const elementtype x); /入隊(duì)入隊(duì) error_code serve(); / 出隊(duì)出隊(duì) private： 隊(duì)列的數(shù)據(jù)成員隊(duì)列的數(shù)據(jù)成員;問(wèn)題：上述類的描述是否還需要補(bǔ)充什么？問(wèn)題：上述類的描述是否還需要補(bǔ)充什么？ 對(duì)類的函數(shù)成員和數(shù)據(jù)成員的接口控制。對(duì)類的函數(shù)成員和數(shù)據(jù)成員的接口控制。123.2 順序隊(duì)列與循環(huán)隊(duì)列3.2.1 存儲(chǔ)

13、結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)：o與順序棧的討論類似：與順序棧的討論類似：n假設(shè)有一個(gè)足夠大的存儲(chǔ)空間（數(shù)組）假設(shè)有一個(gè)足夠大的存儲(chǔ)空間（數(shù)組）data,用于存儲(chǔ)隊(duì)列的元用于存儲(chǔ)隊(duì)列的元素。素。n則將隊(duì)列中的元素依次存儲(chǔ)到數(shù)組中則將隊(duì)列中的元素依次存儲(chǔ)到數(shù)組中-順序存儲(chǔ)方式，順序存儲(chǔ)方式，n由此得到順序隊(duì)列由此得到順序隊(duì)列。n如下圖所示：如下圖所示：o其中，設(shè)置一個(gè)計(jì)數(shù)變量其中，設(shè)置一個(gè)計(jì)數(shù)變量count ，以記錄隊(duì)列中的元素個(gè)數(shù)。，以記錄隊(duì)列中的元素個(gè)數(shù)。o將數(shù)組將數(shù)組data和和count作為類作為類queue的數(shù)據(jù)成員。的數(shù)據(jù)成員。隊(duì)列的存儲(chǔ)結(jié)構(gòu)隊(duì)列的存儲(chǔ)結(jié)構(gòu)a1a2an01n-1maxlen-1dat

14、ancount順序隊(duì)列存儲(chǔ)結(jié)構(gòu)133.2 順序隊(duì)列與循環(huán)隊(duì)列o 由此而得到類由此而得到類queue的完整描述。的完整描述。o 封裝類封裝類: class queue public: queue(); Bool empty()const; Bool full() const; error_code get_front(elementtype &x)const; error_code append(const elementtype x); error_code serve(); private: int count; elementtype datamaxlen;由函數(shù)成員由函數(shù)成員描述

15、的運(yùn)算描述的運(yùn)算由數(shù)據(jù)成員描由數(shù)據(jù)成員描述的存儲(chǔ)結(jié)構(gòu)述的存儲(chǔ)結(jié)構(gòu)143.2 順序隊(duì)列與循環(huán)隊(duì)列3.2.2 關(guān)于存儲(chǔ)結(jié)構(gòu)的進(jìn)一步討論關(guān)于存儲(chǔ)結(jié)構(gòu)的進(jìn)一步討論 因此，插入和刪除操作的實(shí)現(xiàn)討論如下：因此，插入和刪除操作的實(shí)現(xiàn)討論如下：插入插入：插入元素：插入元素x就是要將就是要將x插入到表的末尾，因此，插入操作序列為：插入到表的末尾，因此，插入操作序列為： datacount = x; count +; 刪除刪除：刪除就是刪除表頭元素，因而需將其后面所有元素往前移動(dòng)一位。：刪除就是刪除表頭元素，因而需將其后面所有元素往前移動(dòng)一位。問(wèn)題問(wèn)題：每次刪除都需要移動(dòng)所有元素每次刪除都需要移動(dòng)所有元素， 若隊(duì)

16、列足夠大，花費(fèi)時(shí)間太大！若隊(duì)列足夠大，花費(fèi)時(shí)間太大！如何解決這一問(wèn)題？如何解決這一問(wèn)題？na1a2an01n-1maxlen-1datacount順序隊(duì)列結(jié)構(gòu)順序隊(duì)列結(jié)構(gòu) 下面通過(guò)對(duì)運(yùn)算實(shí)下面通過(guò)對(duì)運(yùn)算實(shí)現(xiàn)的討論來(lái)探討存儲(chǔ)結(jié)現(xiàn)的討論來(lái)探討存儲(chǔ)結(jié)構(gòu)的相關(guān)問(wèn)題：構(gòu)的相關(guān)問(wèn)題： 在這一結(jié)構(gòu)下，約在這一結(jié)構(gòu)下，約定定data0data0為隊(duì)頭元素，為隊(duì)頭元素，另一端為隊(duì)尾。另一端為隊(duì)尾。153.2 順序隊(duì)列與循環(huán)隊(duì)列改進(jìn)的方法改進(jìn)的方法： 設(shè)置頭尾指針設(shè)置頭尾指針front和和rear作為作為queue的數(shù)據(jù)成員，分別指示隊(duì)頭和隊(duì)尾。的數(shù)據(jù)成員，分別指示隊(duì)頭和隊(duì)尾。 并并約定約定： front指向隊(duì)頭

17、的前一個(gè)元素，指向隊(duì)頭的前一個(gè)元素，rear指向隊(duì)尾元素。如圖所示。指向隊(duì)尾元素。如圖所示。 在這種情況下，插入操作和與前面類似，但寫(xiě)法有所不同：在這種情況下，插入操作和與前面類似，但寫(xiě)法有所不同： rear+; datarear = x; count +; 但刪除操作要簡(jiǎn)單和省時(shí)間多了：但刪除操作要簡(jiǎn)單和省時(shí)間多了：front +; count-;問(wèn)題問(wèn)題- “溢出溢出”現(xiàn)象現(xiàn)象: 在連續(xù)插入元素后，會(huì)使在連續(xù)插入元素后，會(huì)使rear指示到數(shù)組的末尾。指示到數(shù)組的末尾。 而此時(shí)的情況是，數(shù)組的前面可能還有空的元素空間。而此時(shí)的情況是，數(shù)組的前面可能還有空的元素空間。01n-1a1a2anma

18、xlen-1datancount順序隊(duì)列結(jié)構(gòu)順序隊(duì)列結(jié)構(gòu)frontrear - “假溢出假溢出”163.2 順序隊(duì)列與循環(huán)隊(duì)列解決解決“假溢出假溢出”問(wèn)題的方法問(wèn)題的方法： 采用采用循環(huán)隊(duì)列循環(huán)隊(duì)列方式：將數(shù)組的頭尾看作是相鄰的元素，方式：將數(shù)組的頭尾看作是相鄰的元素，即將元素即將元素data0看作是看作是datamaxlen-1的下一個(gè)元素。如圖所示。的下一個(gè)元素。如圖所示。 因此，插入和刪除以及狀態(tài)檢測(cè)需要作相應(yīng)的調(diào)整：因此，插入和刪除以及狀態(tài)檢測(cè)需要作相應(yīng)的調(diào)整： 插入操作中移動(dòng)指示位置的計(jì)算插入操作中移動(dòng)指示位置的計(jì)算： if ( rear+1 = maxlen ) rear = 0;

19、 else rear+;或者：或者：rear = ( rear + 1 ) % maxlen ;或者：或者：rear = ( rear + 1 = maxlen ) ? 0 : rear + ;刪除操作刪除操作：front = ( front + 1 ) % maxlen ; 隊(duì)列空隊(duì)列空條件：條件： front = rear 隊(duì)列滿隊(duì)列滿條件：條件： front = rear 沖突沖突：判斷隊(duì)列滿和空的條件相同判斷隊(duì)列滿和空的條件相同！2maxlen-110ana1a3a2aifrontrear173.2 順序隊(duì)列與循環(huán)隊(duì)列解決的方法：解決的方法：（假設(shè)不用假設(shè)不用count） （1）增加標(biāo)

20、志：）增加標(biāo)志： 設(shè)置一個(gè)記錄最后的操作是插入還是刪除的標(biāo)志。設(shè)置一個(gè)記錄最后的操作是插入還是刪除的標(biāo)志。 當(dāng)出現(xiàn)首尾指針值相同時(shí)，當(dāng)出現(xiàn)首尾指針值相同時(shí)， 如果標(biāo)志是插入，則可斷定當(dāng)前隊(duì)列是如果標(biāo)志是插入，則可斷定當(dāng)前隊(duì)列是- 如果標(biāo)志是刪除，則可斷定當(dāng)前隊(duì)列是如果標(biāo)志是刪除，則可斷定當(dāng)前隊(duì)列是- （2）約定保留一個(gè)元素空間：）約定保留一個(gè)元素空間： 即將數(shù)組約定為最多存放即將數(shù)組約定為最多存放maxlen-1個(gè)元素，個(gè)元素， 因此，使得尾指針因此，使得尾指針rear“趕不上趕不上”頭指針頭指針front， 因而不會(huì)出現(xiàn)上述的在滿的情況下，頭尾指針相等的情況。因而不會(huì)出現(xiàn)上述的在滿的情況下，

21、頭尾指針相等的情況。 從而便于判斷的實(shí)現(xiàn)。從而便于判斷的實(shí)現(xiàn)。下面采用第二種方法討論各運(yùn)算的實(shí)現(xiàn)。下面采用第二種方法討論各運(yùn)算的實(shí)現(xiàn)。2maxlen-110ana1a3a2aifrontrear183.2 順序隊(duì)列與循環(huán)隊(duì)列o運(yùn)算實(shí)現(xiàn)（循環(huán)隊(duì)列）：運(yùn)算實(shí)現(xiàn)（循環(huán)隊(duì)列）：queue:queue( ) count = 0; front = rear = 0; Bool queue:empty( )const if ( count = 0 ) return TRUE; return FALSE; /等價(jià)于：return front = rear;Bool queue:full( )const if

22、( count = maxlen - 1 ) return TRUE; return FALSE; /等價(jià)于：return ( rear + 1 ) % maxlen = front ;2maxlen-110ana1a3a2aifrontrear193.2 順序隊(duì)列與循環(huán)隊(duì)列error_code queue:get_front(elementtype &x)const if ( empty() ) return underflow; x = data (front + 1 ) % maxlen ; return success;error_code queue:append(const

23、 elementtype x) if ( full() ) return overflow; rear = ( rear + 1 ) % maxlen ; datarear = x; count +; return success;2maxlen-110ana1a3a2aifrontrear203.2 順序隊(duì)列與循環(huán)隊(duì)列error_code queue:serve() if ( empty() ) return underflow; front = ( front + 1 ) % maxlen; count -; return success;分析：分析： 算法的時(shí)間復(fù)雜度均為算法的時(shí)間復(fù)雜度

24、均為O(1).思考題：思考題：如果不設(shè)置如果不設(shè)置count分量，依據(jù)分量，依據(jù)front和和rear的值，能否計(jì)算出當(dāng)?shù)闹担芊裼?jì)算出當(dāng)前隊(duì)列的元素個(gè)數(shù)？前隊(duì)列的元素個(gè)數(shù)？依據(jù)依據(jù)front和和rear是如何判斷隊(duì)列是如何判斷隊(duì)列“滿滿”的？的？2maxlen-110ana1a3a2aifrontrear213.3隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用o 隊(duì)列在軟件設(shè)計(jì)中有廣泛的應(yīng)用o 例如：n 在操作系統(tǒng)中，多作業(yè)、多任務(wù)的排隊(duì)n 網(wǎng)絡(luò)中：服務(wù)器對(duì)各終端的服務(wù)請(qǐng)求的排隊(duì)。n 在程序設(shè)計(jì)中，用隊(duì)列結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)構(gòu)成某種次序，實(shí)現(xiàn)特定問(wèn)題的求解。o 后面將要介紹的圖的廣度優(yōu)先搜索遍歷算法。223.3隊(duì)列的應(yīng)用隊(duì)列

25、的應(yīng)用o 例例 設(shè)計(jì)算法，用隊(duì)列計(jì)算并打印楊輝三角的前設(shè)計(jì)算法，用隊(duì)列計(jì)算并打印楊輝三角的前8行行的內(nèi)容，即輸出結(jié)果如下：的內(nèi)容，即輸出結(jié)果如下： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1p分析：楊輝三角的規(guī)律是：分析：楊輝三角的規(guī)律是：u每行的第一和最后一個(gè)數(shù)是每行的第一和最后一個(gè)數(shù)是1 1，u從第從第3 3行開(kāi)始的其余的數(shù)是上一行對(duì)應(yīng)行開(kāi)始的其余的數(shù)是上一行對(duì)應(yīng)位置的左右兩個(gè)數(shù)的和。位置的左右兩個(gè)數(shù)的和。u例如，第例如，第7 7行的第行的第3 3個(gè)數(shù)個(gè)數(shù)1515是第是第6

26、 6行中的行中的第第2 2和第和第3 3兩個(gè)數(shù)兩個(gè)數(shù)5 5和和1010的和。的和。u由這一規(guī)律可知，我們可用上一行的數(shù)由這一規(guī)律可知，我們可用上一行的數(shù)來(lái)求出對(duì)應(yīng)位置的下一行的內(nèi)容。來(lái)求出對(duì)應(yīng)位置的下一行的內(nèi)容。u為此，要用隊(duì)列來(lái)保存上一行的內(nèi)容。為此，要用隊(duì)列來(lái)保存上一行的內(nèi)容。u每當(dāng)由上一行的兩個(gè)數(shù)求出下一行的一每當(dāng)由上一行的兩個(gè)數(shù)求出下一行的一個(gè)數(shù)時(shí)，其中的前一個(gè)便需要?jiǎng)h除，而新個(gè)數(shù)時(shí)，其中的前一個(gè)便需要?jiǎng)h除，而新求出的數(shù)就要入隊(duì)。求出的數(shù)就要入隊(duì)。233.3隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用n為了由存放在隊(duì)列中的某行的內(nèi)容求得下一行的內(nèi)容，為了由存放在隊(duì)列中的某行的內(nèi)容求得下一行的內(nèi)容，需要在兩者之間建立一個(gè)對(duì)應(yīng)關(guān)系。需要在兩者之間建立一個(gè)對(duì)應(yīng)關(guān)系。n為便于求解，在每行的第一個(gè)位置添加一個(gè)為便于求解，在每行的第一個(gè)位置添加一個(gè)0作為輔助。作為輔助。n例如，由第例如，由第6行求解第行求解第7行的對(duì)應(yīng)關(guān)系示意圖如下所示。行的對(duì)應(yīng)關(guān)系示意圖如下所示。 s1 s2 0 1 5 10 10 5 1 1 6 15 20 15 6 1n 新一行的最后一個(gè)不能由上一行求得，好在其值是新一行的最后一個(gè)不能由上一行求得，好在其值是確定的數(shù)確定的數(shù)1，只要直接