数据结构PPT教学课件-第3章_栈和队列.ppt

第三章栈和队列
栈
栈的应用举例
队列
栈和队列是两种重要的线性结构。
从数据结构角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表。
从数据类型角度看,它们是和线性表大不相同的两类重要的抽象数据类型。
由于它们广泛应用在各种软件系统中,因此在面向对象的程序设计中,它们是多型数据类型。
多型数据类型:指其值的成分不确定的数据类型。
从抽象数据类型角度看,具有相同的数学抽象特性,故称之为多型数据类型,需要借助面向对象程序设计语言,如C++等实现。
栈
抽象数据类型栈的定义
栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。
当表中没有元素时称为空栈。
假设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…an的次序进栈,退栈的第一个元素应为栈顶元素。
换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。
假设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…an的次序进栈,退栈的第一个元素应为栈顶元素,次序却是an,an-1,…,a1。
栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO),也可称为先进后出(FILO)。
a1
top
bottom
an
.
.
.
.
进栈
出栈
栈的示意图
栈的基本操作演示
栈的表示和实现
由于栈是运算受限的线性表,因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈,它是运算受限的线性表。因此,可用数组来实现顺序栈。
因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点;栈顶位置是随着进栈和退栈操作而变化的,故需用一个整型变量top(栈顶指针),指示栈顶元素在顺序栈中的位置。
顺序栈:栈的顺序存储结构,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,指针top指向栈顶元素在顺序栈中的下一个位置,base为栈底指针,指向栈底的位置。
base
空栈
top
a 进栈
a
base
top
b 进栈
a
b
base
top
top
a
b
c
d
e
e 进栈
base
top
a
b
c
d
e
f 进栈溢出
base
a
b
d
e 出栈
c
base
top
空栈的通常表示方法是:top=0;
鉴于C语言中数组的下标约定从0开始,则当以C做描述语言时,如此设置会带来很大的不便;
另一方面,由于栈在使用过程中所需最大空间的大小很难估计,因此,一般来说,在初始化设空栈时不应限定栈的最大容量。
一个较合理的做法是:
先为栈分配一个基本容量;
然后在应用过程中,当栈的空间不够使用时在逐段扩大;
为此,需要设定两个常量:STACK_INIT_SIZE(存储空间初始分配量)和STACKINCREMENT(存储空间分配增量)。
比较合理的顺序栈的定义
Typedef struct {
StackData *base; //栈底指针
StackData *top; //栈顶指针
int stacksize; //当前栈可使用的最大容量
}SeqStack;
栈的初始化操作:按设定的初始分配量进行第一次存储分配;
base为栈底指针,在顺序栈中始终指向栈底的位置;如果base的值为NULL,则表明栈结构不存在。
top为栈顶指针,其初值指向栈底:即top=base可作为栈空的标记,同时每当插入新的栈顶元素时,指针top增1;删除栈顶元素时,指针top减1;
非空栈中的栈顶指针始终在栈顶元素的下一位置上。