入栈操作: 例如用堆栈存放(A,B,CD(注意要遵循“后进先出”原则) 高地址M rtop top top C B B rtop DCBA 低地址L A A A top 核心语句: top=L; 顺序栈中的PUSH函数 Push(a); status Push( Elem Type x) Push(B ) f(top>M){上溢} Push( c) else v[top++=x Push(D);
入栈操作: 例如用堆栈存放(A,B,C,D)(注意要遵循“后进先出” 原则) A A C B A B A top 核心语句： top=L; 顺序栈中的PUSH函数 status Push( ElemType x ) { if ( top>M ) { 上溢 } else v[top++] = x; } Push( B ); Push( C ); Push( D ); top top top top 低地址L Push( A ); 高地址M B C D
出栈操作:例如从栈中取出B(注意要遵循“后进先出”原 则) 高地址M Stop\ top D D C C Cttop C B 1 B B 低地址LA A A A/op 顺序栈中的PoP函数 核心语句: status Pop Pop o; if(topL){下溢} Popo else( y=v-top Printf(Pop 0); return(y )
出栈操作: 例如从栈中取出‘B’（注意要遵循“后进先出” 原 则） D C B A top top D C A B D C B A D top C B A top 低地址L 高地址M D 核心语句： Pop ( ); Pop ( ); Printf( Pop () ); 顺序栈中的POP函数 status Pop( ) { if ( top=L ) { 下溢 } else { y = v[--top]; return( y ); } }
若入栈动作使地址向高端增长,称为“向上生成”的栈 若入栈动作使地址向低端增长,称为“向下生成”的栈 对于向上生成的栈 入栈口诀:堆栈指针tp先压后加(v[top+]=); 出栈口诀:堆栈指针tp先减后弹(y=v[-top])。 栈不存在的条件:base=NULL 栈为空的条件:base=top; 栈满的条件:top-base= stacksize;
若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈； 对于向上生成的栈 入栈口诀：堆栈指针top先压后加（v[top++]=x）； 出栈口诀：堆栈指针top先减后弹（y=v[--top]) 。 栈不存在的条件：base=NULL; 栈为空 的条件 ： base=top; 栈满的条件 ： top-base=stacksize;
问:为什么要设计堆栈?它有什么独特用途? 答:1.调用函数或子程序非它莫属; 2.递归运算的有力工具; 3.用于保护现场和恢复现场; 4.简化了程序设计的问题。 问:栈是什么?它与一般线性表有什么不同? 答:栈是一种特殊的线性表,它只能在的端即牻顶进行插入和删除运算。 与一般线性表的区别:仅在于运算规则不同。 例对于一个栈,给出输入项A、B、C如果输入项序列由ABC组成, 试给出所有可能的输出序列。 A进A出B进B出C进C出ABC A进A出B进C进C出B出ACB A进B进B出A出C进C出BAC A进B进B出C进C出A出BCA A进B进C进C出B出A出CBA 不可能产生输出序列CAB
问：为什么要设计堆栈？它有什么独特用途？ 1. 调用函数或子程序非它莫属； 2. 递归运算的有力工具； 3. 用于保护现场和恢复现场； 4. 简化了程序设计的问题。 答： 问：栈是什么？ 它与一般线性表有什么不同？ 答：栈是一种特殊的线性表,它只能在表的一端(即栈顶)进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。 例 对于一个栈,给出输入项A、B、C,如果输入项序列由ABC组成， 试给出所有可能的输出序列。 A进 A出 B进 B出 C进 C出 ABC A进 A出 B进 C进 C出 B出 ACB A进 B进 B出 A出 C进 C出 BAC A进 B进 B出 C进 C出 A出 BCA A进 B进 C进 C出 B出 A出 CBA 不可能产生输出序列CAB
例一个栈的输入序列是12345,若在入栈的过程中允许出栈,则 栈的输出序列43512可能实现吗?12345的输出呢? 答:43512不可能实现,主要是其中的12顺序不能实现; 12345的输出可以实现,只需压入一个立即弹出一个即可。 例如果一个栈的输入序列为123456,能否得到435612和135426的 出栈序列? 答:435612中到了12顺序不能实现; 135426可以实现。 例:设依次进入一个栈的元素序列为ca,b,d,则可得到出栈的元素 序列是: A)a,b, c d B)c,,a, b C)b, c, d a D)a, c, d, b 答:A、D可以(B、C不行)。 讨论:有无通用的判别原则? 有。在可能的输出序列中,不存在这样的输入序列k,能同时 满足k和PPP1
例 一个栈的输入序列是12345，若在入栈的过程中允许出栈，则 栈的输出序列43512可能实现吗？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹出一个即可。 435612中到了12顺序不能实现； 135426可以实现。 例 如果一个栈的输入序列为123456，能否得到435612和135426的 出栈序列？ 答： 答： 例：设依次进入一个栈的元素序列为c,a,b,d, 则可得到出栈的元素 序列是： Ａ）a,b,c,d Ｂ）c,d,a,b Ｃ）b,c,d,a Ｄ）a,c,d,b A、D可以( B、C不行)。 讨论：有无通用的判别原则？ 有。在可能的输出序列中，不存在这样的输入序列i,j,k，能同时 满足 i<j<k 和 Pj<Pk<Pi 答：