数据结构与算法第7讲

第七讲队列本讲知识点：(1)了解各种队列的特点(2)掌握顺序、链式队列的(3)运用队列处理实际问题的能力重点：循环队列的特点及操作难点：队列的实际应用2/46Proc

Demo(var

S2:Seqstack;varS1:Seqstack){

//Seqstack是顺序栈类型Seqstack

tmp;DataType

x;

//DataType是栈中元素的类型Initstack(tmp);Initstack(S2);while(not

stackempty(S1)){

//栈S1非空x=pop(S1);push(tmp,x);}while(not

stackempty(tmp)){x=pop(tmp);push(S1,x);push(S2,x);}}3/46回顾一、队列queue只允许在一端

元素，另一端删除元素的线性表允许

的一端称为队尾(rear)，允许删除的一端称为队头(front)特点：先进先出(FIFO)队尾队头a1

a2

a3

…

…an-1an出队列入队列4/46提出问题三角形（二项式系数）的打印输出11

11

2

110105

1

(a+b)i此三角形的特点是？用二维数组实现的方法是？用一维数组实现的方法是？当i=5时展开的系数5/466/46分析问题void

huiTwo(

)//用二维数组实现{ int

a[101][101],

i,

j,

n;

cin>>n;for(

i=1;

i<=n;

i++

){

a[i][1]=1;

a[i][i]=1;

}for(

i=2;

i<=n;i++)for(j=2;j<i;

j++

)a[i][j]=a[i-1][j-1]+a[i-1][j];for(

i=1;

i<=n;

i++

){ for(

j=1;j<=i;

j++

)cout<<a[i][j]<<“

”;cout<<endl;}}参见hui/hui2.cpp7/46分析问题void huiOne(

)//用一维数组实现

cin>>n;{ int

a[101],

i,

j,

n;a[1]=1;cout<<“1”<<endl;for(

i=2;

i<=n;i++){

a[i]=1;for(

j=i-1;

j>=2;

j--

)a[j]

=

a[j-1]+a[j];for(j=1;j<=i;j++)cout<<a[j]<<“

”;cout<<endl;}}参见hui/hui1.cpp8/46例如：显示二项式的系数用队列实现(a+b)ii=111i=2121i=31331i=414641i=515101051i=61615201561参见hui/

hui3.cpp19/46s=1

t=1

s+t21例如：显示二项式的系数用队列实现例如：显示二项式的系数110/46s=1t=2s=t

t=13s+t3s+t1用队列实现例如：显示二项式的系数111/46s=1t=3s=t

t=3s=t

t=14s+t6s+ts+t41用队列实现template<class

ElemType>class{protected://

顺序栈的数据成员:intc

元int

maxSize;

//栈最大元素个数ElemType

*elems;

//

元素 空间//辅助函数bool

Full()

const;void

Init(int

size);//判断栈是否已满//初始化栈解决问题S

ueuefront,

rear;

//队头和队尾标记用顺序队列实现12/4613/46初始化顺序队列maxSize

=

size;elems

=

new

ElemType[maxSize];front

=

rear

=

0;rearmaxSizeelemselems[0]........elems[9]010front0解决问题front

rear

空队列front

rear

A入队用顺序队列实现Afront

rear

B入队A

BA

B

C

Dfront

rear

C,D入队14/46入队执行的语句是？顺序队列的入队操作先判断队列是否已满调用Full()函数判断即可具体看：长度==maxsize-1?长度：Length()return

rear-front;然队：elems[rear]=e;rear++;15/46解决问题B

C

Dfront

rear

B出队C

Dfront

rear

A出队C

D

E

F

Gfront

rear

E,F,G入队C

D

E

F

Gfront

rearH入队,溢出16/46用顺序队列实现出队执行的语句是？17/46顺序队列的出队操作先判断队列是否为空调用Empty()函数判断即可具体看：长度==0?长度：Length()return

rear-front;然后出队：e=elems[front];front++;顺序结构下的空间浪费问题重现！解决办法之一：将队列元素存放数组首尾相接，形成循环(环形)队列。二、循环队列04567

frontrear3

2空队列1

456A

03

2A入队21

4rear57

front

67

frontA

0B

1Crear

3B,

C入队18/46入队语句要如何调整?解决办法之一：将队列元素存放数组首尾相接，形成循环(环形)队列。二、循环队列256front4rear

30B

1C015

57

6

7

6

7A

0BC

1

4rear

3

2

front

2

frontrearD

C19/464

E3FG

HIA出队

B出队

D,E,F,G,H,I入队出队语句调整：(rear+1)%maxsize01356

72

frontrear4

ED

C20/46FG

HI二、循环队列J入队，则队满有什么疑问？解决方法：另设一个标识符或count统计。少用一个元素空间，约定队头在队尾指针的下一个位置时作为队满的标志。21/46小结：队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%maxSize==front接下来：解决问题二、循环队列2/46huiTree()void{Sueue<int>

tmpQ; int

n,

s,

t;cin>>n;tmpQ.InQueue(1);

tmpQ.InQueue(1);cout<<1<<“\t”<<1;for(inti=2;

i<=n;

i++){cout<<endl;tmpQ.InQueue(1);cout<<1<<“\t”;tmpQ.OutQueue(s);for(int

j=2;

j<=i;

j++){tmpQ.OutQueue(t);tmpQ.InQueue(s+t);cout<<s+t<<“\t”;s=t;}tmpQ.InQueue(1);cout<<1;}cout<<endl;}三、双端队列deque和删除限定

性表的两端进行的线性表a1a2anan-1……删除删除23/46三、双端队列输入（出）受限的双端队列：允许在一端进行和删除，在另一端只允许进行删除（

）。a1a2anan-1……删除删除a1a2anan-1……删除24/4625/461:已知输入序列为abcd经过输出受限的双端队列后能得到的输出序列有(

)A.dacb

B.cadb

C.dbca

D.bdac2:若以1234作为双端序列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是(

)A.1234

B.4132

C.4231

D.4213课堂实战链队列frontrear思考：链队列的入队、出队、队满、队空操作四、链队列topan

an-1

an-2a1链栈的入栈、出栈均在top位置26/46template<class

ElemType>class{protected://

链栈的数据成员:Node<ElemType>27/46//辅助函数void

Init();//初始化栈LinkQueue*front,

*rear;四、链队列例如：解决计算机主机与外设不匹配的问题；解决由于多用户引起的资源竞争问题；离散事件的模拟----模拟实际应用中的各种排队现象；用于处理程序中具有先进先出特征的过程；但是：看病的优先权更高Vip客户先服务系统功能要求进程先执行等队列的应用28/46最小优先队列：出队操作删除最小的数据元素值，入队时需按从小到大最大优先队列：出队操作删除最大的数据元素值，入队时需按从大到小简单实现方法：入队时不排在队尾，而是插入在队列的适当位置，是队列的元素有序。从队列类派生，重载入队操作即可。五、优先队列priority

queue29/46emType

&e);template<class

ElemType>class

MinPriorityLinkQueue:

publicLinkQueue<ElemType>{

public:StatusCode

InQueue(cons//重载入队操作};template<class

ElemType>StatusCodeMinPriorityLinkQueue<ElemType>::InQueue(constElemType

&e){ …

…

}30/46参见test_min_priority_lk_queue类实现31/46事件驱动模拟一个系统模拟另一个系统行为的技术称为模拟技术。银行业务模拟：假设某个银行有3个窗口对外接待客户。客户在人数多时需在窗口前顺序排队。刚进入的客户，发现某个窗口空闲，可办理业务。若3个窗口都有客户在办业务，则需排在人数最少的队列后面。设计程序模拟银行业务并计算一天中所有客户在银行停留的平均时间。提出问题平均时间等于每一客户离开时间减去到达时间再除以总客户数目。事件分为两类：事件0：客户到达事件事件1-3：客户离开事件（窗口1,2,3）struct

EventType32/46{ intoccurTime;int

eventType;//事件//事件发生时刻//事件类型，0~4};分析问题优先队列：模拟客户在银行窗口排队任何时刻发生的事件：客户达到事件1号窗口客户离开事件2号窗口客户离开事件3号窗口客户离开事件struct

QElemType33/46{ intarrivalTime;int

duration;//窗口队列中数据元素类型//客户到达时刻//客户办理业务需要的时间};分析问题class

BankSimulation{protected://

模拟类的数据成员:MinPriorityLinkQueue<EventType>

evPQ;//事件优先队列LinkQueue<QElemType>windowsQ[WINDOWS_NUM+1];

//窗口队列int

totalTime;

//累计客户停留时间int

customerNum;

//客户数int

aveDuration;

//办理业务所需平均时间int

aveInterTime;//两个相邻客户到达银行的平均时间间隔int

closeTime;

//银行关门时刻34/46银行业务模拟类windowsQ初始状态evPQ∧∧∧ev.occurTime=0;ev.eventType=0;evPQ.InQueue(ev);evPQ.OutQueue(ev);0类型为到达事件∧35/46windowsQ∧∧evPQ0为到达事件，生成2个随机数

durTime=16;

该到达的客户需要的时长interTime=2;下一客户发生时刻0+2， 优先队列发生时刻2到达事件0016∧客户到达时间0办理需要时间1620∧36/46windowsQ∧∧evPQ20016∧161∧客户排在1号窗口的队头，生成一个离开事件occurTime=0+16eventType=116,1

入队！37/46发生时刻161号窗口离开事件windowsQ∧∧evPQ016∧38/46161∧evPQ.OutQueue(ev);2,0

0为到达事件，生成2个随机数durTime=18

interTime=3下一客户到达事件2+3，0

入队39/46windowsQ∧evPQ50016∧161第2个客户排在第2个窗口到达时间2，处理需要时长18客户排在2号窗口的队头，生成一个离开事件occurTime=2+18

eventType=220,2

入队！218∧202∧40/46windowsQevPQ016∧161218∧202∧evPQ.OutQueue(ev);5,0

0为到达事件，生成2个随机数durTime=15

interTime=6下一客户到达事件5+6，0

入队第