文档介绍：数据结构 Data Structure
回顾
线性结构的特点
顺序表的插入、删除
单链表的插入、删除
第三章
通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
线性表栈队列
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
栈和队列是两种常用的数据类型
栈的类型定义
栈的应用举例
队列的类型定义
队列类型的实现
特殊线性表——栈
栈的逻辑结构
空栈:不含任何数据元素的栈。
(a1, a2, ……, an)
栈:限定仅在表尾进行插入和删除操作的线性表。
栈顶
栈底
允许插入和删除的一端称为栈顶,另一端称为栈底。
a1
a2
a3
入栈
出栈
栈底
栈顶
特殊线性表——栈
插入:入栈、进栈、压栈
删除:出栈、弹栈
栈顶
栈顶
栈的示意图
栈顶
栈的操作特性:后进先出
a1
a2
a3
入栈
出栈
栈底
栈顶
特殊线性表——栈
插入:入栈、进栈、压栈
删除:出栈、弹栈
栈顶
栈的示意图
栈顶
栈的类型定义
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())