文档介绍：第三章栈和队列
中国海洋大学信息学院
魏振钢
Tel:0532-66781226
Email:******@ouc.
通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。
线性表栈队列
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)。
假设栈S={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 },则称a1为栈底元素,an为栈顶元素,栈中元素按a1,a2,…an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈又称为后进先出(last in first out)的线性表(简称LIFO表)。
抽象数据类型栈的定义
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
栈的抽象数据类型定义:
数据对象:D={ai| ai∈ElemSet, i=1,2,···,n, n≥0} 数据关系:R1={<ai-1, ai >|ai-1, ai∈D, i=1,2,···,n} 约定an端为栈顶,a1 端为栈底 基本操作: InitStack(&S) 操作结果:构造一个空栈 S。 DestroyStack(&S) 初始条件:栈 S 已存在。 操作结果:栈 S 被销毁。
ADT Stack {
StackEmpty(S) 初始条件:栈 S 已存在。 操作结果:若栈 S 为空栈,则返TRUE,否则 FALE。 StackLength(S) 初始条件:栈 S 已存在。 操作结果:返回 S 的元素个数,即栈的长度。
ClearStack(&S) 初始条件:栈 S 已存在。 操作结果:将 S 清为空栈。
GetTop(S, &e) 初始条件:栈 S 已存在且非空。操作结果:用 e 返回 S 的栈顶元素。
a1
a2
an
……
Push(&S, e) 初始条件:栈 S 已存在。 操作结果:插入元素 e 为新的栈顶元素。
a1
a2
an
e
……
Pop(&S, &e) 初始条件:栈 S 已存在且非空。 操作结果:删除 S 的栈顶元素,并用 e 返回其值
a1
a2
an
an-1
……
StackTraverse (S, visit()) 初始条件:栈 S 已存在。 操作结果:从栈底到栈顶依次对S 的每个数据元素调用函数visit()。一旦visit()失败,则操作失败。
} ADT Stack
栈的表示和实现
typedef struct {
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize;
} SqStack
其中, stacksize指示栈的当前可使用的最大容量。Top为栈顶指针,其初值指向栈底,每当插入新元素,指针top加1,删除栈顶元素时,指针top减1。非空栈中,top始终指向栈顶元素的下一个位置。
顺序栈的定义: