数据结构之栈和队列.ppt

文档介绍：第三章
1
栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
线性表 栈 队列
Insert(L, i, x) Insert(S, n, x) Insert(Q, n, x)
1≤i≤n+1
Delete(L, i) Delete(S, n) Delete(Q, 1)
1≤i≤n
栈和队列是两种常用的数据类型
2
栈的类型定义
栈的应用举例
栈类型的实现
队列的类型定义
队列类型的实现
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
4
a n
a n-1
a2
a1
……
栈顶(top)
栈底(base)
5
InitStack(&S)
DestroyStack(&S)
ClearStack(&S)
StackEmpty(S)
StackLength(S)
GetTop(S, &e)
Push(&S, e)
Pop(&S, &e)
StackTravers(S, visit())
6
InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。
7
StackEmpty(S)初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALSE。
8
StackLength(S)初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。
9
GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。
a1
a2
an
… …
10