例：一个栈的输入序列为1,2.3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解：即123;①1入1出，2入2出，3入3出，即132;1入1出，2、3入，3、2出,即231;）1、2入，2出，3入3出，3即213;1、2入，2、1出，3入3出，即321;③1、2、3入，3、2、1出，合计有5种可能性
例：一个栈的输入序列为1,2,3，若在入栈的过程中允 许出栈，则可能得到的出栈序列是什么？ 解：可以通过穷举所有可能性来求解： ① 1入1出， 2入2出，3入3出， 即123； ② 1入1出， 2、3入，3、2出， 即132； ③ 1、2入，2出， 3入3出， 即231； ④ 1、2入，2、1出，3入3出， 即213； ⑤ 1、2、3入，3、2、1出， 即321； 合计有5种可能性
例：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，每压入一数便立即弹出即可
例：一个栈的输入序列是12345，若在入栈的过 程中允许出栈，则栈的输出序列43512可能实现 吗？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，每压入一数便立即弹出即可
例设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：B)c,d,a,bA)a,b,c,dD) a, c, d,bC) b, c, d,a答：A）、D）可以，B）、C）不行。讨论：有无通用的判别原则？有！若输入序列是...,P...Pk...Pi...(P:<Pk<P)一定不存在这样的输出序列,Pi...P....Pk即对于输入序列1，23，不存在输出序列3，1，2
例 设依次进入一个栈的元素序列为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
3.1.2堆栈抽象数据类型1数据集合堆栈的数据集合可以表示为a0,al....,an-1，每个数据元素的数据类型可以是任意的类类型。2操作集合（1）入栈push(obi)：把数据元素obj插入堆栈。(2)出栈popO：出栈，删除的数据元素由函数返回。（3）取栈顶数据元素getTopO：取堆栈当前栈顶的数据元素并由函数返回。（4）非空否notEmptyO：若堆栈非空则函数返回true否则函数返回false
１数据集合 堆栈的数据集合可以表示为a0,a1,.,an-1，每个数据 元素的数据类型可以是任意的类类型。 3.1.2 堆栈抽象数据类型 ２操作集合 （1）入栈push(obj)：把数据元素obj插入堆栈。 （2）出栈pop()：出栈, 删除的数据元素由函数返回。 （3）取栈顶数据元素getTop()：取堆栈当前栈顶的数 据元素并由函数返回。 （4）非空否notEmpty()：若堆栈非空则函数返回true， 否则函数返回false
堆栈数据类型的接口定义：interface Stackvoid push(Object obi):Object popO;Object getTopO;bool notEmpty(O);人
interface Stack { void push(Object obj); Object pop(); Object getTop(); bool notEmpty(); } 堆栈数据类型的接口定义：