清華大學(xué)數(shù)據(jù)結(jié)構(gòu)課件(考研必備)dsweekchapqueue

1第三章棧與隊(duì)列

（2）隊(duì)列部分?jǐn)?shù)據(jù)結(jié)構(gòu)電子教案殷人昆

王宏2棧隊(duì)列棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：遞歸隊(duì)列的應(yīng)用：打印楊輝三角形雙端隊(duì)列優(yōu)先級(jí)隊(duì)列第三章棧與隊(duì)列3

隊(duì)列的基本概念只允許在表的一端插入，在另一端刪除。允許插入的一端叫做隊(duì)尾（rear），允許刪除的一端叫做隊(duì)頭（front）。隊(duì)列所具有的這種特性稱為先進(jìn)先出

FIFO（FirstInFirstOut）。a1a2a3

……anfrontrear4template<classT>classQueue{public:Queue(){};

//構(gòu)造函數(shù)

～Queue(){};

//析構(gòu)函數(shù)

virtualboolEnQueue(Tx)=0;//進(jìn)隊(duì)列

virtualboolDeQueue(T&x)=0; //出隊(duì)列

virtualboolgetFront(T&x)=0; //取隊(duì)頭

virtualboolIsEmpty()const=0; //判隊(duì)列空

virtualboolIsFull()const=0; //判隊(duì)列滿};隊(duì)列的抽象數(shù)據(jù)類型5#include<assert.h>#include<iostream.h>#include“Queue.h”template<classT>classSeqQueue:publicQueue<T>{ //隊(duì)列類定義protected:intrear,front; //隊(duì)尾與隊(duì)頭指針

T*elements; //隊(duì)列存放數(shù)組

intmaxSize; //隊(duì)列最大容量public:

SeqQueue(intsz=10);//構(gòu)造函數(shù)

隊(duì)列的數(shù)組存儲(chǔ)表示─順序(循環(huán))隊(duì)列6

～SeqQueue(){

delete[]elements;}//析構(gòu)函數(shù)

boolEnQueue(Tx);//新元素進(jìn)隊(duì)列

boolDeQueue(T&x);//退出隊(duì)頭元素

bool

GetFront(T&x);

//取隊(duì)頭元素值

void

MakeEmpty(){front=rear=0;}

boolIsEmpty()const{returnfront==rear;}

boolIsFull()const

{return

((rear+1)%maxSize==front);}//循環(huán)

intgetSize()const{return

(rear-front+maxSize)%maxSize;}

};7非循環(huán)隊(duì)列的進(jìn)隊(duì)和出隊(duì)(指針變化)

frontrear初始空隊(duì)列frontrearA進(jìn)隊(duì)AfrontrearB進(jìn)隊(duì)ABfrontrearC,D進(jìn)隊(duì)ABCDfrontrearA出隊(duì)BCDfrontrearB出隊(duì)CDfrontrearE,F,G進(jìn)隊(duì)CDEFGCDEFGfrontrearH進(jìn)隊(duì),假溢出8非循環(huán)隊(duì)列的進(jìn)隊(duì)和出隊(duì)原則進(jìn)隊(duì)時(shí)先將新元素按rear指示位置加入，再將隊(duì)尾指針加一rear=rear+1。隊(duì)尾指針指示實(shí)際隊(duì)尾的后一位置。出隊(duì)時(shí)按隊(duì)頭指針指示位置取出元素，再將隊(duì)頭指針進(jìn)一front=front+1，隊(duì)頭指針指示實(shí)際隊(duì)頭位置。隊(duì)滿時(shí)再進(jìn)隊(duì)將溢出出錯(cuò)（可能是假溢出）；隊(duì)空時(shí)再出隊(duì)將按隊(duì)空處理。解決假溢出的辦法之一：將存放隊(duì)列元素的數(shù)組首尾相接，形成循環(huán)（環(huán)形）隊(duì)列。9隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處理。隊(duì)頭、隊(duì)尾指針加1時(shí)從maxSize-1直接進(jìn)到0，可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:

front=(front+1)%maxSize;隊(duì)尾指針進(jìn)1:rear=(rear+1)%maxSize;隊(duì)列初始化：front=rear=0;隊(duì)空條件：front==rear;隊(duì)滿條件：(rear+1)%maxSize==front

思考:按以上定義,隊(duì)列中最多可容納多少元素循環(huán)隊(duì)列(CircularQueue)1001234567front01234567front01234567frontrearAABCrearrear空隊(duì)列A進(jìn)隊(duì)B,C進(jìn)隊(duì)0123456701234567A出隊(duì)B出隊(duì)01234567D,E,F,G,H,I進(jìn)隊(duì)frontBCrearAfrontBCrearfrontCrearDEFGHI11循環(huán)隊(duì)列操作的定義voidMakeEmpty(){front=rear=0;

}

intIsEmpty()const

{returnfront==rear;}

intIsFull()const{return(rear+1)%maxSize==front;}

template<classT>SeqQueue<T>::SeqQueue(intsz)

:front(0),rear(0),maxSize(sz){//構(gòu)造函數(shù)

elements=newT[maxSize];

assert(elements!=NULL);};12template<classT>bool

SeqQueue<T>::EnQueue(Tx){//若隊(duì)列不滿,則將x插入到該隊(duì)列隊(duì)尾,否則返回

if(IsFull()==true)returnfalse;elements[rear]=x;//先存入

rear=(rear+1)%maxSize;//隊(duì)尾指針加一

returntrue; };template<classT>boolSeqQueue<T>::DeQueue(T&x){//若隊(duì)列不空則函數(shù)退隊(duì)頭元素并返回其值

if(IsEmpty()==true)returnfalse;

13

x=elements[front];//先取隊(duì)頭

front=(front+1)%maxSize;

//然后隊(duì)頭指針加一

returntrue;};template<classT>boolSeqQueue<T>::GetFront(T&x)const{//若隊(duì)列不空則函數(shù)返回該隊(duì)列隊(duì)頭元素的值

if(IsEmpty()==true)returnfalse;//隊(duì)列空

x=elements[front]; //返回隊(duì)頭元素

returntrue;};

//分析優(yōu)缺點(diǎn)14隊(duì)列的鏈接存儲(chǔ)表示—

鏈?zhǔn)疥?duì)列隊(duì)頭在鏈頭，隊(duì)尾在鏈尾(真實(shí)隊(duì)尾)。

//與循環(huán)隊(duì)列不同鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無隊(duì)滿問題，但出隊(duì)時(shí)需判斷是否隊(duì)空。隊(duì)空條件為

front==NULL隊(duì)頭隊(duì)尾指針與日常排隊(duì)的情形吻合!frontrear15#include<iostream.h>#include“Queue.h”template<classT>structQueueNode{//隊(duì)列結(jié)點(diǎn)類定義

Tdata; //隊(duì)列結(jié)點(diǎn)數(shù)據(jù)

QueueNode<T>*link;//結(jié)點(diǎn)鏈指針

QueueNode(Td=0,QueueNode<T>*next=NULL):data(d),link(next){}};

鏈?zhǔn)疥?duì)列類的定義16template<classT>classLinkedQueue{

private:

QueueNode<T>*front,*rear;//隊(duì)頭、隊(duì)尾指針public:

LinkedQueue():rear(NULL),front(NULL){}

~LinkedQueue();

boolEnQueue(Tx);//x加入隊(duì)列

boolDeQueue(T&x);

//刪除隊(duì)頭元素,x返回其值

boolGetFront(T&x);

//查看隊(duì)頭元素的值

voidMakeEmpty();//置空隊(duì)列

boolIsEmpty()const

{returnfront==NULL;

}

boolIsFull()const{returnfalse;}};17template<classT>LinkedQueue<T>::~LinkedQueue(){//析構(gòu)函數(shù)

QueueNode<T>*p;

while(front!=NULL){

//逐個(gè)結(jié)點(diǎn)釋放

p=front;front=front->link;

deletep;}};template<classT>bool

LinkedQueue<T>::EnQueue(Tx){//將新元素x插入到隊(duì)列的隊(duì)尾18

if(front==NULL){//創(chuàng)建第一個(gè)結(jié)點(diǎn)

front=rear=newQueueNode<T>(x);//頭尾相同

if(front==NULL)returnfalse;} //分配失敗

else{

//隊(duì)列不空,插入

rear->link=newQueueNode<T>(x);//隊(duì)非空入隊(duì)尾

if(rear->link==NULL)returnfalse;rear=rear->link;}returntrue;};template<classT>//如果隊(duì)列不空，將隊(duì)頭結(jié)點(diǎn)從鏈?zhǔn)疥?duì)列中刪去

19boolLinkedQueue<T>::DeQueue(T&x){

if(IsEmpty()==true)returnfalse;//判隊(duì)空

QueueNode<T>*p=front; x=front->data;front=front->link;

deletep;

returntrue; };template<classT>bool

LinkedQueue<T>::GetFront(T&x){//若隊(duì)列不空，則函數(shù)返回隊(duì)頭元素的值

if(IsEmpty()==true)returnfalse; x=front->data;returntrue;//不改變隊(duì)頭指針};20優(yōu)先級(jí)隊(duì)列(PriorityQueue)優(yōu)先級(jí)隊(duì)列每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素如下表：任務(wù)優(yōu)先權(quán)及執(zhí)行順序的關(guān)系數(shù)字越小，優(yōu)先權(quán)越高21#include<assert.h>#include<iostream.h>#include<stdlib.h>template<classT>classPQueue{private:

T

*pqelements;

//存放數(shù)組

intcount;

//隊(duì)列元素計(jì)數(shù)

intmaxPQSize;//最大元素個(gè)數(shù)

voidadjust();

//調(diào)整優(yōu)先級(jí)隊(duì)列的類定義22public:

PQueue(intsz=50);~PQueue(){delete[]pqelements;}

boolInsert(Tx);

boolRemoveMin(T&x);boolGetFront(T&x);

void

MakeEmpty(){count=0;}

boolIsEmpty()const{returncount==0;}

boolIsFull()const{returncount==maxPQSize;}

intLength()const{returncount;}};23template<classT>PQueue<T>::PQueue(intsz){

maxPQSize=sz;count=0;pqelements=newT[maxPQSize];

assert(pqelements!=NULL);}template<classT>boolPQueue<T>::Insert(Tx){

if(IsFull()==true)returnfalse;//判隊(duì)滿

pqelements[count++]=x;//插入優(yōu)先級(jí)隊(duì)列部分成員函數(shù)的實(shí)現(xiàn)24102040507090插入601020405070906060102040507090606090907070601020405060709025

adjust();returntrue;}template<classT>voidPQueue<T>::adjust(){

T

temp=pqelements[count-1];

//將最后元素暫存再?gòu)暮笙蚯罢也迦胛恢?/p>

for(intj=count-2;j>=0;j--)

if(pqelements[j]<=temp)break;

elsepqelements[j+1]=pqelements[j];

pqelements[j+1]=temp;}26template<classT>boolPQueue<T>::RemoveMin(T&x){if(IsEmpty())returnfalse;x=pqelements[0];//取出0號(hào)元素

for(inti=1;i<count;i++)pqelements[i-1]=pqelements[i];

//從后向前逐個(gè)移動(dòng)元素填補(bǔ)空位

count--;returntrue;}

27template<classT>boolPQueue<T>::GetFront

(T&x){if(IsEmpty()==true)returnfalse;x=pqelements[0];returntrue;}28

雙端隊(duì)列（Deque）

可以在隊(duì)列的兩端進(jìn)行插入和刪除。普通隊(duì)列的延伸和拓展

英文全稱Double-endedqueue

—————————

→←←

—————————→29

雙端隊(duì)列的函數(shù)雙端隊(duì)列提供了三個(gè)存取隊(duì)列頭部的函數(shù)，包括

boolgetHead(T&x)//讀隊(duì)頭元素

boolEnQueueHead(T&x)//在隊(duì)頭插入

boolDeQueueHead(T&x)//刪除隊(duì)頭元素三個(gè)存取隊(duì)列尾部的函數(shù)，包括

boolgetTail(T&x)//讀隊(duì)尾元素

boolEnQueueTail(T&x)//在隊(duì)尾插入

boolDeQueueTail(T&x)//刪除隊(duì)尾元素

30

雙端隊(duì)列的基本操作圖示

142EnQueueHead(3)3142EnQueueTail(5)31425

DeQueueHead()→31425

Initialization

DeQueueTail()→5142

getHead()→1142

getTail()→2142

31

雙端隊(duì)列的C++類template<classT>classDeque:publicQueue<T>{public:

virtualboolgetHead(T&x)const=0;

virtualboolgetTail(T&x)const=0;

virtualboolEnQueue(constT&x);

virtualboolEnQueueHead(constT&x)=0;

virtualboolEnQueueTail(constT&x)=0;

virtualboolDeQueue(T&x);

virtualboolDeQueueHead(T&x)=0;

virtualboolDeQueueTail(T&x)=0;32

雙端隊(duì)列的公共接口在Deque類的公共接口中包括了從基類Queue繼承來的EnQueue和DeQueue函數(shù)。在基類中，由于數(shù)據(jù)元素總是在隊(duì)列尾部進(jìn)隊(duì)列，在頭部出隊(duì)列，所以基類僅需要一個(gè)進(jìn)隊(duì)函數(shù)（EnQueue）及一個(gè)出隊(duì)函數(shù)（DeQueue）。然而，在雙端隊(duì)列中可在任一端進(jìn)行進(jìn)隊(duì)和出隊(duì)操作。33Deque類成員函數(shù)的實(shí)現(xiàn)Deque類提供了EnQueue和Dequeue的默認(rèn)功能，只不過EnQueue僅僅調(diào)用了EnQueueTail函數(shù)（在尾部插入），DeQueue函數(shù)僅僅調(diào)用了DeQueueHead函數(shù)（在頭部刪除）。Deque類成員函數(shù)EnQueue的實(shí)現(xiàn)

template<classT>

boolDeque<T>::EnQueue(constT&x){

return

EnQueueTial(x);};34Deque類成員函數(shù)的實(shí)現(xiàn)boolDeque<T>::DeQueue(T&x){Ttemp;

booltag=DeQueueHead(temp);x=temp;returntag;};

//其它操作參見教材35隊(duì)列的其他變形輸入受限的雙端隊(duì)列允許在一端進(jìn)行插入和刪除，但在另一端只允許刪除的雙端隊(duì)列

—————————

←

←

—————————→輸出受限的雙端隊(duì)列允許在一端進(jìn)行插入和刪除，但在另一端只允許插入的雙端隊(duì)列

—————————

→←

—————————→36

雙端隊(duì)列思考設(shè)一個(gè)雙端隊(duì)列，元素進(jìn)入該隊(duì)列的順序是1，2，3，4，分別求出滿足下列條件的輸出序列：

1.能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列；

2.能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列；

3.既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列。注：在Knuth的名著中該題難度定為25（難度值從0-50），是推薦題目37繼續(xù)深入（應(yīng)該會(huì)提出類似的問題）利用雙端隊(duì)列，是否可得到元素的所有排列。是否有這樣的排列，它不可能利用一個(gè)雙端隊(duì)列得到（既非輸入受限也非輸出受限）38迷宮問題小型迷宮

路口動(dòng)作 結(jié)果

1

(入口)正向走進(jìn)到2

2

左拐彎進(jìn)到3

3

右拐彎進(jìn)到4

4

(堵死)回溯 退到3

3

(堵死)回溯 退到2

2

正向走進(jìn)到5

5

(堵死)回溯 退到2

2

右拐彎進(jìn)到6

6

左拐彎進(jìn)到7(出口)

4352176

6

左0 直2右0

行3行5行60 040 000 00700

7小型迷宮的數(shù)據(jù)39迷宮的類定義#include<iostream.h>#include<fstream.h>#include<stdlib.h>classMaze{private:intMazeSize; intEXIT;

Intersection*intsec; public:Maze(char*filename);

intTraverseMaze(intCurrentPos);}交通路口結(jié)構(gòu)定義structIntersection{

intleft;

intforward;

intright;}40Maze::Maze(char*filename){

//構(gòu)造函數(shù)：從文件

filename

中讀取各路口

//和出口的數(shù)據(jù)

ifstreamfin;

fin.open(filename,ios::in|ios::nocreate);

//為輸入打開文件,文件不存在則打開失敗

if(!fin){

cerr<<“迷宮數(shù)據(jù)文件”<<filename

<<“打不開”<<endl;

exit(1);

}

fin>>MazeSize;

//輸入迷宮路口數(shù)41

intsec=newIntersection[MazeSize+1];

//創(chuàng)建迷宮路口數(shù)組

for(inti=1;i<=MazeSize;i++)

fin>>intsec[i].left>>intsec[i].forward

>>intsec[i].right;

fin>>EXIT;//輸入迷宮出口

fin.close();}迷宮漫游與求解算法

intMaze::TraverseMaze(intCurrentPos){

if(CurrentPos>0){

//路口從1開始42

if(CurrentPos==EXIT){

//出口處理

cout<<CurrentPos<<"";

return1;}

else//遞歸向左搜尋可行

if(TraverseMaze(intsec[CurrentPos].left))

{cout<<CurrentPos<<“”;

return1;}

else//遞歸向前搜尋可行

if(TraverseMaze(intsec[CurrentPos].forward))

{cout<<CurrentPos<<“”;

return1;}

else//遞歸向右搜尋可行

if(TraverseMaze(intsec[CurrentPos].right))

{cout<<CurrentPos<<"";

return1;}

}

return

0;

}43隊(duì)列的應(yīng)用：打印楊輝三角形算法逐行打印二項(xiàng)展開式

(a+b)i

的系數(shù)：楊輝三角形(Pascal’striangle)44分析第i行元素與第i+1行元素的關(guān)系從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)i=2i=3i=401331014641012100110sts+t45從第i行數(shù)據(jù)計(jì)算并存放第i+1行數(shù)據(jù)121013310

146s=0t=1t=2t=1t=0t=1t=3t=3t=1t=0t=1s+ts=ts=ts=ts=ts=ts=ts=ts=ts+t

s+t

s+t

s+t

s+t

s+ts+ts+t46利用隊(duì)列打印二項(xiàng)展開式系數(shù)的算法#include

<stdio.h>#include

<iostream.h>#include"queue.h"void

yanghui(intn){

//分行打印二項(xiàng)式(a+b)n展開式的系數(shù)。程序中利用了一個(gè)

//隊(duì)列,在輸出上一行系數(shù)時(shí),將其下一行的系數(shù)預(yù)先放入

//隊(duì)列中。在各行系數(shù)之間插入一個(gè)0。

Queueq(n+2);

//建立隊(duì)列對(duì)象并初始化

inti=1,j,s=k=0,t,u;

//計(jì)算下一行系數(shù)時(shí)用到的

//工作單元

q.EnQueue(i);