文档介绍：第三章栈和队列
栈
栈的应用举例
队列
诈谭醋刷铆捧晦做呸危宋掷呈奈搭魔趴流芥绽靖力蜡向互潭戚皇的滇渤赞数据结构栈和队列数据结构栈和队列
栈和队列是两种重要的线性结构。
从数据结构角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表。
从数据类型角度看,它们是和线性表大不相同的两类重要的抽象数据类型。
由于它们广泛应用在各种软件系统中,因此在面向对象的程序设计中,它们是多型数据类型。
多型数据类型:指其值的成分不确定的数据类型。
从抽象数据类型角度看,具有相同的数学抽象特性,故称之为多型数据类型,需要借助面向对象程序设计语言,如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为栈顶指针,其