深入JAVA编程之算法及数据结构课件

深入Java编程专业教程理论讲解部分Ver3.1深入Java编程专业教程理论讲解部分Ver3.11第022课算法及数据结构概述：

队列的概念队列的实现重点：难点：

队列的实现

队列的实现第022课算法及数据结构概述：队列的概念重点：难点25队列队列提供了一种“先入先出”的一种数据结构

队列是一块连续的(物理的或者逻辑的)存储区域.有两个标识标志出栈的两个端点–头和尾.堆栈需要提供2个最基本的操作入队(offer)和出队(poll)第022课算法及数据结构5队列队列提供了一种“先入先出”的一种数据结构队列3第022课算法及数据结构下面我们以一个数组实现的循环队列为例,进行队列的讲解.什么是循环队列循环队列就是反复的利用同一块存储空间进行队列的移动.这种队列的好处,是不需要队列的整理.可以提高队列效率.

是将数组的首尾相连,使移动到末端的队列仍旧可以继续爬行到数组的头部.5队列第022课算法及数据结构下面我们以一个数组实现的循环队列45.1队列的初始化

在进行具体的初始化之前,我们需要明确,如何实现队列在存储空间尾部可以自然的移动到存储空间头部.

队列的移动主要依靠两个变量来指示,headend.队列的移动方向定义为正方向.当head向正方向移动时,队列向着正方向减少.当end向正方向移动时,队列向着正方向增长.endheadendheadendhead第022课算法及数据结构初始状态入队出队5队列5.1队列的初始化在进行具体的初始化之前,我们需要5当队列移动到存储空间边缘时会发生什么?endhead此时end将增加到什么地方?endhead第022课算法及数据结构将end移动到数组头部.head也是同样的道理5.1队列的初始化5队列当队列移动到存储空间边缘时会发生什么?endhead此时en6第022课算法及数据结构

因为headend都需要有这样的移动规则,所以给出一个next()方法来取得移动后的位置.privateintnext(inti){ return(i+1)%SIZE;}5.1队列的初始化5队列第022课算法及数据结构因为headend都需7下面我们来实现一个最简单的循环队列.privatefinalintSIZE;privateint[]queue;privateinthead;privateintend;

其中,SIZE是数组得大小.当这个队列被创建后其大小不会改变,所以我们定义它为final(不会改变得变量).queue[]是存储数据的数组.head标识着队列的队首,也就是队列中的第一个元素.end标识着队列尾部,它是第一个未被使用的空间.第022课算法及数据结构5.1队列的初始化5队列下面我们来实现一个最简单的循环队列.privatefina8当这个队列被初始化之后,如图SIZE=size;queue=newint[SIZE];head=0;end=0;初始化代码如下:其中,size为初始化参数.可以当作已知量.第022课算法及数据结构

endhead0SIZE5.1队列的初始化5队列当这个队列被初始化之后,如图SIZE=size;初始化代9一个栈被建立,我们需要在任意时刻需要了解到它得情况,比如是否为空.队列是否为空主要依靠head与end的位置关系.publicbooleanisEmpty(){ returnend==head;}无论head与end在什么位置,当head==end时,此时队列为空,否则队列非空.第022课算法及数据结构5.2队列空的判断5队列一个栈被建立,我们需要在任意时刻需要了解到它得情况,比如是否10第022课算法及数据结构

endhead0SIZE空栈非空栈

endhead0SIZE5.2队列空的判断5队列第022课算法及数据结构11同样,我们还需要在任何时刻需要判断栈是否为满栈.publicbooleanisFull(){ returnnext(end)==head;}当head前进的速度大于end的前进速度,直到head如果再前进就把end覆盖的时候,此时队列就满了.当next(end)==head时,此时栈为满,否则栈不满.第022课算法及数据结构5.3队列满的判断5队列同样,我们还需要在任何时刻需要判断栈是否为满栈.public12第022课算法及数据结构

endhead0SIZE满栈非满栈

endhead0SIZE5.3队列满的判断5队列第022课算法及数据结构13将数据存储到队列中叫入队.入队的数据只能在当前的队尾之后添加.下面我们来看看入队的实现.publicvoidoffer(intdata)throwsException{ if(isFull()){ thrownewException("queueisfull"); }else{ queue[end]=data; end=next(end); }}第022课算法及数据结构5.4入队5队列将数据存储到队列中叫入队.入队的数据只能在当前的队尾之后添加14这里我们要注意入队的步骤:1.需要判断栈是否是满队,如果队满,那么返回一个异常说明队已经满了.无法在使其它元素入队.如果栈非满,那么继续.2.将数据存储到end指向的空间.由于end始终指向第一个未使用的空间.所以可以将数据存储进去.3.调用next()得到end的下一个位置并赋值.注意,第2步与第3步千万不能颠倒.否则会引起栈的存储异常.第022课算法及数据结构5.4入队5队列这里我们要注意入队的步骤:1.需要判断栈是否是满队,如果队满15第022课算法及数据结构

endhead0SIZE

endhead0SIZE

endhead0SIZE1.检查是否是满队2.数据加入到end所指向的位置3.将end向正方向移动5.4入队5队列第022课算法及数据结构16当需要从队列中取出数据时,只能从队列首部取出,这个动作叫出队.我们来看看poll如何实现.publicintpoll()throwsException{ if(isEmpty()){ thrownewException("queueisempty"); }else{ intresult=queue[head]; head=next(head); returnresult; }}第022课算法及数据结构5.5出队5队列当需要从队列中取出数据时,只能从队列首部取出,这个动作叫出队17这里我们要注意出队的步骤:1.需要判断队是否是空队,如果队空,那么返回一个异常说明队已经空了.无法弹出.如果队非空,那么继续.3.调用next()求出head得下一个位置然后移动.2.将head指向元素保存等待返回.注意,第2步与第3步千万不能颠倒.否则会引起队列的存储异常.第022课算法及数据结构4.返回保存元素.5.5出队5队列这里我们要注意出队的步骤:1.需要判断队是否是空队,如果队空18第022课算法及数据结构

endhead0SIZE

endhead0SIZE

endhead0SIZE1.检查是否是空队2.将head指向元素保存3.head向正方向移动5.5出队5队列第022课算法及数据结构19下面给出程序的完整代码,及必要注释.第022课算法及数据结构publicclassMyQueue{ privatefinalintSIZE; privateint[]queue; privateinthead; privateintend; publicMyQueue(intsize){ super(); SIZE=size; queue=newint[SIZE]; head=0; end=0; }队列所需要的空间及标志构造函数,当该类被实例化后,一个队列就创建了.5队列下面给出程序的完整代码,及必要注释.第022课算法及数据20privateintnext(inti){ return(i+1)%SIZE;}publicbooleanisFull(){ returnnext(end)==head;}publicvoidoffer(intdata)throwsException{ if(isFull()){ thrownewException("queueisfull"); }else{ queue[end]=data; end=next(end); }}第022课算法及数据结构5队列privateintnext(inti){第022课21publicintpoll()throwsException{ if(isEmpty()){ thrownewException("queueisempty"); }else{ intresult=queue[head]; head=next(head); returnresult; }}publicintsize(){ return((end+SIZE)-head)%SIZE;}publicbooleanisEmpty(){ returnend==head;}第022课算法及数据结构求出队列得大小5队列publicintpoll()throwsExcep22小结：

队列的定义满队的条件空队的条件入队的操作顺序出队的操作顺序第022课算法及数据结构队列的定义第022课算法及数据结构231、队列是一种()的存储结构

A)先进先出B)后进先出C)先进后出D)任意进出2、判断队列空的条件是()A)head==endB)head==next(end)C)head==SIZED)end==03、判断队列满的条件是()

A)head==endB)head==next(end)C)head==SIZED)end==04、入队的顺序()A)next(end)B)判断队空C)判断队满D)数据写入end指向的位置5、出队的顺序()A)next(head)B)判断队空C)判断队满D)读出head指向的位置小测验（单选题）：第022课算法及数据结构1、队列是一种()的存储结构小测验（单选题）：第022课241、队列是一种(a)的存储结构

A)先进先出B)后进先出C)先进后出D)任意进出2、判断队列空的条件是(A)A)head==endB)head==next(end)C)head==SIZED)end==03、判断队列满的条件是(B)

A)head==endB)head==next(end)C)head==SIZED)end==04、入队的顺序(CDA)A)next(end)B)判断队空C)判断队满D)数据写入end指向的位置5、出队的顺序(BAD)A)next(head)B)判断队空C)判断队满D)读出head指向的位置小测验（单选题答案）：第022课算法及数据结构1、队列是一种(a)的存储结构小测验（单选题答案）：第02225使用队列实现一个模拟饭店排队现象.

定时产生一个1-4随机数表示来的人数,然后使其进入队列.另一方面从队列中找出队首进行处理.课后作业：第022课算法及数据结构使用队列实现一个模拟饭店排队现象.课后作业：第022课算26深入Java编程专业教程理论讲解部分Ver3.1深入Java编程专业教程理论讲解部分Ver3.127第022课算法及数据结构概述：

队列的概念队列的实现重点：难点：

队列的实现

队列的实现第022课算法及数据结构概述：队列的概念重点：难点285队列队列提供了一种“先入先出”的一种数据结构

队列是一块连续的(物理的或者逻辑的)存储区域.有两个标识标志出栈的两个端点–头和尾.堆栈需要提供2个最基本的操作入队(offer)和出队(poll)第022课算法及数据结构5队列队列提供了一种“先入先出”的一种数据结构队列29第022课算法及数据结构下面我们以一个数组实现的循环队列为例,进行队列的讲解.什么是循环队列循环队列就是反复的利用同一块存储空间进行队列的移动.这种队列的好处,是不需要队列的整理.可以提高队列效率.

是将数组的首尾相连,使移动到末端的队列仍旧可以继续爬行到数组的头部.5队列第022课算法及数据结构下面我们以一个数组实现的循环队列305.1队列的初始化

在进行具体的初始化之前,我们需要明确,如何实现队列在存储空间尾部可以自然的移动到存储空间头部.

队列的移动主要依靠两个变量来指示,headend.队列的移动方向定义为正方向.当head向正方向移动时,队列向着正方向减少.当end向正方向移动时,队列向着正方向增长.endheadendheadendhead第022课算法及数据结构初始状态入队出队5队列5.1队列的初始化在进行具体的初始化之前,我们需要31当队列移动到存储空间边缘时会发生什么?endhead此时end将增加到什么地方?endhead第022课算法及数据结构将end移动到数组头部.head也是同样的道理5.1队列的初始化5队列当队列移动到存储空间边缘时会发生什么?endhead此时en32第022课算法及数据结构

因为headend都需要有这样的移动规则,所以给出一个next()方法来取得移动后的位置.privateintnext(inti){ return(i+1)%SIZE;}5.1队列的初始化5队列第022课算法及数据结构因为headend都需33下面我们来实现一个最简单的循环队列.privatefinalintSIZE;privateint[]queue;privateinthead;privateintend;

其中,SIZE是数组得大小.当这个队列被创建后其大小不会改变,所以我们定义它为final(不会改变得变量).queue[]是存储数据的数组.head标识着队列的队首,也就是队列中的第一个元素.end标识着队列尾部,它是第一个未被使用的空间.第022课算法及数据结构5.1队列的初始化5队列下面我们来实现一个最简单的循环队列.privatefina34当这个队列被初始化之后,如图SIZE=size;queue=newint[SIZE];head=0;end=0;初始化代码如下:其中,size为初始化参数.可以当作已知量.第022课算法及数据结构

endhead0SIZE5.1队列的初始化5队列当这个队列被初始化之后,如图SIZE=size;初始化代35一个栈被建立,我们需要在任意时刻需要了解到它得情况,比如是否为空.队列是否为空主要依靠head与end的位置关系.publicbooleanisEmpty(){ returnend==head;}无论head与end在什么位置,当head==end时,此时队列为空,否则队列非空.第022课算法及数据结构5.2队列空的判断5队列一个栈被建立,我们需要在任意时刻需要了解到它得情况,比如是否36第022课算法及数据结构

endhead0SIZE空栈非空栈

endhead0SIZE5.2队列空的判断5队列第022课算法及数据结构37同样,我们还需要在任何时刻需要判断栈是否为满栈.publicbooleanisFull(){ returnnext(end)==head;}当head前进的速度大于end的前进速度,直到head如果再前进就把end覆盖的时候,此时队列就满了.当next(end)==head时,此时栈为满,否则栈不满.第022课算法及数据结构5.3队列满的判断5队列同样,我们还需要在任何时刻需要判断栈是否为满栈.public38第022课算法及数据结构

endhead0SIZE满栈非满栈

endhead0SIZE5.3队列满的判断5队列第022课算法及数据结构39将数据存储到队列中叫入队.入队的数据只能在当前的队尾之后添加.下面我们来看看入队的实现.publicvoidoffer(intdata)throwsException{ if(isFull()){ thrownewException("queueisfull"); }else{ queue[end]=data; end=next(end); }}第022课算法及数据结构5.4入队5队列将数据存储到队列中叫入队.入队的数据只能在当前的队尾之后添加40这里我们要注意入队的步骤:1.需要判断栈是否是满队,如果队满,那么返回一个异常说明队已经满了.无法在使其它元素入队.如果栈非满,那么继续.2.将数据存储到end指向的空间.由于end始终指向第一个未使用的空间.所以可以将数据存储进去.3.调用next()得到end的下一个位置并赋值.注意,第2步与第3步千万不能颠倒.否则会引起栈的存储异常.第022课算法及数据结构5.4入队5队列这里我们要注意入队的步骤:1.需要判断栈是否是满队,如果队满41第022课算法及数据结构

endhead0SIZE

endhead0SIZE

endhead0SIZE1.检查是否是满队2.数据加入到end所指向的位置3.将end向正方向移动5.4入队5队列第022课算法及数据结构42当需要从队列中取出数据时,只能从队列首部取出,这个动作叫出队.我们来看看poll如何实现.publicintpoll()throwsException{ if(isEmpty()){ thrownewException("queueisempty"); }else{ intresult=queue[head]; head=next(head); returnresult; }}第022课算法及数据结构5.5出队5队列当需要从队列中取出数据时,只能从队列首部取出,这个动作叫出队43这里我们要注意出队的步骤:1.需要判断队是否是空队,如果队空,那么返回一个异常说明队已经空了.无法弹出.如果队非空,那么继续.3.调用next()求出head得下一个位置然后移动.2.将head指向元素保存等待返回.注意,第2步与第3步千万不能颠倒.否则会引起队列的存储异常.第022课算法及数据结构4.返回保存元素.5.5出队5队列这里我们要注意出队的步骤:1.需要判断队是否是空队,如果队空44第022课算法及数据结构

endhead0SIZE

endhead0SIZE

endhead0SIZE1.检查是否是空队2.将head指向元素保存3.head向正方向移动5.5出队5队列第022课算法及数据结构45下面给出程序的完整代码,及必要注释.第022课算法及数据结构publicclassMyQueue{ privatefinalintSIZE; privateint[]queue; privateinthead; privateintend; publicMyQueue(intsize){ super(); SIZE=size; queue=newint[SIZE]; head=0; end=0; }队列所需要的空间及标志构造函数,当该类被实例化后,一个队列就创建了.5队列下面给出程序的完整代码,及必要注释.第022课算法及数据46privateintnext(inti){ return(i+1)%SIZE;}publicbooleanisFull(){ returnnext(end)==head;}publicvoidoffer(intdata)throwsException{ if(isFull()){ thrownewException("queueisfull"); }else{ queue[end]=data; end=next(end); }}第022课算法及数据结构5队列privateintnext(inti){第022课47publicintpoll()throwsException{ if(isEmpty()){ thrownewException("queueisempty"); }else{ intresult=queue[head]; head=next(head); returnresult; }}publicintsize(){ return((end+SIZE)-head)%SIZE;}publicbooleanisEmpty(){ returnend==head;