文档介绍：第三章栈和队列
本章内容
栈
栈的定义及基本运算
栈的存储结构和实现
栈的应用
队列
队列的定义及基本运算
队列的存储结构和实现
队列的应用
栈的定义及基本运算
栈(Stack)的定义
–栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(top),另一端为栈底(bottom)。当表中没有元素时称为空栈。
an
an-1
...
a2
a1
栈底
栈顶
入栈
出栈
栈的特点
栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。
栈的定义及基本运算
栈的运算演示
(1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。
D
C
B
A
ABCD
DCBA
栈的定义及基本运算
栈的运算演示
(1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。
(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE?
ABCDE
操作序列:
出栈序列:
①元素A入栈
A
A
②元素B入栈
B
B
③元素C入栈
C
C
栈的定义及基本运算
栈的运算演示
(1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。
(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE?
DE
操作序列:
出栈序列:
①元素A入栈
A
②元素B入栈
B
③元素C入栈
④元素C出栈
C
C
⑤元素B出栈
B
栈的定义及基本运算
栈的运算演示
(1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。
(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE?
DE
操作序列:
出栈序列:
①元素A入栈
A
②元素B入栈
③元素C入栈
④元素C出栈
C
⑤元素B出栈
B
⑥元素D入栈
D
D
⑦元素D出栈
D
⑧元素A出栈
A
栈的定义及基本运算
栈的运算演示
(1)A、B、C、D四个元素依次进入一个栈,再依次出栈,得到一个输出序列DCBA。
(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE?
E
操作序列:
出栈序列:
①元素A入栈
②元素B入栈
③元素C入栈
④元素C出栈
C
⑤元素B出栈
B
⑥元素D入栈
⑦元素D出栈
D
⑧元素A出栈
A
⑨元素E入栈
E
E
⑩元素E出栈
E
栈的基本运算
InitStack(&S): 初始化栈S
StackEmpty(): 判断栈是否为空
Push(e): 将元素e放入栈顶
Pop(e): 移走栈顶的元素,同时由e带回该元素的值
Gettop(): 获取栈顶的元素,但不从栈中移走
栈的定义及基本运算
栈的存储结构和实现
an
an-1
...
a2
a1
栈
base
top
•栈的表示和实现
假设栈S=(a1,a2,a3,…,an),则a1称为栈底元素,an为栈顶元素。栈中元素按a1,a2,a3,…,an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(Last In First Out,LIFO)
栈的存储结构和实现
•顺序栈
–由于栈是运算受限的线性表,因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈,它是运算受限的线性表。因此,可用数组来实现顺序栈。