资源描述：
《深入JAVA编程之算法及数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、深入Java编程专业教程理论讲解部分Ver3.1第022课算法及数据结构概述：队列的概念队列的实现重点：难点：队列的实现队列的实现5队列队列提供了一种“先入先出”的一种数据结构队列是一块连续的(物理的或者逻辑的)存储区域.有两个标识标志出栈的两个端点–头和尾.堆栈需要提供2个最基本的操作入队(offer)和出队(poll)第022课算法及数据结构第022课算法及数据结构下面我们以一个数组实现的循环队列为例,进行队列的讲解.什么是循环队列循环队列就是反复的利用同一块存储空间进行队列的移动.这种队列的好处,是不需要队列的整理.可以提高队列效率.是将数组的首尾相连,使移动到末端的队列仍
2、旧可以继续爬行到数组的头部.5队列5.1队列的初始化在进行具体的初始化之前,我们需要明确,如何实现队列在存储空间尾部可以自然的移动到存储空间头部.队列的移动主要依靠两个变量来指示,headend.队列的移动方向定义为正方向.当head向正方向移动时,队列向着正方向减少.当end向正方向移动时,队列向着正方向增长.endheadendheadendhead第022课算法及数据结构初始状态入队出队5队列当队列移动到存储空间边缘时会发生什么?endhead此时end将增加到什么地方?endhead第022课算法及数据结构将end移动到数组头部.head也是同样的道理5.1队列的初始化5
3、队列第022课算法及数据结构因为headend都需要有这样的移动规则,所以给出一个next()方法来取得移动后的位置.privateintnext(inti){return(i+1)%SIZE;}5.1队列的初始化5队列下面我们来实现一个最简单的循环队列.privatefinalintSIZE;privateint[]queue;privateinthead;privateintend;其中,SIZE是数组得大小.当这个队列被创建后其大小不会改变,所以我们定义它为final(不会改变得变量).queue[]是存储数据的数组.head标识着队列的队首,也就是队列中的第一个元素.en
4、d标识着队列尾部,它是第一个未被使用的空间.第022课算法及数据结构5.1队列的初始化5队列当这个队列被初始化之后,如图SIZE=size;queue=newint[SIZE];head=0;end=0;初始化代码如下:其中,size为初始化参数.可以当作已知量.第022课算法及数据结构endhead0SIZE5.1队列的初始化5队列一个栈被建立,我们需要在任意时刻需要了解到它得情况,比如是否为空.队列是否为空主要依靠head与end的位置关系.publicbooleanisEmpty(){returnend==head;}无论head与end在什么位置,当head==end时,
5、此时队列为空,否则队列非空.第022课算法及数据结构5.2队列空的判断5队列第022课算法及数据结构endhead0SIZE空栈非空栈endhead0SIZE5.2队列空的判断5队列同样,我们还需要在任何时刻需要判断栈是否为满栈.publicbooleanisFull(){returnnext(end)==head;}当head前进的速度大于end的前进速度,直到head如果再前进就把end覆盖的时候,此时队列就满了.当next(end)==head时,此时栈为满,否则栈不满.第022课算法及数据结构5.3队列满的判断5队列第022课算法及数据结构endhead0SIZE满栈非满
6、栈endhead0SIZE5.3队列满的判断5队列将数据存储到队列中叫入队.入队的数据只能在当前的队尾之后添加.下面我们来看看入队的实现.publicvoidoffer(intdata)throwsException{if(isFull()){thrownewException("queueisfull");}else{queue[end]=data;end=next(end);}}第022课算法及数据结构5.4入队5队列这里我们要注意入队的步骤:1.需要判断栈是否是满队,如果队满,那么返回一个异常说明队已经满了.无法在使其它元素入队.如果栈非满,那么继续.2.将数据存储到end
7、指向的空间.由于end始终指向第一个未使用的空间.所以可以将数据存储进去.3.调用next()得到end的下一个位置并赋值.注意,第2步与第3步千万不能颠倒.否则会引起栈的存储异常.第022课算法及数据结构5.4入队5队列第022课算法及数据结构endhead0SIZEendhead0SIZEendhead0SIZE1.检查是否是满队2.数据加入到end所指向的位置3.将end向正方向移动5.4入队5队列当需要从队列中取出数据时,只能从队列首部取出,这个动作叫出队.我们来看看po
