数据结构与算法设计堆栈、队列和字符串.ppt

文档介绍：Stack 、Queue & String
栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
线性表栈队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)
1≤i≤n+1
Delete(L, i) Delete(S, n) Delete(Q, 1)
1≤i≤n
栈和队列是两种常用的数据类型
Section 1Stack
只允许在一端插入和删除的线性表
允许插入和删除
的一端称为栈顶
(top),另一端称
为栈底(bottom)
特点
后进先出(LIFO)
栈( Stack )
退栈
进栈
a0
an-1
an-2

top
bottom
栈的抽象数据类型定义
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
InitStack(&S)
DestroyStack(&S)
ClearStack(&S)
StackEmpty(s)
StackLength(S)
GetTop(S, &x)
Push(&S, x)
Pop(&S, &x)
InitStack(&S) 操作结果:构造一个空栈 S。 DestroyStack(&S) 初始条件:栈 S 已存在。 操作结果:栈 S 被销毁。
StackEmpty(S)初始条件:栈 S 已存在。 操作结果:若栈 S 为空栈,  则返回 TRUE,  否则 FALE。
StackLength(S)初始条件:栈 S 已存在。操作结果:返回 S 的元素 个数,即栈的 长度。
GetTop(S, &x)初始条件:栈 S 已存在且非空。 操作结果:用 x 返回 S 的栈顶 元素。
a1
a2
an
……