文档介绍：第十三讲栈
栈
知识点
栈的定义和特点
栈的基本运算和算法
栈的典型应用
难点
后缀表达式的算法
数制的换算
利用本章的基本知识设计相关的应用问题
要求
掌握栈的特点
掌握栈的基本运算
熟悉栈的各种实际应用
能设计栈的应用的典型算法
了解栈的运算时间复杂度分析
13-1 栈的定义和运算
13-1-1 栈(Stack)的定义
1. 栈的定义
    栈是限制在表尾进行插入和删除的线性表。
a1
a2
a3
进栈
出栈
图3-1栈的示意图
2. 栈的特性
(1)栈的主要特点是“后进先出”
(2)允许插入、删除的这一端称为栈顶(Top),另一端称为栈底(Bottom)。
3. 应用实例
(1)分币筒;
(2)铁路调度站。
13-1-2 栈的运算
: Push(&s,x)
初始条件:栈s已存在且非满。
操作结果:在栈顶插入一个元素x,栈中多了一个元素。
:Pop(&s)
初始条件:栈s存在且非空。
操作结果:删除栈顶元素,栈中少了一个元素。
:ReadTop(s,&e)
初始条件:栈s已存在且非空。
操作结果:输出栈顶元素,但栈中元素不变。
4. 判栈空:SEmpty(s)
初始条件:栈s已存在。
操作结果:若栈空则返回为0,否则返回为1。
5. 判栈满:SFull(s)
初始条件:栈s已存在。
操作结果:若栈满则返回为0,否则返回为1。
6. 显示栈元素:ShowStack (s)
初始条件:栈s已存在 ,且非空。
操作结果:显示栈中所有元素。
13-2 栈的存储和实现
13-2-1 顺序栈
1. 顺序栈的实现
(1) 用一维数组实现顺序栈
设栈中的数据元素的类型是字符型,用一个足够长度的一维数组s来存放元素,数组的最大容量为MAXLEN,栈顶指针为top,则顺序栈可以用C(或C++)语言描述如下:
#define MAXLEN 10 // 分配最大的栈空间
char s[MAXLEN]; // 数据类型为字符型
int top; // 定义栈顶指针
(2) 用结构体数组实现顺序栈
顺序栈的结构体描述:
#define MAXLEN 10 // 分配最大的栈空间
typedef struct // 定义结构体
{ datatype data[MAXLEN]; // datatype可根据用需要定义类型
int top; // 定义栈顶指针
} SeqStack;
再定义一个指向顺序栈的指针:
SeqStack *S; // 定义S为结构体类型的指针变量
(3)栈操作的示意图如图3-3所示。
A
F
E
D
C
B
A
F
E
D
C
B
A
J
I
H
G
F
E
D
C
B
A
top=-1
top=0
top=5
top=3
top=9
(a) (b) (c) (d) (e)