045046数据结构和算法的Java实现栈队列课件.ppt

1、2006Java高级程序设计高级程序设计专业教程专业教程理论讲解部分理论讲解部分 2006课程概述课程概述栈队列重点重点栈队列难点难点栈队列学习目标学习目标掌握栈使用掌握队列的使用2006 栈只允许访问一个数据项：即最后插入的数据项。移除这个数据项后才能访问倒数第二个插入的数据项，依此类推。这种机制在不少编程环境中都很有用。栈提供了一种“后入先出”的一种数据结构 栈是一块连续的(物理的或者逻辑的)存储区域.有两个标识标志出栈的两个端点 栈底和栈顶.栈需要提供2个最基本的操作压入(push)和弹出(pop)6.4 堆栈2006下面我们用一个数组来实现一个最简单的栈.private int sta

2、ck;但是,只有一个数组还无法实现栈得功能,我们还需要一些标识.private final int SIZE;private final int BOTTOM=0;private int top;其中,SIZE是数组得大小,栈得大小要比数组得小1个,随后我们会解释原因.当这个栈被创建后其大小不会改变,所以我们定义它为final(不会改变得变量).BOTTOM标识着这个栈得栈底,它始终为数组得第一个元素,所以为final得0.top标识着这个栈得栈顶,它会随着栈得使用变化.6.4 堆栈2006初始化栈初始化栈BOTTOMtop0SIZE当这个栈被初始化之后,如图SIZE=size;stack=n

3、ew intSIZE;top=BOTTOM;初始化代码如下:其中,size为初始化参数.可以当作已知量.6.4 堆栈2006栈被初始化时有一下几点:2.栈底通常定义于存储空间得一段,而且通常是固定得.1.存储空间得初始化.如果是动态的仅仅需要得到其大小及初始空间得创建.3.令栈顶指向栈底.这里我们只需令top=BOTTOM;此时,一个空栈被创建.6.4 堆栈2006一个栈被建立,我们需要在任意时刻需要了解到它得情况,比如是否为空.下面我们来看看如何判断一个栈是否为空.public boolean isEmpty()if(top!=BOTTOM)return false;elsereturn t

4、rue;判断得依据是依靠判断top与BOTTOM的关系.当top=BOTTOM时,此时栈为空,否则栈非空.6.4 堆栈2006空栈空栈BOTTOMtop0SIZE12BOTTOMtopSIZE0非空栈非空栈6.4 堆栈2006同样,我们还需要在任何时刻需要判断栈是否为满栈.public boolean isFull()if(top!=SIZE)return false;elsereturn true;判断得依据是依靠判断top与SIZE的关系.当top=SIZE时,此时栈为满,否则栈不满.6.4 堆栈2006空栈空栈1234567BOTTOM0SIZE12BOTTOMtopSIZE0非空栈非空

5、栈top注意注意:这里需要声明一点,top指向的是下一个将要使用的空间.为了数组的安全,不至越界.通常top=SIZE定义为满栈.这就是为什么栈的空间比数组的小的原因.6.4 堆栈2006栈是要用来存储数据的,数据被存储到栈中,这个动作叫入栈或者压栈.下面我们来看看压栈的实现.public synchronized void push(int data)throws IllegalStateExceptionif(!isFull()stacktop+=data;elsethrow new IllegalStateException(Stack is overload.);6.4 堆栈2006这

6、里我们要注意入栈的步骤:1.需要判断栈是否是满栈,如果栈满,那么返回一个异常说明栈已经满了.无法在使其它元素入栈.如果栈非满,那么继续.2.将数据存储到top指向的空间.由于top始终指向第一个未使用的空间.所以可以将数据存储进去.3.将top向栈底反向移动一个单位.注意,第2步与第3步千万不能颠倒.否则会引起栈的存储异常.6.4 堆栈2006123BOTTOMtopSIZE0第第3步步123BOTTOMtopSIZE0第第2步步第第1步步判断12BOTTOMtopSIZE0将3写入top指向位置top+6.4 堆栈2006当需要从栈中取出数据时,只能从栈顶取出,这个动作叫出栈.我们来看看po

7、p如何实现.public synchronized int pop()throws IllegalStateExceptionif(!isEmpty()return stack-top;elsethrow new IllegalStateException(Stack is empty.);6.4 堆栈2006这里我们要注意出栈的步骤:1.需要判断栈是否是空栈,如果栈空,那么返回一个异常说明栈已经空了.无法弹出.如果栈非空,那么继续.3.将top指向的数据返回.栈空间中的数据实际上是没有被删除的,但是对于栈来说,该数据已经没有任何意义.当下一次使用该空间时,它会被当作空,由新的数据覆盖掉.2.

8、将top向栈底方向移动一个单位.注意,第2步与第3步千万不能颠倒.否则会引起栈的存储异常.6.4 堆栈200612345BOTTOMtopSIZE0第第3步步12345BOTTOMtopSIZE0第第2步步第第1步步判断12345BOTTOMtopSIZE0top-将top指向内容返回6.4 堆栈2006 细心的同学会注意到,在push()pop()方法中都使用了synchronized 关键字.这是为了使入栈与出栈操作原子化,就是说在入栈与出栈的操作过程中是不允许其它操作干扰的.有了同步的保障,栈的工作才不会出现异常.下面给出程序的完整代码,及必要注释.6.4 堆栈2006public cl

9、ass MyStack private int stack;private final int SIZE;private final int BOTTOM=0;private int top;public MyStack(int size)super();SIZE=size;stack=new intSIZE;top=BOTTOM;栈所需要的空间及标志构造函数,当该类被实例化后,一个栈就创建了.2006public synchronized void push(int data)throws IllegalStateExceptionif(!isFull()stacktop+=data;els

10、ethrow new IllegalStateException(Stack is overload.);public synchronized int pop()throws IllegalStateExceptionif(!isEmpty()return stack-top;elsethrow new IllegalStateException(Stack is empty.);6.4 堆栈2006public boolean isEmpty()if(top!=BOTTOM)return false;elsereturn true;public boolean isFull()if(top

11、!=SIZE)return false;elsereturn true;6.4 堆栈2006public static void main(String args)MyStack ms=new MyStack(20);ms.push(1);ms.push(2);ms.push(3);System.out.println(1th pop:+ms.pop();ms.push(4);for(int i=0;ims.stack.length;i+)System.out.println(ms.stacki);main()函数,这里定义了一个名为ms的栈,然后将1,2,3分别入栈,之后作了一个出栈操作,最

12、后又将4入栈.程序的末尾检查了一下栈的存储情况.6.4 堆栈2006队列提供了一种“先入先出”的一种数据结构 队列是一块连续的(物理的或者逻辑的)存储区域.有两个标识标志出栈的两个端点 头和尾.堆栈需要提供2个最基本的操作入队(offer)和出队(poll)6.5 队列2006下面我们以一个数组实现的循环队列为例,进行队列的讲解.什么是循环队列循环队列就是反复的利用同一块存储空间进行队列的移动.这种队列的好处,是不需要队列的整理.可以提高队列效率.是将数组的首尾相连,使移动到末端的队列仍旧可以继续爬行到数组的头部.6.5 队列2006 在进行具体的初始化之前,我们需要明确,如何实现队列在存储空

13、间尾部可以自然的移动到存储空间头部.队列的移动主要依靠两个变量来指示,head end.队列的移动方向定义为正方向.当head向正方向移动时,队列向着正方向减少.当end向正方向移动时,队列向着正方向增长.endheadendheadendhead初始状态入队出队6.5 队列2006当队列移动到存储空间边缘时会发生什么?endhead此时end将增加到什么地方?endhead将end移动到数组头部.head也是同样的道理6.5 队列2006 因为head end都需要有这样的移动规则,所以给出一个next()方法来取得移动后的位置.private int next(int i)return(i

14、+1)%SIZE;6.5 队列2006下面我们来实现一个最简单的循环队列.private final int SIZE;private int queue;private int head;private int end;其中,SIZE是数组得大小.当这个队列被创建后其大小不会改变,所以我们定义它为final(不会改变得变量).queue是存储数据的数组.head标识着队列的队首,也就是队列中的第一个元素.end标识着队列尾部,它是第一个未被使用的空间.6.5 队列2006当这个队列被初始化之后,如图SIZE=size;queue=new intSIZE;head=0;end=0;初始化代码如

15、下:其中,size为初始化参数.可以当作已知量.endhead0SIZE6.5 队列2006一个队列被建立,我们需要在任意时刻需要了解到它得情况,比如是否为空.队列是否为空主要依靠head与end的位置关系.public boolean isEmpty()return end=head;无论head与end在什么位置,当head=end时,此时队列为空,否则队列非空.6.5 队列2006 endhead0SIZE空栈非空栈 endhead0SIZE6.5 队列2006同样,我们还需要在任何时刻需要判断栈是否为满栈.public boolean isFull()return next(end)=

16、head;当head前进的速度大于end的前进速度,直到head如果再前进就把end覆盖的时候,此时队列就满了.当next(end)=head时,此时栈为满,否则栈不满.6.5 队列2006 end head0SIZE满栈非满栈 endhead0SIZE6.5 队列2006将数据存储到队列中叫入队.入队的数据只能在当前的队尾之后添加.下面我们来看看入队的实现.public void offer(int data)throws Exceptionif(isFull()throw new Exception(queue is full);elsequeueend=data;end=next(end

17、);6.5 队列2006这里我们要注意入队的步骤:1.需要判断栈是否是满队,如果队满,那么返回一个异常说明队已经满了.无法在使其它元素入队.如果栈非满,那么继续.2.将数据存储到end指向的空间.由于end始终指向第一个未使用的空间.所以可以将数据存储进去.3.调用next()得到end的下一个位置并赋值.注意,第2步与第3步千万不能颠倒.否则会引起栈的存储异常.6.5 队列2006 endhead0SIZE endhead0SIZE endhead0SIZE1.检查是否是满队2.数据加入到end所指向的位置3.将end向正方向移动6.5 队列2006当需要从队列中取出数据时,只能从队列首部取

18、出,这个动作叫出队.我们来看看poll如何实现.public int poll()throws Exceptionif(isEmpty()throw new Exception(queue is empty);elseint result=queuehead;head=next(head);return result;6.5 队列2006这里我们要注意出队的步骤:1.需要判断队是否是空队,如果队空,那么返回一个异常说明队已经空了.无法弹出.如果队非空,那么继续.3.调用next()求出head得下一个位置然后移动.2.将head指向元素保存等待返回.注意,第2步与第3步千万不能颠倒.否则会引起

19、队列的存储异常.4.返回保存元素.6.5 队列2006 endhead0SIZE endhead0SIZE endhead0SIZE1.检查是否是空队2.将head指向元素保存3.head向正方向移动6.5 队列2006下面给出程序的完整代码,及必要注释.public class MyQueueprivate final int SIZE;private int queue;private int head;private int end;public MyQueue(int size)super();SIZE=size;queue=new intSIZE;head=0;end=0;队列所需要

20、的空间及标志构造函数,当该类被实例化后,一个队列就创建了.6.5 队列2006private int next(int i)return(i+1)%SIZE;public boolean isFull()return next(end)=head;public void offer(int data)throws Exceptionif(isFull()throw new Exception(queue is full);elsequeueend=data;end=next(end);6.5 队列2006public int poll()throws Exceptionif(isEmpty()

21、throw new Exception(queue is empty);elseint result=queuehead;head=next(head);return result;public int size()return(end+SIZE)-head)%SIZE;public boolean isEmpty()return end=head;求出队列得大小6.5 队列2006本课小结 本课介绍了栈和队列，这两各数据结构在程序设计中使用非常广泛。它们有着相似的特性，前者是先入后出结构，后者是先入先出结构。它们相似的特性导致了它们的标志属性甚至方法都非常相似。在使用过程中要多多的体会。2006小测验1.画出MIDP的层次结构。2.借助图示描述MIDlet的生命周期。2006小测验答案1.画出MIDP的层次结构。答：2006小测验答案2.借助图示描述MIDlet的生命周期。答：2006课后作业【作业【作业1】下载一款手机游戏，查看在不同的生命周期下，游戏的不】下载一款手机游戏，查看在不同的生命周期下，游戏的不同反应。同反应。