数据结构(栈与队列).ppt

文档介绍：第三章栈与队列
栈的类型定义
栈的应用举例
栈类型的实现
队列的类型定义
队列类型的实现
第三章栈与队列
本章主要内容:
本章重点:
栈的类型定义
栈的应用举例
队列的类型定义
本章难点:
栈的应用举例
栈和队列是两种常用的数据类型
栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性DS
只能在表的“端点”插入和删除进行的线性表
栈的类型定义
1. 栈(stack)的定义和特点
定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈
特点:先进后出(FILO)或后进先出(LIFO)
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,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 被销毁。
StackEmpty(S)初始条件:栈 S 已存在。 操作结果:若栈 S 为空栈,则返回 TRUE,否则 FALSE。
StackLength(S)初始条件:栈 S 已存在。 操作结果:返回 S 的元素个数,即栈的长度。