练习2 设一个栈的输入序列为A、B、C、D,则借助一个 栈所得到的输出序列不可能是 (A)A, B, C, D B)D, C, B, A (C)A, CD, B D)D,A, B,C 答案:D
6 • 设一个栈的输入序列为A、B、C、D,则借助一个 栈所得到的输出序列不可能是 。 (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C 练 习 2 答案：D
栈的抽象数据类型 ADT Stacki 数据对象:D={a11m,n>0,a1为 ElemType类型} 数据关系:R={<a1,a21Na1;a11∈D,i1,n-1} 基本运算: Initstack(&s)∥{始化栈:构造一个空栈s DestroyStacke(&s)/销毁栈:释放栈S占用的存储空间 StackEmpty(s))/判断栈是否为空 Push(&S,e)进栈:将元素c插入到栈s中作为栈项元素 Pop(&s&e)∥出栈:从栈s中退出栈顶元素,并将其值赋给e GetTop(s,&e)/取栈顶元素:返回当前的栈顶元素,并将其值赋给e JADT Stack
7 栈的抽象数据类型 ADT Stack{ 数据对象：D={ai |1≤i≤n,n≥0，ai为ElemType类型} 数据关系：R={<ai ，ai+1 >| ai，ai+1 D ，i=1,...,n-1} 基本运算: InitStack(&s) //初始化栈：构造一个空栈s DestroyStack(&s) //销毁栈：释放栈s占用的存储空间 StackEmpty(s) //判断栈是否为空 Push(&S,e) //进栈：将元素e插入到栈s中作为栈顶元素 Pop(&s,&e) //出栈：从栈s中退出栈顶元素，并将其值赋给e GetTop(s,&e) //取栈顶元素：返回当前的栈顶元素，并将其值赋给e }ADT Stack
Push(&s, e) 初始条件:栈S已存在 操作结果:插入e为新的栈顶元素 a1 a 2 ●●●●● a e n 8
8 a1 a2 a … … n Push(&S, e) 初始条件：栈 S 已存在 操作结果：插入e为新的栈顶元素 e
Pop(&s, &e) 初始条件:栈S存在且非空 操作结果:删除S的栈顶元素,赋值给e a1 a 2 ●●●●● n n
9 a1 a2 a … … n-1 Pop(&S,&e) 初始条件：栈 S 存在且非空 操作结果：删除S 的栈顶元素，赋值给e an
GetTop(s, &e) 初始条件:栈S已存在且非空 操作结果:返回S的栈顶元素,赋值给e 1c2 ●●●●●● n
10 a1 a2 a … … n GetTop(S,&e) 初始条件：栈 S 已存在且非空 操作结果：返回 S 的栈顶元素，赋值给e