3-3隊(duì)列v第三章棧和隊(duì)列隊(duì)列的邏輯結(jié)構(gòu)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)學(xué)什么？循環(huán)隊(duì)列和鏈隊(duì)列的比較3-3-1隊(duì)列的邏輯結(jié)構(gòu)v第三章棧和隊(duì)列隊(duì)列的定義隊(duì)列：只允許在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作（a1,a2,…,an-1,an）隊(duì)尾：允許插入的一端，相應(yīng)地，位于隊(duì)尾的元素稱(chēng)為隊(duì)尾元素a1

a2

…

an棧a1

a2

…

an隊(duì)列隊(duì)頭隊(duì)尾隊(duì)頭：允許刪除的一端，相應(yīng)地，位于隊(duì)頭的元素稱(chēng)為隊(duì)頭元素隊(duì)列的操作特性插入：入隊(duì)、進(jìn)隊(duì)任何時(shí)候執(zhí)行出隊(duì)操作，一定是哪個(gè)元素呢？隊(duì)列的操作特性：先進(jìn)先出（FirstInFirstOut，F(xiàn)IFO）a入隊(duì)出隊(duì)bc例：有三個(gè)元素按a、b、c的次序依次入隊(duì)，且每個(gè)元素只允許進(jìn)一次隊(duì)，則出隊(duì)序列是什么？答：出隊(duì)序列只有一種情況：abc刪除：出隊(duì)空隊(duì)列：不含任何數(shù)據(jù)元素的隊(duì)列

隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義ADTStackDataModelOperationendADT隊(duì)列中元素具有相同類(lèi)型及先進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系InitQueue：隊(duì)列的初始化DestroyQueue：隊(duì)列的銷(xiāo)毀EnQueue：入隊(duì)DeQueue：出隊(duì)GetQueue：取隊(duì)頭元素Empty：判空與棧類(lèi)似，隊(duì)列的基本操作是確定的InitQueue

輸入：無(wú)功能：初始化隊(duì)列，創(chuàng)建一個(gè)空隊(duì)列輸出：無(wú)DestroyQueue

輸入：無(wú)功能：銷(xiāo)毀隊(duì)列，釋放隊(duì)列所占用的存儲(chǔ)空間輸出：無(wú)EnQueue

輸入：元素值x

功能：在隊(duì)尾插入一個(gè)元素輸出：如果插入成功，隊(duì)尾增加了一個(gè)元素；否則返回失敗信息a1

a2

…an入隊(duì)出隊(duì)Enqueue操作需要指明插入位置嗎？隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義DeQueue

輸入：無(wú)功能：刪除隊(duì)頭元素輸出：如果刪除成功，返回被刪元素值；否則給出失敗信息GetQueue

輸入：無(wú)功能：讀取隊(duì)頭元素輸出：若隊(duì)列不空，返回隊(duì)頭元素；否則給出失敗信息Empty

輸入：無(wú)功能：判斷隊(duì)列是否為空輸出：如果隊(duì)列為空，返回1，否則，返回0a1

a2

…an入隊(duì)出隊(duì)隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義3-3-2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)v第三章棧和隊(duì)列順序隊(duì)列順序隊(duì)列：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如何表示隊(duì)尾：設(shè)變量rear存儲(chǔ)隊(duì)尾元素所在的下標(biāo)如何表示隊(duì)頭：用數(shù)組的一端作為隊(duì)頭，從下標(biāo)0處開(kāi)始存放如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？01234a1a2a3a4rear例：a1a2a3a4依次入隊(duì)入隊(duì)操作的時(shí)間性能？01234a1a2a3a4rear例：a1a2依次出隊(duì)順序隊(duì)列順序隊(duì)列：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)出隊(duì)操作的時(shí)間性能？如何表示隊(duì)尾：設(shè)變量rear存儲(chǔ)隊(duì)尾元素所在的下標(biāo)如何表示隊(duì)頭：用數(shù)組的一端作為隊(duì)頭，從下標(biāo)0處開(kāi)始存放如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？如何改進(jìn)出隊(duì)操作的時(shí)間性能？01234a2a3a4rear設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)位置指針約定：隊(duì)頭front指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾rear指向隊(duì)尾元素fronta1例：a1a2依次出隊(duì)入隊(duì)、出隊(duì)時(shí)間性能均是O(1)順序隊(duì)列隊(duì)列的移動(dòng)有什么特點(diǎn)？01234a2a3a4front例：a1a2依次出隊(duì)整個(gè)隊(duì)列向數(shù)組下標(biāo)較大方向移動(dòng)單向移動(dòng)性隊(duì)列的單向移動(dòng)性會(huì)產(chǎn)生什么問(wèn)題？a5假溢出：數(shù)組空間發(fā)生上溢，但數(shù)組的低端還有空閑空間rear順序隊(duì)列如何解決假溢出呢？01234a3a4rearfront如何使數(shù)組下標(biāo)循環(huán)呢？a5a6if(rear+1>4)rear=0;elserear++;循環(huán)隊(duì)列：隊(duì)列采用順序存儲(chǔ)，并且數(shù)組是頭尾相接的循環(huán)結(jié)構(gòu)程序技巧：求模（正余數(shù)）使得數(shù)組下標(biāo)循環(huán)rear=(rear+1)%5循環(huán)隊(duì)列循環(huán)隊(duì)列的類(lèi)定義InitQueue：隊(duì)列的初始化DestroyQueue：隊(duì)列的銷(xiāo)毀EnQueue：入隊(duì)DeQueue：出隊(duì)GetQueue：取隊(duì)頭元素Empty：判空隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義？constintQueueSize=100;template<typenameDataType>classCirQueue{public:CirQueue();~CirQueue();voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();intEmpty();private:

DataTypedata[QueueSize];intfront,rear;};CirQueue<DataType>::CirQueue(){front=rear=QueueSize-1;}循環(huán)隊(duì)列的實(shí)現(xiàn)——初始化01234rearfrontCirQueue<DataType>::CirQueue(){front=rear=-1;}rearfront循環(huán)隊(duì)列：隊(duì)列采用順序存儲(chǔ)，并且數(shù)組是頭尾相接的循環(huán)結(jié)構(gòu)設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)位置指針會(huì)出現(xiàn)Bug？01234a3rearfront如何判斷循環(huán)隊(duì)列的隊(duì)空？隊(duì)空的判定條件：front=rearintCirQueue<DataType>::Empty(){if(rear==front)return1;elsereturn0;}循環(huán)隊(duì)列的實(shí)現(xiàn)——判空a6a2a4a5rearfront如何判斷循環(huán)隊(duì)列隊(duì)滿(mǎn)？隊(duì)空的判定條件：front=rear隊(duì)滿(mǎn)的判定條件：front=rearx隊(duì)空和隊(duì)滿(mǎn)0123401234a6a2a4a5rearfront如何確定不同的隊(duì)空、隊(duì)滿(mǎn)的判定條件？隊(duì)空的判定條件：front=rear隊(duì)滿(mǎn)的判定條件：front=rear數(shù)組中有一個(gè)空閑單元01234a1a2a4a5rearfront(rear+1)%QueueSize=front隊(duì)空和隊(duì)滿(mǎn)template<typenameDataType>voidCirQueue<DataType>::EnQueue(DataTypex){

if((rear+1)%QueueSize==front)throw"上溢";

rear=(rear+1)%QueueSize;//隊(duì)尾指針在循環(huán)意義下加1data[rear]=x;//在隊(duì)尾處插入元素}

01234a3a4rearfront時(shí)間復(fù)雜度是多少？循環(huán)隊(duì)列的實(shí)現(xiàn)——入隊(duì)xPage07template<typenameDataType>DataTypeCirQueue<DataType>::DeQueue(){if(rear==front)throw"下溢";

front=(front+1)%QueueSize;//隊(duì)頭指針在循環(huán)意義下加1returndata[front];//讀取并返回出隊(duì)前的隊(duì)頭元素}取隊(duì)頭元素的實(shí)現(xiàn)？01234a2a3a4rearfront循環(huán)隊(duì)列的實(shí)現(xiàn)——出隊(duì)3-3-3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)v第三章棧和隊(duì)列鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)定義鏈隊(duì)列：隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)firsta1a2an∧aiP：用鏈表的哪一端作為隊(duì)頭？哪一端作為隊(duì)尾？A：鏈頭作為隊(duì)頭，出隊(duì)時(shí)間為O(1)

鏈尾作為隊(duì)尾，入隊(duì)時(shí)間為O(n)P：鏈隊(duì)列需要加頭結(jié)點(diǎn)嗎？rearfront設(shè)置隊(duì)尾指針rear鏈隊(duì)列的類(lèi)定義InitQueue：隊(duì)列的初始化DestroyQueue：隊(duì)列的銷(xiāo)毀EnQueue：入隊(duì)DeQueue：出隊(duì)GetQueue：取隊(duì)頭元素Empty：判空隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義？template<typenameDataType>classLinkedQueue{public:

LinkedQueue();~LinkedQueue();voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();intEmpty();private:

Node<DataType>*front,*rear;};xs∧front∧rear沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？xs∧rearfrontrear=s;front=s;鏈隊(duì)列的實(shí)現(xiàn)——入隊(duì)voidLinkedQueue<DataType>::EnQueue(DataTypex){

Node<DataType>*s=nullptr;

s=newNode<DataType>;//申請(qǐng)結(jié)點(diǎn)s

s->data=x;s->next=nullptr;

rear->next=s;rear=s;}時(shí)間復(fù)雜度是多少？a1a2an∧airearfrontxs∧考慮邊界情況？p∧考慮邊界情況？如何判斷邊界情況？a1a2an∧airearfrontprear∧a1frontp->next=nullptr鏈隊(duì)列的實(shí)現(xiàn)——出隊(duì)DataTypeLinkedQueue<DataType>::DeQueue(){DataTypex;Node<DataType>*p=nullptr;

if(rear==front)throw"下溢";p=front->next;x=p->data;

front->next=p->n