资源描述：
《数据结构栈和队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列栈和队列是两种重要的线性结构。从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列的插入、删除操作与线性表的插入、删除操作的比较：3.1栈栈（stack）是一种只允许在一端进行插入
2、和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。根据栈的定义可知，栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。这种表是按照后进先出（LIFO）的原则组织数据的，因此，栈也被称为“后进先出”的线性表。栈的示意图：a1a2an出栈入栈栈顶top栈底bottom…若输入序列是1,2,3，则可能的输出序列有哪些？1,
3、3,21,2,32,1,33,2,12,3,1栈的应用在各种程序设计语言中都有子程序（或称函数、过程）调用功能。而子程序也可以调用其它的子程序，甚至可以直接或间接地调用自身，即递归。相应的算法：floatfact(intn){if(n==0
4、
5、n==1)s=1;elses=n*fact(n-1);returns;}下面以求阶乘的递归方法为例，来分析计算机系统是如何处理这种递归调用关系的。求n！的递推公式：若求5!，递归调用执行过程：主函数mani()printf(“fact(5)”)第一层调用n=5s=5*fact(4)第二层调用n=4
6、s=4*fact(3)第三层调用n=3S=3*fact(2)第四层调用n=2S=2*fact(1)第五层调用n=1S=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24fact(5)=120输出s=120.00每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact才有结果为1，然后再一一返回计算，最终得到结果。计算机系统处理上述过程时，其关键是要正确处理执行过程中的递归调用层次和返回路径，也就是要记住每一次递归调用时的返回地址。在系统中用一个线性表动态记忆调用过程中的路径，
7、其处理原则为：（1）在开始执行程序前，建立一个线性表，其初始状态为空。（2）当发生调用（递归）时，将当前的调用的返回点地址插入到线性表的末尾；（3）当调用（递归）返回时，其返回地址从线性表的末尾取出。根据以上的原则，可以给出线性表中的元素变化状态如下图所示（以递归调用时n值的变化为例）：545453453245321——该线性表就是栈3.1.1栈的类型定义3.1.3栈的应用举例3.1.2栈类型的实现[栈]提要ADTStack{数据对象：D＝{ai
8、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
9、
10、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack3.1.1栈的类型定义InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())栈的基本操作InitStack(&S)DestroyStack(&S)操作结果：构造一个空栈S。初始条件：栈S已存在。操作结果：栈S被销毁。StackLength(S)
11、StackEmpty(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。GetTop(S,&e)ClearStack(&S)a1a2an……初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)a1a2ane……初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)a1a2anan-1……初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返
12、 回其值。StackTravers(S,visit())初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用visit()。若visit()失败，则操作失效。例一、数制转换例二、括号
