文档介绍：数据结构 第三章 栈和队列
主讲人:包晖
本章内容
栈
栈的应用举例
栈类型的实现
3-3
栈
栈的定义
ADT Stack {
数据对象:
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系:
R1={ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶,a1 端为栈底。
基本操作:
} ADT Stack
3-4
栈
栈的定义
栈(stack):是限定仅在表尾进行插入和删除操作的线性表。又称为后进先出(last in first out)的线性表(简称LIFO结构)。
栈顶(top):栈表尾端。
栈底(bottom):栈表头端。
例:假设栈 S=(a1,a2,…,an) ,则 a1 称
为栈底元素,an 为栈顶元素。栈中元素按
a1,a2,…,an 的次序进栈,退栈的第一个元
素应为栈顶元素。如右图所示。
出栈进栈
栈顶 an
.
.
.
a2
栈底 a1
栈的示意图
3-5
栈
初始化栈
InitStack(&S) 操作结果:构造一个空栈 S。
2. 销毁栈
DestroyStack(&S) 初始条件:栈 S 已存在。 操作结果:栈 S 被销毁。
3-6
栈
判断栈空
StackEmpty(S) 初始条件:栈 S 已存在。 操作结果:若栈 S 为空栈,则返回TRUE,否则 FALE。
4. 求栈的长度
StackLength(S) 初始条件:栈 S 已存在。 操作结果:返回 S 的元素个数,即栈的长度。
3-7
栈
5. 取得栈顶元素
GetTop(S, &e) 初始条件:栈 S 已存在且非空。 操作结果:用 e 返回 S 的栈顶元素。
a1
a2
an
……
3-8
栈
6. 清空栈
ClearStack(&S) 初始条件:栈 S 已存在。 操作结果:将 S 清为空栈。
3-9
栈
7. 入栈
Push(&S, e) 初始条件:栈 S 已存在。 操作结果:插入元素 e 为新的栈顶元素。
a1
a2
an
e
……
3-10
栈
8. 出栈
Pop(&S, &e) 初始条件:栈 S 已存在且非空。 操作结果:删除 S 的栈顶元素,并用 e 返回其值。
a1
a2
an
an-1
……