栈与队列(java版).ppt

《栈与队列(java版).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈与队列教学内容3.2队列3.1栈3.4栈与队列的综合应用举例3.3栈与队列的比较教学重点与难点重点：栈、队列的特点；栈、队列基本操作的实现算法难点：栈、队列的应用通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(i,x)Insert(n,x)Insert(n,x)0≤i≤nDelete(i)Delete(n-1)Delete(0)0≤i≤n-1栈和队列是两种操作受限的线性表，是两种常用的数据类型。3.1.1栈的概念(1)栈是仅限制在表尾进行插入和删除操作的特殊线性表，限制操作的表尾端称为“栈顶”,另一

2、端称为“栈底”a0a1a2…an-1栈底栈顶进出(2)栈是“后进先出”的线性表（LIFO）或“先进后出”的线性表（FILO）3.1.1栈的概念如下图所示的是铁路调度站形象地表示栈的“后进先出”特点。3.1.1栈的概念思考题：设有编号为1，2，3，4的四辆列车，顺序进一个栈式结构的站台，具体写出这四辆列车开出车站的所有可能的顺序。3.1.1栈的概念解答：四辆车出站的所有可能顺序为：6）2、1、3、4；7）2、1、4、3；8）2、3、4、1；9）2、3、1、4；10）2、4、3、1；14）4、3、2、1。1）1、2、3、4；2）1、2、4、3；3）1、3

3、、2、4；4）1、3、4、2；5）1、4、3、2；11）3、2、1、4；12）3、2、4、1；13）3、4、2、1；3.1.2栈的抽象数据类型描述clear()1）栈的置空操作：isEmpty()2）栈的判空操作：length()3）求栈的长度：4）取栈顶元素操作：5）入栈操作：peek()push(x)6）出栈操作：pop()1.基本操作3.1.2栈的抽象数据类型描述2.栈的抽象数据类型的Java接口描述publicinterfaceIStack{}publicvoidclear();publicbooleanisEmpty();publicint

4、length();publicObjectpeek();publicvoidpush(Objectx)throwsException;publicObjectpop();实现此接口的方法有两种:顺序栈链栈3.1.3顺序栈及其基本操作的实现1.顺序栈非空栈空栈a0a1an-1……top=nstackElemmaxSize-101……n-1……top=0stackElemmaxSize-1012……3.1.3顺序栈及其基本操作的实现1.顺序栈思考栈空条件?栈满条件?栈的长度?栈顶元素?如下问题如何描述?top==0top==stackElem.lengt

5、htopstackElem[top-1]a0a1an-1……top=nstackElem01……n-13.1.3顺序栈及其基本操作的实现2.顺序栈类的描述(书P71-与P33顺序表类对照学习)publicclassSqStackimplementsIStack{privateObject[]stackElem;privateinttop;}//构造一个容量为maxSize的空栈publicSqStack(intmaxSize){}//栈置空publicvoidclear(){}……stackElem=newObject[maxSize];top=0;

6、top=0;2.顺序栈类的描述(见教材P71)publicclassSqStackimplementsIStack{}//栈判空publicbooleanisEmpty(){}//求栈数据元素个数函数publicintlength(){}…………//取栈顶元素的函数publicObjectpeek(){}returntop==0;returntop;if(!isEmpty())//栈非空returnstackElem[top-1];//栈顶元素elsereturnnull;2.顺序栈类的描述(见教材P71)publicclassSqStackimpl

7、ementsIStack{}//入栈操作的函数publicvoidpush(Objectx){……}……//出栈操作的函数publicvoidpop(){……}//输出函数(从栈顶到栈底)publicvoiddisplay(){}for(inti=top-1;i>=0;i--)System.out.print(stackElem[i].toString()+"");3.顺序栈基本操作的实现1)顺序栈的入栈操作push(x)的实现（算法3.1)(1)操作要求：插入元素x使其成为顺序栈中新的栈顶元素。xa0a1an-1……toptopa.[判断顺序栈是否

8、为满，若满则抛出异常]b.[若栈不满，则将新元素x压入栈顶，并修正栈顶指针](2)算法步骤：if(top==