清华大学数据结构课件(考研必备)dsweekchapqueue

1第三章栈与队列

（2）队列部分数据结构电子教案殷人昆

王宏2栈队列栈的应用：表达式求值栈的应用：递归队列的应用：打印杨辉三角形双端队列优先级队列第三章栈与队列3

队列的基本概念只允许在表的一端插入，在另一端删除。允许插入的一端叫做队尾（rear），允许删除的一端叫做队头（front）。队列所具有的这种特性称为先进先出

FIFO（FirstInFirstOut）。a1a2a3

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

//构造函数

～Queue(){};

//析构函数

virtualboolEnQueue(Tx)=0;//进队列

virtualboolDeQueue(T&x)=0; //出队列

virtualboolgetFront(T&x)=0; //取队头

virtualboolIsEmpty()const=0; //判队列空

virtualboolIsFull()const=0; //判队列满};队列的抽象数据类型5#include<assert.h>#include<iostream.h>#include“Queue.h”template<classT>classSeqQueue:publicQueue<T>{ //队列类定义protected:intrear,front; //队尾与队头指针

T*elements; //队列存放数组

intmaxSize; //队列最大容量public:

SeqQueue(intsz=10);//构造函数

队列的数组存储表示─顺序(循环)队列6

～SeqQueue(){

delete[]elements;}//析构函数

boolEnQueue(Tx);//新元素进队列

boolDeQueue(T&x);//退出队头元素

bool

GetFront(T&x);

//取队头元素值

void

MakeEmpty(){front=rear=0;}

boolIsEmpty()const{returnfront==rear;}

boolIsFull()const

{return

((rear+1)%maxSize==front);}//循环

intgetSize()const{return

(rear-front+maxSize)%maxSize;}

};7非循环队列的进队和出队(指针变化)

frontrear初始空队列frontrearA进队AfrontrearB进队ABfrontrearC,D进队ABCDfrontrearA出队BCDfrontrearB出队CDfrontrearE,F,G进队CDEFGCDEFGfrontrearH进队,假溢出8非循环队列的进队和出队原则进队时先将新元素按rear指示位置加入，再将队尾指针加一rear=rear+1。队尾指针指示实际队尾的后一位置。出队时按队头指针指示位置取出元素，再将队头指针进一front=front+1，队头指针指示实际队头位置。队满时再进队将溢出出错（可能是假溢出）；队空时再出队将按队空处理。解决假溢出的办法之一：将存放队列元素的数组首尾相接，形成循环（环形）队列。9队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:

front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%maxSize==front

思考:按以上定义,队列中最多可容纳多少元素循环队列(CircularQueue)1001234567front01234567front01234567frontrearAABCrearrear空队列A进队B,C进队0123456701234567A出队B出队01234567D,E,F,G,H,I进队frontBCrearAfrontBCrearfrontCrearDEFGHI11循环队列操作的定义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){//构造函数

elements=newT[maxSize];

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

SeqQueue<T>::EnQueue(Tx){//若队列不满,则将x插入到该队列队尾,否则返回

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

rear=(rear+1)%maxSize;//队尾指针加一

returntrue; };template<classT>boolSeqQueue<T>::DeQueue(T&x){//若队列不空则函数退队头元素并返回其值

if(IsEmpty()==true)returnfalse;

13

x=elements[front];//先取队头

front=(front+1)%maxSize;

//然后队头指针加一

returntrue;};template<classT>boolSeqQueue<T>::GetFront(T&x)const{//若队列不空则函数返回该队列队头元素的值

if(IsEmpty()==true)returnfalse;//队列空

x=elements[front]; //返回队头元素

returntrue;};

//分析优缺点14队列的链接存储表示—

链式队列队头在链头，队尾在链尾(真实队尾)。

//与循环队列不同链式队列在进队时无队满问题，但出队时需判断是否队空。队空条件为

front==NULL队头队尾指针与日常排队的情形吻合!frontrear15#include<iostream.h>#include“Queue.h”template<classT>structQueueNode{//队列结点类定义

Tdata; //队列结点数据

QueueNode<T>*link;//结点链指针

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

链式队列类的定义16template<classT>classLinkedQueue{

private:

QueueNode<T>*front,*rear;//队头、队尾指针public:

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

~LinkedQueue();

boolEnQueue(Tx);//x加入队列

boolDeQueue(T&x);

//删除队头元素,x返回其值

boolGetFront(T&x);

//查看队头元素的值

voidMakeEmpty();//置空队列

boolIsEmpty()const

{returnfront==NULL;

}

boolIsFull()const{returnfalse;}};17template<classT>LinkedQueue<T>::~LinkedQueue(){//析构函数

QueueNode<T>*p;

while(front!=NULL){

//逐个结点释放

p=front;front=front->link;

deletep;}};template<classT>bool

LinkedQueue<T>::EnQueue(Tx){//将新元素x插入到队列的队尾18

if(front==NULL){//创建第一个结点

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

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

else{

//队列不空,插入

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

if(rear->link==NULL)returnfalse;rear=rear->link;}returntrue;};template<classT>//如果队列不空，将队头结点从链式队列中删去

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

if(IsEmpty()==true)returnfalse;//判队空

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

deletep;

returntrue; };template<classT>bool

LinkedQueue<T>::GetFront(T&x){//若队列不空，则函数返回队头元素的值

if(IsEmpty()==true)returnfalse; x=front->data;returntrue;//不改变队头指针};20优先级队列(PriorityQueue)优先级队列每次从队列中取出的是具有最高优先权的元素如下表：任务优先权及执行顺序的关系数字越小，优先权越高21#include<assert.h>#include<iostream.h>#include<stdlib.h>template<classT>classPQueue{private:

T

*pqelements;

//存放数组

intcount;

//队列元素计数

intmaxPQSize;//最大元素个数

voidadjust();

//调整优先级队列的类定义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;//判队满

pqelements[count++]=x;//插入优先级队列部分成员函数的实现24102040507090插入601020405070906060102040507090606090907070601020405060709025

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

T

temp=pqelements[count-1];

//将最后元素暂存再从后向前找插入位置

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号元素

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

//从后向前逐个移动元素填补空位

count--;returntrue;}

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

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

双端队列（Deque）

可以在队列的两端进行插入和删除。普通队列的延伸和拓展

英文全称Double-endedqueue

—————————

→←←

—————————→29

双端队列的函数双端队列提供了三个存取队列头部的函数，包括

boolgetHead(T&x)//读队头元素

boolEnQueueHead(T&x)//在队头插入

boolDeQueueHead(T&x)//删除队头元素三个存取队列尾部的函数，包括

boolgetTail(T&x)//读队尾元素

boolEnQueueTail(T&x)//在队尾插入

boolDeQueueTail(T&x)//删除队尾元素

30

双端队列的基本操作图示

142EnQueueHead(3)3142EnQueueTail(5)31425

DeQueueHead()→31425

Initialization

DeQueueTail()→5142

getHead()→1142

getTail()→2142

31

双端队列的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

双端队列的公共接口在Deque类的公共接口中包括了从基类Queue继承来的EnQueue和DeQueue函数。在基类中，由于数据元素总是在队列尾部进队列，在头部出队列，所以基类仅需要一个进队函数（EnQueue）及一个出队函数（DeQueue）。然而，在双端队列中可在任一端进行进队和出队操作。33Deque类成员函数的实现Deque类提供了EnQueue和Dequeue的默认功能，只不过EnQueue仅仅调用了EnQueueTail函数（在尾部插入），DeQueue函数仅仅调用了DeQueueHead函数（在头部删除）。Deque类成员函数EnQueue的实现

template<classT>

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

return

EnQueueTial(x);};34Deque类成员函数的实现boolDeque<T>::DeQueue(T&x){Ttemp;

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

//其它操作参见教材35队列的其他变形输入受限的双端队列允许在一端进行插入和删除，但在另一端只允许删除的双端队列

—————————

←

←

—————————→输出受限的双端队列允许在一端进行插入和删除，但在另一端只允许插入的双端队列

—————————

→←

—————————→36

双端队列思考设一个双端队列，元素进入该队列的顺序是1，2，3，4，分别求出满足下列条件的输出序列：

1.能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；

2.能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；

3.既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。注：在Knuth的名著中该题难度定为25（难度值从0-50），是推荐题目37继续深入（应该会提出类似的问题）利用双端队列，是否可得到元素的所有排列。是否有这样的排列，它不可能利用一个双端队列得到（既非输入受限也非输出受限）38迷宫问题小型迷宫

路口动作 结果

1

(入口)正向走进到2

2

左拐弯进到3

3

右拐弯进到4

4

(堵死)回溯 退到3

3

(堵死)回溯 退到2

2

正向走进到5

5

(堵死)回溯 退到2

2

右拐弯进到6

6

左拐弯进到7(出口)

4352176

6

左0 直2右0

行3行5行60 040 000 00700

7小型迷宫的数据39迷宫的类定义#include<iostream.h>#include<fstream.h>#include<stdlib.h>classMaze{private:intMazeSize; intEXIT;

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

intTraverseMaze(intCurrentPos);}交通路口结构定义structIntersection{

intleft;

intforward;

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

//构造函数：从文件

filename

中读取各路口

//和出口的数据

ifstreamfin;

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

//为输入打开文件,文件不存在则打开失败

if(!fin){

cerr<<“迷宫数据文件”<<filename

<<“打不开”<<endl;

exit(1);

}

fin>>MazeSize;

//输入迷宫路口数41

intsec=newIntersection[MazeSize+1];

//创建迷宫路口数组

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队列的应用：打印杨辉三角形算法逐行打印二项展开式

(a+b)i

的系数：杨辉三角形(Pascal’striangle)44分析第i行元素与第i+1行元素的关系从前一行的数据可以计算下一行的数据i=2i=3i=401331014641012100110sts+t45从第i行数据计算并存放第i+1行数据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利用队列打印二项展开式系数的算法#include

<stdio.h>#include

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

yanghui(intn){

//分行打印二项式(a+b)n展开式的系数。程序中利用了一个

//队列,在输出上一行系数时,将其下一行的系数预先放入

//队列中。在各行系数之间插入一个0。

Queueq(n+2);

//建立队列对象并初始化

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

//计算下一行系数时用到的

//工作单元

q.EnQueue(i);