ADTStack(数据对象：D=[ai0≤i≤n-1，n≥0，元素ai为E类型}数据关系：R=(r]r=[<ai, ai+1> I ai, ai+iED, i=0, ."", n-2]基本运算：booleanempty（)：判断栈是否为空，若空栈返回真；否则返回假。voidPush(Ee）：进栈操作，将元素e插入到栈中作为栈顶元素。Epop()：出栈操作，返回栈顶元素。Epeek()：取栈顶操作，返回当前的栈顶元素。栈抽象数据类型=线性结构+栈的基本运算6/101
栈抽象数据类型 = 线性结构 + 栈的基本运算 ADT Stack { 数据对象： D={ai | 0≤i≤n-1，n≥0，元素ai为E类型} 数据关系： R={r} r={<ai，ai+1> | ai，ai+1∈D， i=0，.，n-2} 基本运算： boolean empty()：判断栈是否为空，若空栈返回真；否则返回假。 void Push(E e)：进栈操作，将元素e插入到栈中作为栈顶元素。 E pop()：出栈操作，返回栈顶元素。 E peek()：取栈顶操作，返回当前的栈顶元素。 } 6/101
应用程序基本运算栈元素7/101
栈元素 基本运算 应用程序 7/101
一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（）。示例A.edcbaB.decbaD.abcdeC.dceab方法1：用栈模拟进行判断方法2：利用判断准则判断准则：输入序列为1，2，，n，（pi，P2，…，Pn）是1,2，…，n的一种排列，利用一个栈得到输出序列（pi，P2，…Pn）的充分必要条件是不存在这样的i、j、k满足i<j<h的同时也满足P<Pk<Pi违反了！d c e;a b个个不Pj PkPi8/101
一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序 列是（ ）。 A.edcba B.decba C.dceab D.abcde 示例 方法2：利用判断准则 方法1：用栈模拟进行判断 判断准则：输入序列为1，2，.，n，（p1，p2，.，pn）是1， 2，.，n的一种排列，利用一个栈得到输出序列（p1，p2，.， pn）的充分必要条件是不存在这样的i、j、k满足i<j<k的同 时也满足pj<pk<pi。 d c e a b 违反了! pi pj pk 8/101
11～n共产生种合法出栈序列。C2nn+1例如，n=5合法45321不合法31254个不合法14235个9/101
1～n共产生 n+1 1 C 2n n 种合法出栈序列。 例如，n=5 4 5 3 2 1 合法 3 1 2 5 4 不合法 1 4 2 3 5 不合法 9/101
已知一个栈的进栈序列是1，2，3，…，n，其输出序列是p1，示例P2，，Pn，若pi=n，则p,的值为（）。A.iB.n-iD.不确定C.n-i+11,2, 3,.,nn输出序列唯一Pi=nP2=n-1P3=n-2Pi+i=n+1即p;=n-i+1Pn=110/101
已知一个栈的进栈序列是1，2，3，.，n，其输出序列是p1， p2，.，pn，若p1=n，则pi的值为（ ）。 A.i B.n-i C.n-i+1 D.不确定 示例 1，2，3，.，n n，. 输出序列唯一 p1=n p2=n-1 p3=n-2 . pn=1 pi+i=n+1即pi=n-i+1 10/101