文档介绍：1)线性表
2)栈和队列
3)串
4)数组与广义表
第三章栈和队列
四类基本结构:
栈和队列的逻辑特征:
从数据结构角度讲,栈与队列也是线性表,不同之处在于其操作的特殊性(栈为LIFO,队列为FIFO),为操作受限的线性表。
从数据类型角度讲,栈和队列是与线性表不同的重要抽象数据类型,广泛的应用于各类软件系统中。
栈和队列的逻辑特征:
从数据结构的角度看: 它们和线性表相同
从数据类型的角度看: 它们和线性表不同
3. 1 栈
3. 2 栈的应用
*3. 3 栈与递归的实现
3. 4 队列
栈
抽象数据类型栈的定义
1. 基本概念
定义:栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。
an
.
.
.
a2
a1
栈顶
Top
栈底
Bottom
栈顶(Top)—表尾元素,
允许插入和删除的一端。
栈底(Bottom) —表头元素,不允许插入和删除的一端。
空栈—表中没有元素。
2. 栈的基本特征-- “很窄的死胡同”
栈——后进先出(LIFO,Last In First Out)。故栈又称为后进先出的线性表。
an
.
.
.
a2
a1
入栈
出栈
栈顶
栈底
入栈(PUSH)---最先插入的元素放在栈的底部。
出栈(POP)---最后插入的元素最先出栈。
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
3. 栈的抽象数据类型的定义
基本操作
初始化操作
销毁操作
引用型操作
加工型操作
InitStack( &S)
DestroyStack(&S )
GetTop(S , &e )
StackEmpty( S )
StackLength( S )
StackTraverse(S,visit())
Push(&S ,e)
Pop( &S , &e )
ClearStack( &S)
Push(&S, e) 初始条件:栈 S 已存在。 操作结果:插入元素 e 为新的栈顶元素。
a1
a2
an
e
……