第3章 栈和队列.ppt

第三章栈和队列
通常称,栈和队列是限定只能在表的“端点”进行插入和删除的线性表。
线性表栈队列
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
栈和队列是两种常用的数据类型
栈
栈的类型定义
栈的表示和实现
栈的应用举例
栈与递归的实现
队列
队列的类型定义
队列的链式表示和实现
循环队列-队列的顺序表示和实现
离散事件模拟
栈(Stack) 是限制仅在表尾进行插入和删除运算的线性表。
栈
通常称执行插入、删除的表尾端为栈顶(Top),另一端为栈底(Bottom)。不含元素的空表称为空栈。
栈称为后进先出(LIFO)的线性表。
栈的示意图
a n
a n-1
a2
a1
……
栈顶
栈底
出栈
进栈
假设有一个栈 S= (a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。
栈的类型定义
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, &e)
Push(&S, e)
Pop(&S, &e)
StackTravers(S, visit())
InitStack(&S) 操作结果:构造一个空栈 S。 DestroyStack(&S) 初始条件:栈 S 已存在。 操作结果:栈 S 被销毁。
StackLength(S)初始条件:栈 S 已存在。 操作结果:返回 S 的元素个数,即栈的长度。
StackEmpty(S)初始条件:栈 S 已存在。 操作结果:若栈 S 为空栈,则返回 TRUE,否则 FALE。