java数据结构老师课件第4章 栈和队列.ppt

《java数据结构老师课件第4章 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章栈和队列栈和队列是两种特殊的线性表。它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制。栈和队列被广泛应用于各种软件设计中。主要内容4.1栈4.2队列4.3优先队列4.4递归算法目的：使用栈或队列求解应用问题。要求：掌握栈和队列抽象数据类型，以及顺序和链式存储结构实现；理解对于怎样的应用问题，需要使用栈或队列，以及怎样使用。重点：栈和队列的设计和应用。难点：栈或队列的使用场合，以及如何使用栈和队列求解应用问题。4.1栈4.1.1栈抽象数据类型4.1.2顺序栈4.1.3链式栈4.1.4栈的应用4.1.1栈抽

2、象数据类型1、栈的定义栈（Stack）又称堆栈，是指插入和删除运算被限制在表的一端进行的线性表。允许操作的一端称为栈顶（Top）；不允许操作的一端称为栈底（Bottom）；在栈顶插入元素的操作称为入栈（Push）；删除栈顶元素的操作称为出栈（Pop）；没有元素的栈称为空栈。栈的运算规则是按后进先出的原则进行的，因此栈又称为LIFO（lastinfirstout）表。2、栈抽象数据类型publicinterfaceSStack//栈接口，栈抽象数据类型{booleanisEmpty();//判断栈是否为空voidpus

3、h(Tx);//元素x入栈Tpop();//出栈，返回栈顶元素Tget();//取栈顶元素，未出栈}4.1.2顺序栈采用顺序存储结构的栈称为顺序栈。举例：数据序列：{A、B、C、D}操作序列：{push()、push()、pop()、push()、push()、pop()、pop()、pop()}思考给定一个数据序列，通过控制入栈和出栈时机，可以得到多种出栈排列。当入栈次序为A、B、C时，有哪些出栈序列？A,B,CA,C,BB,A,CB,C,AC,B,AAC012B栈底栈顶入栈{A，B，C}出栈{C，B，A}顺序栈类（Se

4、qStack.java）publicclassSeqStackimplementsSStack//顺序栈类，实现栈接口{privateObjectelement[];//存储栈数据元素的数组privateinttop;//栈顶元素下标publicSeqStack(intsize)//构造容量为size的空栈{this.element=newObject[Math.abs(size)];this.top=-1;}publicSeqStack()//构造默认容量的空栈{this(64);}//其它方法后续给出}to

5、p=-1012空栈value[]（1）判断是否空栈publicbooleanisEmpty()//判断栈是否空，若空返回true{returnthis.top==-1;}top=-1012空栈value[]（2）入栈publicvoidpush(Tx)//元素x入栈，空对象不能入栈{if(x==null)return;//空对象不能入栈if(this.top==element.length-1)//若栈满，则扩充栈容量{Object[]temp=this.element;this.element=newObject[tem

6、p.length*2];//重新申请一个容量更大的数组for(inti=0;i

7、元素“B”出桟后AB012元素“B”出桟前top=（4）取栈顶元素值publicTget()//取栈顶元素，未出栈，若栈空返回null{returnthis.top==-1?null:(T)this.element[this.top];}AB012取栈顶元素值为：“B”top=（5）成串publicStringtoString()//返回栈所有元素的描述字符串，形式为“(,)”，算法同顺序表{Stringstr="(";if(this.top!=-1)str+=this.element[this.top].toString

8、();for(inti=this.top-1;i>=0;i--)str+=","+this.element[i].toString();returnstr+")";}AB012该栈成串为：{B,A}top=顺序栈操作的效率分析isEmpty()Push()Pop()get()toString()时间复杂