外观
3.2 栈的操作与抽象数据类型
调度员要对调度站做什么
3.1节把1、2、3调成了2、1、3开出。看其中一个时刻:1号、2号已经开进站,3号还在右边等着,现在轮到开出2号。
开出之前,调度员要先看一眼:站里还有没有车?最外面是几号?确认最外面就是2号,才让它开出去。开出之后,他要记下开出的是几号,才知道开出的顺序对不对。接下来,3号还要开进来。
这些事都从一个空的调度站开始。
本节问题把调度站看成栈,调度员的这些动作,栈要提供哪些操作?
栈的五个操作
2.2节给线性表定了五个操作。栈是线性表,只是只能动栈顶。把这五个操作逐个改成栈的,就得到栈的五个操作。下面把栈记作S。
InitStack(S):建立一个空栈。对应线性表的Init,没有变。调度站开始时空着,一节车厢都没有。
StackEmpty(S):栈空返回1,不空返回0。对应线性表的Length。栈用不着说第几个,也就用不着数一共有几个,只要知道空不空。调度员问"站里还有没有车",问的就是这个。
GetTop(S, &x):取栈顶元素,用x带回。对应线性表的Get。线性表可以取第几个,栈只能取栈顶,所以不用说第几个。取完之后栈不变,就像调度员只是看一眼最外面是几号,车不开走:
Push(S, x):把x放到栈顶。对应线性表的Insert。线性表要说插在第几个,栈不用说,位置只能是栈顶。x放进来之后,就是新的栈顶。3号开进,就是Push(S, 3):
Pop(S, &x):删除栈顶元素,用x带回。对应线性表的Delete。同样不用说删第几个,只能删栈顶。和Delete不同的是,Pop还要告诉调用者删掉的是谁,因为调度员得知道开出去的是几号。3号开出,就是Pop(S, &x),x是3:
GetTop和Pop为什么用x带回,不像线性表的Get那样直接返回?因为空栈时,它们做不成。线性表的Get做不成时返回'\0',可栈里放的是车厢编号,任何一个整数都可能是编号,挑不出一个数专门表示"做不成"。所以返回值留着报告做成没做成,栈顶元素用x带回。x前面的&,就是2.5节讲的传地址。
五个操作和线性表的对应如下:
| 线性表 | 栈 | 含义 |
|---|---|---|
| Init(L) | InitStack(S) | 建立一个空栈 |
| Length(L) | StackEmpty(S) | 栈空返回1,不空返回0 |
| Get(L, i) | GetTop(S, &x) | 取栈顶元素,用x带回,栈不变 |
| Insert(L, i, x) | Push(S, x) | 把x放到栈顶 |
| Delete(L, i) | Pop(S, &x) | 删除栈顶元素,用x带回 |
栈的操作都没有i,因为位置总是栈顶。空栈没有栈顶,所以不能GetTop,也不能Pop。栈满了怎么办,是实现时的事。
3.1节说的是栈"是什么":只能在一端插入和删除的线性表。这五个操作说的是栈"能做什么"。两样合起来,就是栈的抽象数据类型。和2.2节线性表的抽象数据类型一样,它只说是什么、能做什么,不说元素怎么存、操作怎么做。
例题:用五个操作调出2、1、3
题目1号、2号、3号车厢按这个顺序开到调度站。把调度站看成栈S,要按2、1、3的顺序开出,依次调用哪些操作?每次开出时,x是几?
分析。按要开出的车厢,一节一节写。
- 开始:调用InitStack(S),S是空栈。
- 开出2号:2号还没进站,先让1号、2号入栈,调用Push(S, 1)、Push(S, 2)。这时栈顶是2,调用Pop(S, &x),x是2。
- 开出1号:1号现在是栈顶,调用Pop(S, &x),x是1。
- 开出3号:3号还没进站,调用Push(S, 3)。它就是栈顶,再调用Pop(S, &x),x是3。
答案依次调用InitStack(S)、Push(S, 1)、Push(S, 2)、Pop(S, &x)、Pop(S, &x)、Push(S, 3)、Pop(S, &x)。三次Pop带回的x依次是2、1、3。
调度员的每一个动作都是五个操作之一,没有一步需要知道车厢存在哪里。下一节给栈选一种存法,这串调用不用改。
练习1:x依次是几?
填空
从空栈开始,依次调用:
Push(S, 5),Push(S, 8),Pop(S, &x),Push(S, 6),GetTop(S, &x),Pop(S, &x)
- 第一次Pop之后,x是
- GetTop之后,x是
- 第二次Pop之后,x是
- 全部做完,栈里只剩
第一次Pop时栈里是5、8,栈顶是8。接着6入栈,栈顶是6。GetTop只看不拿,x是6,栈不变。所以第二次Pop删掉的还是6,栈里只剩5。
练习2:空栈上哪些调用不合法?
多选
S是一个空栈。下面哪些调用不合法?
A
Pop(S, &x)
空栈没有栈顶,没有东西可删。
B
GetTop(S, &x)
空栈没有栈顶,没有东西可取。
C
Push(S, 4)
空栈可以入栈。4放进来,既是栈顶,也是栈底。
D
StackEmpty(S)
任何时候都能问空不空。这里返回1。
GetTop和Pop都要用到栈顶,空栈没有栈顶,所以都不能调用。Push和StackEmpty不需要栈顶。
到这里你有了栈的五个操作InitStack、StackEmpty、GetTop、Push、Pop,以及栈的抽象数据类型。它们都没有i,因为位置总是栈顶。下一步把栈放进内存。