数据结构-基于Python语言（微课版） 课件T6-栈与队列(栈)

栈第三章：栈与队列

主讲：周翔回顾请从存储结构、基本操作两方面简述顺序表与链表的不同之处预习检查请概括一下栈的概念请概括一下队列的概念本章目标3栈的应用循环队列重点了解掌握2栈、队列的链式实现栈、队列的定义和性质栈、队列的顺序实现1什么是栈什么是栈？什么是栈栈（Stack）栈也是一种线性表，但它是受到限制的线性表用铁路调度站表示栈什么是栈栈(Stack)定义：只能在表的一端（栈顶）进行插入和删除运算的线性表逻辑结构：与线性表相同，仍为一对一关系存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则实现方式：关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等什么是栈栈(Stack)（1）栈中允许执行插入和删除操作的一端称为栈顶，不允许执行插入和删除操作的一端称为栈底；（2）向一个栈中插入新元素又称为入栈、压栈。入栈之后该元素被放在栈顶元素的上面，成为新的栈顶元素；（3）从一个栈中删除元素又称为出栈、弹栈，是把栈顶元素删除，使其相邻元素成为新的栈顶元素。什么是栈设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列____。 A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A543210-1ECABDADECBAEDCB什么是栈设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是_________。 2，3，5，4，112453栈的表示和实现栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行ADTStack{

数据元素：可以是任意类型的数据，但必须属于同一个数据对象 结论关系：栈中数据元素之间是线性关系 基本操作： InitStack(S); //将S初始化为空栈Push(S,x); //进栈Pop(S,x); //出栈……}栈的表示和实现——顺序栈栈的顺序存储也称为顺序栈，它利用一组地址连续的存储单元，依次存放自栈底到栈顶的元素，同时附设栈顶标识top来指示栈顶元素在顺序栈中的位置用数组实现栈数组elem存储栈元素elem[0]为最早入栈的元素，即为数组的底部数组向下标增大方向扩展栈底elem[0]0123456789

Stack_Size

top(栈空)elem栈顶elem[top]栈的表示和实现——顺序栈顺序栈插入元素：进栈栈的表示和实现——顺序栈顺序栈删除元素：出栈栈的表示和实现——双端栈栈的应用非常广泛，经常会出现在一个程序中需要同时使用多个栈的情况若使用顺序栈，会因为对栈空间难以估计而产生有的栈溢出、有的栈空间还很空闲的情况。解决方案：让多个栈共享一个足够大的数组空间最常用的是两个栈的共享技术－－双端栈栈的表示和实现——双端栈双栈共享一个栈空间两个栈共享一个数组空间Stack[0:M-1]两栈栈底分别放在一维数组的两端，分别是0和M-1两个栈顶动态变化初始情况：top[0]=-1,top[1]=M栈满条件：top[0]+1==top[1]//两个栈顶指针相遇

top[0]top[1]0n-1StackM-1栈的表示和实现——链式栈栈的链式存储也称为链栈，它和链表的存储原理一样，都可以利用闲散空间来存储元素，用指针来建立各结点之间的逻辑关系。链栈也会设置一个栈顶元素的标识符top，称为栈顶指针。它和链表的区别是，只能在一端进行各种操作。栈的表示和实现——链式栈用指针实现栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行即：在链表的表头进行！链表的表头指针就作为栈顶指针栈空操作：top→next=NULL;top栈顶栈底a1an0an-1栈的表示和实现——链式栈进栈topa1an0an-1tempx栈的表示和实现——链式栈出栈topa10an-1tempxanan栈的表示和实现——多栈运算若同时使用两个以上的栈，采用顺序栈处理极不方便。采用多个单链表实现多个链栈是很好的实现途径！栈的表示和实现——多栈运算E1M-1......543210C1C2NULLD1NULLNULLF1NULLE2E3NULLG1G2NULLdatanextLinkStackNodeLinkStacktop[M]栈的表示和实现——多栈运算E1M-1......543210C1C2NULLD1NULLNULLF1NULLE2E3NULLG1G2NULLtop[M]top[0]、top[1]，…，top[M-1]分别是M个链栈的栈顶指针分别指向M个不同的链栈！递归的概念递归：在定义自身的同时又出现了对自身的引用递归函数：直接地或间接地调用自身的算法走迷宫骑士游历递归的概念递归函数调用时，按照“后调用先返回”的原则处理调用递归过程必须通过栈来实现递归调用时需完成调用返回时需完成保留本层参数与返回地址保存被调函数的计算结果为被调用算法的局部变量分配存储区，给下层参数赋值释放分配给调用算法的数据区，恢复上层参数将程序转移到被调函数的入口依照被调函数保存的返回地址将控制转回调用函数递归的概念所谓递归就是程序调用自身的过程，它可以把一个大型的、复杂的问题层层转化为一个与原问题相似的、规模较小的问题来求解，递归策略只需少量的代码就可描述出解题过程中所需要的多次重复计算，大大地减少了程序的代码量。一般来说，递归需要有临界条件：递归前进和递归返回段。否则递归将无限调用，永远无法结束程序，最后会造成内存崩溃。以下三种情况常常用到递归方法递归定义的数学函数具有递归特性的数据结构可递归求解的问题递归的应用——递归定义的数学函数递归在数学方面的应用xn=x*x*x*...*x*xS(n)=1+2+...+(n-1)+n要计算xn+1或S(n+1)，可利用前面计算过的结果以求得答案:xn+1=xn*xS(n+1)=S(n)+(n+1)这种利用前面运算来求得答案的过程就叫递归过程递归的应用——递归定义的数学函数阶乘函数（Factorial）//求解阶乘函数的递归算法longfact(intn){ if(n==0) return1; else returnn*fact(n-1);}每个递归函数都必须有非递归定义的初始值！递归的应用——递归定义的数学函数f(n)=n×f(n-1)递归的应用——递归定义的数学函数参数传递主程序

main:fact(4)参数4计算4*fact(3)参数3计算3*fact(2)参数2计算2*fact(1)参数1计算1*fact(0)参数0直接定值=1结果返回递归调用回归求值返回24返回6返回2返回1返回1递归的应用——递归定义的数学函数求Fibonacci序列intfib(intn){ if(n<=1) return1; return

fib(n-1)+fib(n-2);}Fibonacci数列：1,1,2,3,5,8,13,21,34,55,...递归的应用——具有递归特性的数据结构树

RootLchildRchild广义表A=(a,A)递归的应用——可递归求解的问题Hanoi塔（汉诺塔）问题设a,b,c是三个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小的叠在一起各圆盘从小到大编号为1,2,...,n如图所示acb递归的应用——可递归求解的问题目的：将塔座x上的这一叠圆盘移到塔座z上，并仍按照同样顺序叠置。xyz递归的应用——可递归求解的问题在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则①和②的前提下，可将圆盘移至x,y,z中任一塔座上。递归的应用——可递归求解的问题xyz321121321很难理解它的道理也很难理解它的设计思想递归的应用12…nxyz21…n-1递归算法将一个复杂的大问题，分割成一些规模较小的类似的子问题规模最小的子问题具有直接解原问题子问题1子问题2子问题3...递归算法递归算法分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解必备的三个条件：能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的可以通过上述转化而使问题简化必须有一个明确的递归出口，或称递归的边界递归算法使用递归算法的前提：原问题可以层层分解为类似的规模更小的子问题；规模最小的子问题具有直接解。 如求n!中，n==0时，0!=1若递归设计时递归出口设计不当……//无穷递归的例子//讲不完的故事voidStory(){

printf("从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，有一天，老和尚对小和尚说：");

Story();}递归算法递归算法的优缺点：优点：结构清晰，程序易读缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大递归算法的效率分析空间效率：与递归树的深度成正比，O(n)时间效率：与递归树的结点数成正比，O(2n)递归算法把复杂的问题分解为简单问题，分而治之，因此，对求解某些复杂问题，递归算法的分析方法十分有效。但，递归算法的效率较低。栈的应用栈是嵌套调用机制的实现基础使用栈以非递归方式实现递归算法栈的应用——括号匹配问题表达式中包含三种括号

()、[]、{}

例如：正确格式——{[(x+6)+(x+y)]+(y-x)}

错误格式——{[]})对于给定的表达式，从左到右逐个字符扫描：每个右圆括号与最近遇到的尚未匹配的左圆括号匹配；每个右花括号与最近遇到的尚未匹配的左花括号匹配；每个右方括号与最近遇到的尚未匹配的左方括号匹配。栈的应用——括号匹配问题判断表达式中圆括号是否匹配栈的应用——括号匹配问题算法：在扫描过程中将所遇到“左圆括号(、左方括号[、左花括号{”存入栈中①遇到“右圆括号)、右方括号]、右花括号}”时若栈空，则遇到的“右”不匹配；②若栈非空栈顶元素是同类型的“左”型括号，则将栈顶元素作出栈操作；③栈顶元素不是同类型的“左”型括号，不合法。④读入序列已结束，而栈中仍有等待匹配的左括号，不合法!⑤读入序列与栈同时结束，则所有括号匹配！⑥栈的应用——用栈实现四则运算1、中缀转后缀对于数字：直接输出；对于符号：左括号：进栈，不管栈中是否有元素。运算符：若此时栈为空，直接进栈。若栈中有元素，则与栈顶符号进行优先级比较：若新符号优先级高，则新符号进栈（默认左