数据结构与算法（Python版）第2版 课件 chap4.2 栈

周元哲栈栈与队列的逻辑特征：

从数据结构角度讲，栈与队列也是线性表，不同之处在于其操作的特殊性（栈为LIFO，队列为FIFO），为操作受限的线性表。

从数据类型角度讲，栈与队列是与线性表不同的重要抽象数据类型，广泛的应用于各类软件系统中。1.基本概念定义：栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。an...a2a1

栈顶

Top

栈底

Bottom栈顶（Top）—表尾元素，允许插入和删除的一端。栈底（Bottom)—表头元素，不允许插入和删除的一端。空栈—表中没有元素。2.栈的基本特征栈——后进先出(LIFO，LastInFirstOut)。故栈又称为后进先出的线性表。an...a2a1入栈出栈栈顶栈底入栈(PUSH)---最先插入的元素放在栈的底部。出栈(POP)---最后插入的元素最先出栈。

栈的实现——顺序栈

——链栈2.顺序栈：栈顶指针与栈中元素间关系3210BAtopC出栈top=-1，B、A出栈32103210空栈top=-13210AA进栈top3210CBAtopB,C依次进栈〖例〗设有一个空栈，栈顶指针为1000H，现有输入序列为12345,PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后,输出序列为___,栈顶指针为______〖例〗在一个n个单元的顺序栈中，假定以地址高端(下标为n的单元)作为栈底，以top作为栈顶指针，则向栈中压入一个元素时，top的变化是______top不变top=ntop=top-1 top=top+1〖例〗若一个栈的输入序列是1，2，…，n，输出序列的第一个元素是n，则第i个输出元素是______n-i n-i+1 i n-i-12,31003H3.顺序栈的基本操作特点下溢：栈空时再做退栈运算将产生溢出。1）栈底位置固定在向量的低端，即S->elem[0]----表示栈底元素2）入栈：S->top++

，保存元素；3）出栈：取元素，S->top--；4）空栈：S->top=-1；5）栈满：S->top=Stack_Size-1；上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。classStack(object):def__init__(self):#初始化self.items=[]defis_empty(self):#判断栈是否为空returnself.items==[]defpush(self,item):#加入元素self.items.append(item)defpop(self):#弹出元素returnself.items.pop()defpeek(self):#返回栈顶元素returnself.items[len(self.items)-1]defsize(self):#返回栈的大小returnlen(self.items)注意:链栈中指针的方向8.链栈的基本概念anan-1^a1····栈顶指针链栈的特点插入和删除（进栈/退栈）仅能在表头位置上（栈顶）进行。链栈中的结点是动态产生的，可不考虑上溢问题。不需附加头结点，栈顶指针就是链表（即链栈）的头指针。11.链栈的基本操作特点栈底位置固定链表的末尾p->next=NULL----表示栈底元素入栈：用入栈元素建立新结点，并将其插入到链表的第一个结点之前（头插法）；出栈：取出链表第一个结点的元素，并将其第一个结点从链表中删除；空栈：S=NULL；假设在表达式中 （［］（））或［（［］［］）］等为正确的格式， ［（］）或（［（））或（（）］)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例.括号匹配的检验分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。例如：考虑下列括号序列：

[([][])]12345678栈与递归过程2.递归应用：1)阶乘函数2)斐波纳契数列(Fibonacci函数)递归算法的两个基本特征递推归纳将问题转化为比原问题小的同类规模，归纳出一般递推公式.

故所处理的对象要有规律地递增或递减递归终止当规模小到一定的程度应该结束递归调用,逐层返回常用条件语句来控制何时结束递归例求递归方法求n的阶乘总结执行过程（两个阶段）第一阶段：逐层调用，调用函数自身第二阶段：逐层返回，返回到调用该层的位置继续执行后递归调用是多重嵌套调用的一种特殊情况调用的深度：调用的层数设计递归算法的方法前提：原问题可以层层分解为类似的子问题，且子问题比原问题规模更小规模最小的问题具有直接解方法：寻找分解方法：将原问题转化为子问题求解，例：n!=n*(n-1)!设计递归出口：根据规模最小的子问题确定递归终止条件，例：求解n!，当n＝0时，n!＝1；2.递归应用示例——汉诺(hanoi)问题n阶Hanoi塔问题：假设有三个分别命名为X,Y,Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大的编号为1,2,3,…,n的圆盘。现要求将X轴上的n个盘移到至塔座Z上并保持同样顺序叠排，移动圆盘时必须遵守以下规则：（1）每次只能移动一个圆盘；（2）圆盘可以插在X,Y,Z任意一个塔座上；（3）任何时候都不能将一个较大的圆盘放到较小的圆盘之上。

将A塔上的红、黄两盘移动到B上蓝盘放到C上将红、黄两盘从B移动到C盘上。（完成）ABC问题分析：n=1时，直接将其从A－>C；n>1时，只要先将前n-1个借助C从A－>B,那么可以把第n个直接从A－>C;3.如何将剩下的n-1个圆盘遵守规则借助A从B－>C，问题性质同（2）;问题性质相同，因此适合采用递归过程！若将n个盘片按规定从A塔移至C塔，移动步骤可分为三步：把A塔上的n-1个盘片借助C移动到B塔把第n个盘片从A塔移至C塔把B塔上的n-1个盘片借助A塔移至C塔算法用函数hanoi(n,x,y,z)以递归算法实现盘片数源塔借用塔目标塔

递归终止：当递归调用到盘片数为1时算法描述：1)递归调用hanoi(n-1,a,c,b);2)将n号盘片从a塔移动到c塔；3)递归调用hanoi(n-1,b,a,c)。将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：3.函数调用实现内幕保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套调用，例如：栈小结栈是一种操作受限制的特殊