例3：一个栈的输入序列是12345，若在入栈的 过程中允许出栈，则栈的输出序列43512可能 实现吗？12345的输出呢？ 答： 43512不可能实现，主要是其中的12顺序不能实 现； 12345的输出可以实现，每压入一数便立即弹出 即可
6 例3：一个栈的输入序列是12345，若在入栈的 过程中允许出栈，则栈的输出序列43512可能 实现吗？12345的输出呢？ 答： 43512不可能实现，主要是其中的12顺序不能实 现； 12345的输出可以实现，每压入一数便立即弹出 即可
例4： 计算机系2001年考研题 设依次进入一个栈的元素序列为c,a,b,d, 则可得到出栈的元素序列是： A)a,b,c,d B)c,d,a,b C)/b,c,d,a D)a,c,d,b 答： A)、D)可以， B) C)不行。 讨论：有无通用的判别原则？ 有！若输入序列是，PPkP1.(PPkP) 定不存在这样的输出序列，PPP k” 即对于输入序列1,2,3，不存在输出序列3,1,2
7 例4： 设依次进入一个栈的元素序列为c，a，b，d， 则可得到出栈的元素序列是： Ａ）a，b，c，d Ｂ）c，d，a，b Ｃ）b，c，d，a Ｄ）a，c，d，b A）、D）可以， B）、C）不行。 讨论：有无通用的判别原则？ 有！若输入序列是 .,Pj.Pk.Pi .(Pj<Pk<Pi) ， 一定不存在这样的输出序列 .,Pi.Pj.Pk . 答： 即对于输入序列1，2，3，不存在输出序列3，1，2 计算机系2001年考研题
本节重点：顺序栈和链栈的基本操作 栈的抽象数据类型定义： 教材P44-45) ADT Stack{ 数据对象：D= 入栈、出栈、 数据关系： R-. 建栈初始化、 基本操作： 判断栈满或栈空、 读栈顶元素值等。 }ADT Stack
8 栈的抽象数据类型定义: (教材P44-45） ADT Stack{ 数据对象：D=. 数据关系：R=. 基本操作： . } ADT Stack 入栈、出栈、 建栈初始化、 判断栈满或栈空、 读栈顶元素值等