数据结构Java版第4章 栈与队列ppt课件.ppt

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

1、《数据结构（Java版）》叶核亚《数据结构（Java版）》第1章绪论第2章线性表第3章排序第4章栈与队列第5章数组和广义表第6章树和二叉树第7章查找第8章图第9章综合应用设计第4章栈与队列栈和队列是两种特殊的线性表。与线性表一样，栈和队列的数据元素之间具有顺序的逻辑关系，都可以采用顺序存储结构和链式存储结构；与线性表不同的是，线性表的插入和删除操作不受限制，可以在任意位置进行，而栈和队列的插入和删除操作受到限制，栈的插入和删除操作只允许在线性表的一端进行，而队列的插入和删除操作则分别在线性表的两端进行。栈的特点是

2、后进先出，队列的特点是先进先出，两者在实际问题中有着广泛的应用。4.1栈4.2队列4.3递归4.1栈4.1.1栈的定义4.1.2栈的抽象数据类型4.1.3栈的存储结构及实现4.1.4栈的应用举例4.1.1栈的定义栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。允许操作一端称为栈顶（top），不允许操作的一端称为栈底（bottom）。栈顶的当前位置是动态的，标识栈顶当前位置的变量称为栈顶指针。栈中插入数据元素的过程称为入栈（push），删除数据元素的过程称为出栈（pop）。当栈中没有数

3、据元素时称之为空栈。图4.1栈结构4.1.2栈的抽象数据类型1．栈的数据元素2．栈的基本操作栈的初始化，设置栈状态为空。判断栈的状态是否为空。判断栈的状态是否已满。入栈：将数据元素插入栈中作为新的栈顶数据元素的过程。在入栈之前必须判断栈的状态是否已满，如果栈不满，则接收新数据元素入栈，否则产生上溢错误（overflow）。出栈：取出当前栈顶数据元素，下一个数据元素成为新的栈顶数据元素的过程。在出栈之前，必须判断栈的状态是否为空。如果栈的状态为空，产生下溢错误（underflow）。获得栈顶数据元素，此时该数据元素

4、未出栈。栈的接口StackInterfacepackageds_java;publicinterfaceStackInterface//栈的接口{publicbooleanisEmpty();//判断栈的状态是否为空publicbooleanisFull();//判断栈的状态是否已满publicbooleanpush(Objectk);//k对象入栈publicObjectpop();//出栈publicObjectget();//获得栈顶元素，未出栈}4.1.3栈的存储结构及实现1．栈的顺序存储结构及操作实现p

5、ackageds_java;importds_java.StackInterface;publicclassStack1implementsStackInterface{//栈的顺序存储结构privateObjecttable[];privatefinalintempty=-1;//声明整数常量privateinttop=empty;//top为栈顶元素下标}顺序栈的操作实现数据结构（Java版）》叶核亚【例4.1】使用顺序栈的基本操作数据结构（Java版）》叶核亚2．栈的链式存储结构及操作实现packageds

6、_java;importds_java.OnelinkNode;//引用单链表结点类importds_java.Onelink1;publicclassStack2extendsOnelink1{//栈的链式存储结构privateOnelinkNodetop;}图4.3栈的链式存储结构链式栈的操作实现数据结构（Java版）》叶核亚链式栈的基本操作4.1.4栈的应用举例1．栈是嵌套调用机制的实现基础2．实现深度遍历算法时使用栈3．利用栈以非递归方式实现递归算法图4.5方法嵌套调用时的系统栈【例4.2】判断表达式中括

7、号是否匹配。数据结构（Java版）》叶核亚判断表达式中括号是否匹配的算法描述4.2队列4.2.1队列的定义4.2.2队列的抽象数据类型4.2.3队列的存储结构及实现4.2.4队列的应用举例4.2.1队列的定义队列（queue）是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。向队列中插入元素的过程称为入队（enqueue），删除元素的过程称为出队（dequeue）。允许入队的一端为队尾（rear），允许出队的一端为队头（front）。标识队头和队尾当前位置的变量称为队头指针和队尾指针。当队列中没有数据元

8、素时称作空队列。4.2.2队列的抽象数据类型1．队列的数据元素2．队列的基本操作队列的初始化，设置队列状态为空。判断队列的状态是否为空。判断队列的状态是否已满。入队：将数据元素从队尾处加入队列的过程。在入队之前必须判断队列的状态是否已满，如果队列不满，则接收新数据元素入队，队列满时数据元素不能入队，产生上溢错误（overflow）。出队：从队头处取出数据元素的过程。在出队