1、模塊十二堆棧與隊列（二）堆棧與隊列（二）n 隊列的定義及其運算隊列的定義及其運算n 抽象隊列類的定義抽象隊列類的定義n 隊列的定義及其實現(xiàn)隊列的定義及其實現(xiàn)n 隊列順序存儲結(jié)構(gòu)隊列順序存儲結(jié)構(gòu)n 循環(huán)隊列循環(huán)隊列n 鏈?zhǔn)疥犃墟準(zhǔn)疥犃兄饕獌?nèi)容主要內(nèi)容13.6 隊列的概念及其運算隊列的概念及其運算n隊列的概念隊列的概念n隊列的有關(guān)運算隊列的有關(guān)運算 隊列的概念隊列的概念n隊列簡稱隊列簡稱隊隊，是一種只允許在，是一種只允許在表的一端進(jìn)表的一端進(jìn)行插入操作行插入操作而在表的而在表的另一端進(jìn)行刪除操作另一端進(jìn)行刪除操作的線性表。的線性表。n允許進(jìn)行插入的一端稱為允許進(jìn)行插入的一端稱為隊尾隊尾，允許刪除，

2、允許刪除的一端稱為的一端稱為隊頭隊頭。隊列的插入運算也簡稱。隊列的插入運算也簡稱進(jìn)隊進(jìn)隊，刪除運算簡稱為，刪除運算簡稱為出隊出隊。n隊列也稱為隊列也稱為先進(jìn)先出表先進(jìn)先出表(FIFO)。 隊列的概念隊列的概念n假設(shè)假設(shè)Q=(a1，a2，an-1，an)為一個隊結(jié)構(gòu)，為一個隊結(jié)構(gòu)，則隊頭為則隊頭為a1，隊尾為，隊尾為an。該隊列是按。該隊列是按a1，a2，an-1，an的順序進(jìn)入的，退出該隊列的順序進(jìn)入的，退出該隊列也只能按這個順序進(jìn)行。也只能按這個順序進(jìn)行。n隊列和堆棧一樣，也是動態(tài)結(jié)構(gòu)，同樣存在隊列和堆棧一樣，也是動態(tài)結(jié)構(gòu)，同樣存在溢出問題，在進(jìn)行插入、刪除運算之前，應(yīng)溢出問題，在進(jìn)行插入、

3、刪除運算之前，應(yīng)進(jìn)行隊滿、隊空的判斷。進(jìn)行隊滿、隊空的判斷。 隊列的有關(guān)運算隊列的有關(guān)運算n進(jìn)隊：進(jìn)隊：在隊列的尾部插入一個新元素在隊列的尾部插入一個新元素n出隊：出隊：刪除隊列的隊頭元素刪除隊列的隊頭元素n測試隊空：測試隊空：測試隊列是否為空測試隊列是否為空n測試隊滿：測試隊滿：測試隊列是否為滿測試隊列是否為滿n清隊：清隊：創(chuàng)建一個空隊列創(chuàng)建一個空隊列 13.3 抽象隊列類抽象隊列類templateclass abque /定義抽象隊列類模板定義抽象隊列類模板 protected : int qsize;/隊列長度隊列長度 public: bool IsEmpty( ) /判隊列是否為空判隊

4、列是否為空 return (qsize=0)?true:false; virtual void PushTail(type&)=0; /將元素插入隊尾將元素插入隊尾 virtual bool PopFront(type&)=0; /從對頭提取元素從對頭提取元素 virtual void Clear( )=0; /清空隊列清空隊列 ; 13.7 隊列的定義與實現(xiàn)隊列的定義與實現(xiàn)n隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)n循環(huán)隊列的定義循環(huán)隊列的定義n循環(huán)隊列類的定義及常用成員函數(shù)的實現(xiàn)循環(huán)隊列類的定義及常用成員函數(shù)的實現(xiàn)n鏈?zhǔn)疥犃械亩x鏈?zhǔn)疥犃械亩xn鏈?zhǔn)疥犃蓄惖亩x及常用成員函數(shù)的

5、實現(xiàn)鏈?zhǔn)疥犃蓄惖亩x及常用成員函數(shù)的實現(xiàn)13.7.1 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)n隊列的順序存儲結(jié)構(gòu)的實現(xiàn)隊列的順序存儲結(jié)構(gòu)的實現(xiàn)n隊列的順序存儲結(jié)構(gòu)的特點隊列的順序存儲結(jié)構(gòu)的特點n假溢出問題假溢出問題 隊列順序存儲結(jié)構(gòu)的實現(xiàn)隊列順序存儲結(jié)構(gòu)的實現(xiàn) n可以用可以用一維數(shù)組一維數(shù)組來描述隊列的順序存儲結(jié)構(gòu)。來描述隊列的順序存儲結(jié)構(gòu)。n首先定義一維數(shù)組首先定義一維數(shù)組elementsmaxsize來存放隊來存放隊列元素，列元素，同時還需要設(shè)置兩個變量同時還需要設(shè)置兩個變量front與與 rear分別指出隊頭元素和隊尾元素的分別指出隊頭元素和隊尾元素的下標(biāo)下標(biāo)。n約定約定：隊頭指針：隊頭指

6、針front指出實際隊頭元素所在指出實際隊頭元素所在位置的位置的前一個位置前一個位置，而隊尾指針，而隊尾指針rear指出實際指出實際隊尾元素隊尾元素所在的位置。所在的位置。初始時，初始時，front=rear= -1，測試一個隊列是否，測試一個隊列是否為空的條件是為空的條件是rear= =front。 以下是隊列示意圖：以下是隊列示意圖： 隊列順序存儲結(jié)構(gòu)的特點隊列順序存儲結(jié)構(gòu)的特點n進(jìn)行插入運算，必須先測試隊滿與否。進(jìn)行插入運算，必須先測試隊滿與否。若隊滿，若隊滿，則調(diào)用相關(guān)算法處理有關(guān)溢出問題；否則，將則調(diào)用相關(guān)算法處理有關(guān)溢出問題；否則，將隊尾指針加隊尾指針加1，然后將新元素插入到當(dāng)前隊

7、尾指，然后將新元素插入到當(dāng)前隊尾指針?biāo)傅奈恢谩ａ標(biāo)傅奈恢谩刪除隊頭元素，必須先測試隊列是否為空。刪除隊頭元素，必須先測試隊列是否為空。若若隊空，則調(diào)用相關(guān)算法處理有關(guān)信息；否則，隊空，則調(diào)用相關(guān)算法處理有關(guān)信息；否則，刪除隊頭元素刪除隊頭元素(隊頭指針加隊頭指針加1)，如果需要，可以，如果需要，可以把被刪除元素保存起來。把被刪除元素保存起來。frontrearfrontreara3元素元素a2出隊后的狀態(tài)出隊后的狀態(tài)front rear元素元素a3出隊后的狀態(tài)出隊后的狀態(tài) 假溢出問題假溢出問題n在隊列的插入算法中，當(dāng)隊尾指針在隊列的插入算法中，當(dāng)隊尾指針rear=maxsize-1時，再

8、做插入運算好象會產(chǎn)生溢出，而實際上這時，再做插入運算好象會產(chǎn)生溢出，而實際上這時隊列的前端還有許多空的位置，稱為時隊列的前端還有許多空的位置，稱為“假溢假溢出出”。n解決假溢出問題，有兩種辦法：解決假溢出問題，有兩種辦法：1、每次刪除隊頭一個元素后，把每次刪除隊頭一個元素后，把整個隊列整個隊列往前移往前移動一個位置，過程如圖所示。在這種情況下，隊動一個位置，過程如圖所示。在這種情況下，隊頭指針頭指針front就沒有用處了。就沒有用處了。 2、可以把隊列設(shè)想成可以把隊列設(shè)想成頭尾相連頭尾相連的循環(huán)表，即把的循環(huán)表，即把存儲隊列元素的表從邏輯上看成一個環(huán)，這種存儲隊列元素的表從邏輯上看成一個環(huán)，這

9、種隊列通常稱為隊列通常稱為循環(huán)隊列循環(huán)隊列。循環(huán)隊列操作圖示循環(huán)隊列操作圖示空隊列空隊列J1,J2,J3J1,J2,J3入隊列入隊列J1,J2,J3J1,J2,J3出隊出隊J4,J5,J6J4,J5,J6入隊入隊rearfront J1J1 J2J2 J3J3 rearfront J6J6 J5J5 J4J4rearfrontrearfront 又有又有J7入隊入隊,該怎么辦？該怎么辦？假溢出n存在問題存在問題設(shè)數(shù)組大小為設(shè)數(shù)組大小為M，則：則：n當(dāng)當(dāng)front=0，rear= M 時，再入隊發(fā)生溢時，再入隊發(fā)生溢出出真溢出真溢出n當(dāng)當(dāng)front 0，rear= M 時，再入隊發(fā)生溢時，再入隊

10、發(fā)生溢出出假溢出假溢出n解決方案解決方案n隊首固定，每次出隊后將剩余元素向下隊首固定，每次出隊后將剩余元素向下移動移動浪費時間浪費時間n循環(huán)隊列循環(huán)隊列n基本思想：把隊列設(shè)想成環(huán)形，讓基本思想：把隊列設(shè)想成環(huán)形，讓 elementsM-1 接在接在 elements0 之之后，若后，若rear+1=M，則令則令rear=0;rear123450J4,J5,J6入隊入隊J4J5J6front0M-11frontrear.實現(xiàn)：利用實現(xiàn)：利用“模模”運算運算入隊：入隊：elementsrear=e; rear=(rear+1)%M; 出隊：出隊：e=elementsfront; front=(fr

11、ont+1)%M; 隊滿、隊空判定條件隊滿、隊空判定條件?012345rearfrontJ7J5J6012345frontJ4J9J8rearJ5J6J4012345rearfrontJ4,J5,J6出隊出隊J7,J8,J9入隊入隊隊空：隊空：front=rear解決方案：解決方案：1.另外另外設(shè)一個標(biāo)志設(shè)一個標(biāo)志以區(qū)別隊空、隊以區(qū)別隊空、隊滿滿2.少用一個元素空間：少用一個元素空間： 隊空：隊空：front=rear 隊滿：隊滿：(rear+1)%M=front隊滿：隊滿：front=rearJ4,J5,J6出隊出隊J7,J8入隊入隊隊滿：隊滿：front=(rear+1)%Mn 少用一個元

12、素空間：少用一個元素空間： 隊空：隊空：front=rear 隊滿：隊滿：(rear+1)%M=front隊空：隊空：front=rearJ5J6J4012345rearfront012345rearfrontJ7J5J6012345frontJ4J8rear在循環(huán)隊列示意圖中，可以看到隊列空和隊在循環(huán)隊列示意圖中，可以看到隊列空和隊列滿時，都有列滿時，都有rear= =front。為區(qū)分隊空隊滿，可采用兩種處理方法：為區(qū)分隊空隊滿，可采用兩種處理方法：u設(shè)一個設(shè)一個標(biāo)志位標(biāo)志位以區(qū)別隊列是空還是滿；以區(qū)別隊列是空還是滿；u少用一個元素空間，約定以少用一個元素空間，約定以“隊列頭指針隊列頭指針

13、在隊列尾指針的下一位置上在隊列尾指針的下一位置上”作為隊列滿作為隊列滿的標(biāo)志。的標(biāo)志。 循環(huán)隊列的首尾相接，當(dāng)隊頭指針循環(huán)隊列的首尾相接，當(dāng)隊頭指針front和隊尾指針和隊尾指針rear進(jìn)到進(jìn)到maxsize-1時，再前進(jìn)時，再前進(jìn)一個位置就自動到一個位置就自動到0，利用，利用除法取余除法取余的運算的運算來實現(xiàn)。來實現(xiàn)。插入運算修改隊尾指針：插入運算修改隊尾指針： rear=(rear+1)%maxsize刪除運算修改隊頭指針：刪除運算修改隊頭指針： front=(front+1)%maxsize11.7.2 循環(huán)隊列類的定義及常用成員函數(shù)的實現(xiàn)循環(huán)隊列類的定義及常用成員函數(shù)的實現(xiàn)templa

14、teclass SeqQuene: public abqueprotected: int head； /隊頭指針隊頭指針 int tail; /隊尾指針隊尾指針 type *elements; /存放隊列元素的數(shù)組存放隊列元素的數(shù)組 int maxsize; /隊列最大可容納元素個數(shù)隊列最大可容納元素個數(shù) SeqQuene & Copy(SeqQuene & q); /隊列拷貝函數(shù)隊列拷貝函數(shù) public: SeqQuene(int i=10); /構(gòu)造函數(shù)，缺省參數(shù)構(gòu)造函數(shù)，缺省參數(shù) SeqQuene( ) /析構(gòu)函數(shù)析構(gòu)函數(shù) Clear( ); void PushTail

15、 (type &); /將新元素插入在隊尾將新元素插入在隊尾 bool PopFront (type &); /從隊頭取一個元素從隊頭取一個元素 void Clear( ) /清空隊列清空隊列 delete elements; /重載賦值運算符，用來對同類隊列賦值重載賦值運算符，用來對同類隊列賦值 SeqQuene & operator=(SeqQuene & q) Copy(q); return *this; bool IsFull( ) const /判隊列是否為滿判隊列是否為滿 return(tail+1)%maxsize=head?ture:false;

16、 bool IsEmpty( ) /判隊列是否為空判隊列是否為空 return head=tail?ture:false; ;const的含義：該成的含義：該成員函數(shù)的算法不修改員函數(shù)的算法不修改該類的成員變量的值該類的成員變量的值13.7.2 循環(huán)隊列類的定義及常用成員函數(shù)的實現(xiàn)循環(huán)隊列類的定義及常用成員函數(shù)的實現(xiàn)n構(gòu)造函數(shù)構(gòu)造函數(shù) ：首先將隊列設(shè)置為空隊列，設(shè)置隊列最首先將隊列設(shè)置為空隊列，設(shè)置隊列最大長度，為隊列分配空間。大長度，為隊列分配空間。templateSeqQuene: SeqQuene(int i) head=tail=0; /將隊列設(shè)置為空隊列將隊列設(shè)置為空隊列 maxsi

17、ze=i10?10:i; /設(shè)置隊列的最大長度，最小為設(shè)置隊列的最大長度，最小為10 qsize=0; /隊列實際長度隊列實際長度 elements=new typemaxsize; /給隊列分配內(nèi)存空間給隊列分配內(nèi)存空間 assert(elements!=0); /失敗，警告失敗，警告n插入運算插入運算(進(jìn)隊進(jìn)隊)：進(jìn)隊之前，先判斷隊滿與否。進(jìn)隊之前，先判斷隊滿與否。 若隊滿，則退出程序的執(zhí)行；否則，將隊尾指針若隊滿，則退出程序的執(zhí)行；否則，將隊尾指針加加1后求模，然后將新元素插入到當(dāng)前隊尾指針?biāo)笄竽＃缓髮⑿略夭迦氲疆?dāng)前隊尾指針?biāo)谖恢茫犻L加在位置，隊長加1。templateSeqQ

18、uene: PushTail(type & x) assert(!IsFull( ); /若隊滿，警告，出錯處理若隊滿，警告，出錯處理 tail=(tail+1)%maxsize; /尾指針加尾指針加1 elementstail=x; /給隊尾賦值給隊尾賦值 qsize+; /隊長加隊長加1n刪除運算刪除運算(出隊出隊)：刪除隊頭元素之前，先測試隊列是否刪除隊頭元素之前，先測試隊列是否 為空。若為空，則退出程序；否則，刪除隊頭元素為空。若為空，則退出程序；否則，刪除隊頭元素(隊頭隊頭指針加指針加1)，隊列長度減，隊列長度減1。如果需要，可以把刪除的元素。如果需要，可以把刪除的元素保存起

19、來。保存起來。templateSeqQuene: PopFront(type & x) assert(!IsEmpty( ); /若隊空，警告，出錯處理若隊空，警告，出錯處理 x=elementshead; /取出隊頭元素取出隊頭元素 head=(head+1)%maxsize; /頭指針加頭指針加1 qsize-; /隊長減隊長減1 return true; n 拷貝函數(shù)拷貝函數(shù)：將隊列將隊列que拷貝到當(dāng)前隊列。拷貝到當(dāng)前隊列。templateSeqQuene&SeqQuene:Copy(SeqQuene&que) if(elements) /若當(dāng)前隊列不為空，刪除

20、當(dāng)前隊列元素若當(dāng)前隊列不為空，刪除當(dāng)前隊列元素 delete elements; maxsize=que.maxsize; qsize=que.qsize; tail=que.tail; head=que.head; /按按que隊列的大小，為當(dāng)前隊列分配內(nèi)存空間隊列的大小，為當(dāng)前隊列分配內(nèi)存空間 elements=new typemaxsize; assert(elements)； /內(nèi)存分配成功，復(fù)制隊列的內(nèi)容內(nèi)存分配成功，復(fù)制隊列的內(nèi)容 memmove(elements, que.elements, sizeof(type)*maxsize); return *this;13.7.4 鏈

21、式隊列的定義鏈?zhǔn)疥犃械亩xn鏈?zhǔn)疥犃械亩x鏈?zhǔn)疥犃械亩xn鏈?zhǔn)疥犃蓄惖亩x鏈?zhǔn)疥犃蓄惖亩xn鏈?zhǔn)疥犃兄谐Ｓ贸蓡T函數(shù)的實現(xiàn)鏈?zhǔn)疥犃兄谐Ｓ贸蓡T函數(shù)的實現(xiàn)13.7.4 鏈?zhǔn)疥犃械亩x鏈?zhǔn)疥犃械亩xn隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)就是用一個隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)就是用一個線性鏈表線性鏈表來來表示隊列，簡稱表示隊列，簡稱鏈?zhǔn)疥犳準(zhǔn)疥牐籲把線性鏈表的把線性鏈表的頭指針定義為頭指針定義為“隊頭指針隊頭指針” head，把鏈表的，把鏈表的最后結(jié)點指針作為最后結(jié)點指針作為“隊尾指隊尾指針針” tail，并且限定只能在鏈頭進(jìn)行刪除，只，并且限定只能在鏈頭進(jìn)行刪除，只能在鏈尾進(jìn)行插入。該線性鏈表就成為一個能在鏈尾進(jìn)行插入。該線性鏈

22、表就成為一個鏈?zhǔn)疥犃校绘準(zhǔn)疥犃校籲鏈?zhǔn)疥犃械年狀^指針與隊尾指針都指向?qū)嶋H鏈?zhǔn)疥犃械年狀^指針與隊尾指針都指向?qū)嶋H 的隊頭與隊尾結(jié)點。的隊頭與隊尾結(jié)點。a1a2anheadtailheadtaila1非空鏈隊列非空鏈隊列空的鏈隊列空的鏈隊列NULLNULLheadtail 鏈?zhǔn)疥犃袌D示鏈?zhǔn)疥犃袌D示u 對如下的一般鏈接隊列：對如下的一般鏈接隊列：u 測試鏈?zhǔn)疥犃袦y試鏈?zhǔn)疥犃小笆欠駷榭帐欠駷榭铡钡臈l件為的條件為: head =NULLu 插入一個新元素就是在隊尾結(jié)點后添加一個新結(jié)點插入一個新元素就是在隊尾結(jié)點后添加一個新結(jié)點; u 刪除一個元素就是刪除鏈表的第一個結(jié)點。刪除一個元素就是刪除鏈表的第一個

23、結(jié)點。 13.7.5 鏈?zhǔn)疥犃蓄惖亩x及常用成員函數(shù)的實現(xiàn)鏈?zhǔn)疥犃蓄惖亩x及常用成員函數(shù)的實現(xiàn)n隊列結(jié)點結(jié)構(gòu)的定義隊列結(jié)點結(jié)構(gòu)的定義templatestruct QueneNode /定義隊列的結(jié)點類型定義隊列的結(jié)點類型 type data; /結(jié)點數(shù)據(jù)元素值結(jié)點數(shù)據(jù)元素值 QueneNode *next; /結(jié)點指針值結(jié)點指針值;n鏈?zhǔn)疥犃蓄惖亩x鏈?zhǔn)疥犃蓄惖亩xtemplate /定義鏈?zhǔn)疥犃蓄惗x鏈?zhǔn)疥犃蓄恈lass LinkQuene: public abque protected: QueneNode *head; /隊頭隊頭 QueneNode *tail; /隊尾隊尾 /隊列拷貝

24、函數(shù)隊列拷貝函數(shù) LinkQuene & Copy(LinkQuene & q)； public: LinkQuene( ); /構(gòu)造函數(shù)構(gòu)造函數(shù) LinkQuene(LinkQuene & q) /拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù) head=NULL; tail=NULL; Copy(q); LinkQuene( ) /析構(gòu)函數(shù)析構(gòu)函數(shù) Clear( ); void PushTail(type &); /將新元素插入在隊尾將新元素插入在隊尾 bool PopFront(type &); /從隊頭取一個元素從隊頭取一個元素 void Clear( ); /清空隊

25、列清空隊列 /重載賦值運算符，對同類隊列賦值重載賦值運算符，對同類隊列賦值 LinkQuene & operator=(LinkQuene & q) Copy(q); return *this; ;11.7.5 鏈?zhǔn)疥犃蓄惖亩x及常用成員函數(shù)的實現(xiàn)鏈?zhǔn)疥犃蓄惖亩x及常用成員函數(shù)的實現(xiàn)n構(gòu)造函數(shù)：構(gòu)造函數(shù)：建立一個空隊列。建立一個空隊列。template /定義構(gòu)造函數(shù)定義構(gòu)造函數(shù)LinkQuene : LinkQuene( ) head=tail=NULL; qsize=0; /構(gòu)造一個空隊列構(gòu)造一個空隊列 n 進(jìn)隊函數(shù)進(jìn)隊函數(shù)(入隊入隊)：鏈?zhǔn)疥犃胁迦脒\算一般不會鏈?zhǔn)疥犃胁迦?/p>

26、運算一般不會溢出。插入運算時可不判斷隊滿，但插入每個結(jié)點溢出。插入運算時可不判斷隊滿，但插入每個結(jié)點都要動態(tài)分配存儲空間，要修改頭、尾指針。都要動態(tài)分配存儲空間，要修改頭、尾指針。template /向隊尾插入元素向隊尾插入元素void LinkQuene:PushTail(type & x) QueneNode *p; p=new QueneNode; /建立新結(jié)點建立新結(jié)點 assert(p)； /分配失敗，設(shè)置錯誤信息，返回分配失敗，設(shè)置錯誤信息，返回 p-data=x; /給新結(jié)點賦值給新結(jié)點賦值 if(tail) /若隊列非空若隊列非空 p-next=NULL; tail-n

27、ext=p; /將新結(jié)點鏈接到隊尾將新結(jié)點鏈接到隊尾 tail=p; /修改隊尾指針修改隊尾指針 else /若隊列為空若隊列為空 p-next=NULL; tail=p; /將將p結(jié)點設(shè)置為隊列頭和隊列尾結(jié)點設(shè)置為隊列頭和隊列尾 head=p; qsize+; /隊長加隊長加1n 出隊函數(shù)出隊函數(shù)(出隊出隊)：刪除前，先判斷隊列是否為空。刪除前，先判斷隊列是否為空。若為空，返回；若非空，先將隊頭結(jié)點數(shù)據(jù)元素賦給若為空，返回；若非空，先將隊頭結(jié)點數(shù)據(jù)元素賦給x，再修改隊頭指針。若隊列已刪空，應(yīng)將，再修改隊頭指針。若隊列已刪空，應(yīng)將tail改為改為NULL。修改指針后，應(yīng)釋放。修改指針后，應(yīng)釋放

28、(刪除刪除)原隊頭指向的結(jié)原隊頭指向的結(jié)點，隊列長度減點，隊列長度減1。template /從隊頭取一結(jié)點從隊頭取一結(jié)點bool LinkQuene:PopFront(type & x) QueneNode *p; if(head) /若隊列非空若隊列非空 x=head-data; /將隊頭結(jié)點數(shù)據(jù)元素值賦給將隊頭結(jié)點數(shù)據(jù)元素值賦給x p=head; head=head-next; /修改隊頭，后移一個結(jié)點位置修改隊頭，后移一個結(jié)點位置 /修改修改head后，若隊列被刪空，將后，若隊列被刪空，將tail改為改為NULL if(head=NULL) tail=NULL; delete p

29、; /刪除或釋放原隊頭結(jié)點占用的空間刪除或釋放原隊頭結(jié)點占用的空間 qsize-; /隊長減隊長減1 return true; return false; /隊列空時，返回隊列空時，返回falsen 拷貝函數(shù)拷貝函數(shù)，注意兩點：注意兩點： 1、 插入每個結(jié)點都要動態(tài)分配存儲空間；插入每個結(jié)點都要動態(tài)分配存儲空間； 2、 頭、尾指針都要修改。頭、尾指針都要修改。templateLinkQuene& LinkQuene:Copy(LinkQuene&que) QueneNode *p, *q, *r; if(head)/若當(dāng)前隊列非空，先收回隊列結(jié)點占用的空間若當(dāng)前隊列非空，先收回

30、隊列結(jié)點占用的空間 Clear( ); qsize=que.qsize; /復(fù)制隊列長度復(fù)制隊列長度 head=tail=NULL; if(!que.head) /若若que隊列為空，返回隊列為空，返回 return *this; /為當(dāng)前隊列結(jié)點分配存儲空間為當(dāng)前隊列結(jié)點分配存儲空間 head=new QueneNode; assert(head); /若分配失敗，返回若分配失敗，返回/將將que隊列頭結(jié)點內(nèi)容復(fù)制給當(dāng)前隊列結(jié)點隊列頭結(jié)點內(nèi)容復(fù)制給當(dāng)前隊列結(jié)點 head-data=que.head-data; head-next=NULL; /將隊列頭和尾均指向此結(jié)點，因隊列只含一個結(jié)點將隊

31、列頭和尾均指向此結(jié)點，因隊列只含一個結(jié)點 tail=head; p=head; /p指向當(dāng)前隊列頭指向當(dāng)前隊列頭 /將指向隊列將指向隊列que第二個結(jié)點的指針賦給第二個結(jié)點的指針賦給q q=que.head-next; while(q) /從第二個結(jié)點至隊尾進(jìn)行結(jié)點間賦值從第二個結(jié)點至隊尾進(jìn)行結(jié)點間賦值 r=new QueneNode; /建立一個新結(jié)點建立一個新結(jié)點 assert(r)； /失敗，返回失敗，返回 r-data=q-data; /給結(jié)點賦值給結(jié)點賦值 r-next=NULL; p-next=r; /將新拷貝的結(jié)點鏈接到當(dāng)前隊列尾將新拷貝的結(jié)點鏈接到當(dāng)前隊列尾 tail=r; /

32、隊尾指針指向新結(jié)點，即最后一個結(jié)點隊尾指針指向新結(jié)點，即最后一個結(jié)點 p=p-next; /當(dāng)前隊列指針后移一個結(jié)點當(dāng)前隊列指針后移一個結(jié)點 q=q-next; /que隊列指針后移一個結(jié)點隊列指針后移一個結(jié)點 return *this; n 清清隊函數(shù)隊函數(shù)templatevoid LinkQuene:Clear() type p; /從隊頭至隊尾，循環(huán)提取隊列中各元素（保存從隊頭至隊尾，循環(huán)提取隊列中各元素（保存 到到p中），實現(xiàn)清除中），實現(xiàn)清除 while(PopFront(p); head=tail=NULL;順序隊列與鏈?zhǔn)疥犃械谋容^順序隊列與鏈?zhǔn)疥犃械谋容^ n順序隊列順序隊列 n固定的存儲空間固定的存儲空間n方便訪問隊列內(nèi)部元素方便訪問隊列內(nèi)部元素n鏈?zhǔn)芥準(zhǔn)疥犃嘘犃衝可以滿足可以滿足大小無法估計的情況大小無法估計的情況 n訪問隊列內(nèi)部元素不方便訪問隊列內(nèi)部元素不方便隊列的應(yīng)用隊列的應(yīng)用 n只要滿足先來先服務(wù)特性的應(yīng)用均可采用隊只要滿足先來先服務(wù)特性的應(yīng)用均可采用隊列作為其數(shù)據(jù)組織方式或中間數(shù)據(jù)結(jié)構(gòu)。列作為其數(shù)據(jù)組織方式或中間數(shù)據(jù)結(jié)構(gòu)。 n調(diào)度或緩沖調(diào)度或緩沖n消息緩沖器消息緩沖器 n郵件緩沖器郵件緩沖器 n計算機(jī)的硬設(shè)備之間的通信也需要隊列作為數(shù)