文档介绍：20 十一月 2017
1
第三章栈和队列
20 十一月 2017
2
从数据结构上看,栈和队列也是线性表,不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作,而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而,栈和队列也可以被称作为操作受限的线性表。通过本章的学****读者应能掌握栈和队列的逻辑结构和存储结构,以及栈和队列的基本运算以及实现算法。
本章学****导读
20 十一月 2017
3
栈
抽象数据类型栈的定义
栈的表示和实现
顺序栈定义及基本操作
链式栈定义及基本操作
两个栈共享数组空间
栈的应用举例
数制转换
括号匹配的检验
行编辑程序
表达式求值
队列
抽象数据类型队列的定义
链队列-队列的顺序表示和实现
循环队列-队列的顺序表示和实现
本章重点内容
20 十一月 2017
4
栈的逻辑结构
空栈:不含任何数据元素的栈。
(a1, a2, ……, an)
栈:(Stack)是限制仅在表的一端进行插入和删除
运算的线性表。
栈顶
栈底
允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)。
栈的定义及其运算
20 十一月 2017
5
a1
a2
a3
入栈(push)
出栈(pop)
栈底
栈顶
插入:入栈、进栈、压栈
删除:出栈、弹栈
栈顶
栈顶
栈的示意图
栈的定义及其运算
20 十一月 2017
6
栈的操作特性:后进先出(LIFO)
修改原则:退栈者总是最近入栈者
服务原则:后来者先服务(LIFO表)
a1
a2
a3
入栈
出栈
栈底
栈顶
插入:入栈、进栈、压栈
删除:出栈、弹栈
栈顶
栈的示意图
栈的定义及其运算
20 十一月 2017
7
a0
a1
an-1
入栈
出栈
栈顶 top
栈底 bottom
图3-3栈的示意图
...
图3-3是一个栈的示意图,通常用指针top指示栈顶的位置,用指针bottom指向栈底。栈顶指针top动态反映栈的当前位置。
20 十一月 2017
8
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)
StackLength(S)
StackEmpty(s)
GetTop(S, &e)
ClearStack(&S)
Push(&S, e)
Pop(&S, &e)
StackTravers(S, visit())
20 十一月 2017
9
顺序栈:栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
①顺序栈中元素用数组存放;
②栈底位置是固定不变的,可设置在数组两端的任意一个端点;例如设在下标值大的一端;
③栈顶位置是随着进栈和退栈操作而变化的,用一个整型量top(通常称top为栈顶指针)来指示当前栈顶位置;
④“上溢”现象:栈已满还要执行Push()操作或top指向超过数组的最大值;
⑤“下溢”现象:没有栈元素时还要执行Pop()或getTop()操作;
栈的表示和实现
1、顺序存储
20 十一月 2017
10
类似于线性表的顺序映象实现, 顺序栈的类型定义只需将顺序表的类型定义中的长度属性(length)改为top即可。
//----- 栈的顺序存储表示-----
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct {
ElemType elem[STACK_INIT_SIZE]
int top; //存放指向栈顶的指针
} SqStack;
栈的表示和实现
1、顺序存储