文档介绍：第3章栈和队列
教学目标
栈
栈的定义
栈的顺序存储结构及其基本实现
栈的链式存储结构及其基本实现
队列
队列的定义
队列的顺序存储结构及其基本实现
队列的链式存储结构及其基本实现
本章小结
队列
队列的定义
队列的顺序存储结构及其基本实现
温故知新环节
特殊线性表——队列
队列的逻辑结构
队列:只允许在一端进行插入操作,而另一端进行删除操作的线性表。
队尾
队头
a1
a2
a3
入队
出队
队列的操作特性:
先进先出
循环队列:将存储队列的数组头尾相接。
如何解决假溢出?
0 1 2 3 4
入队
出队
a3
a4
front
a5
rear
rear
a6
队列的顺序存储结构及实现(顺序队列)
不存在物理的循环结构,但可用软件方法实现。
求模:(4+1)mod 5=0
【0】
【1】
【2】
【3】
【4】
【5】
C
D
E
front
rear
B
MaxSize=6
char data[MaxSize];
rear=5
rear=?
data[rear]=‘F’;
rear=(rear+1)%MaxSize
队列的顺序存储结构及其实现--- 问题一
循环队列首尾相连, 这可以利用除法取余的运算(%)来实现:
队首指针进1:front=(front+1)%MaxSize
队尾指针进1:rear=(rear+1)%MaxSize
队空和队满的条件都是 front=rear,如何区分?
rear
0
1
2
3
4
front
(a)
空队
rear
0
1
2
3
4
front
(e)
出队
多
次
,
队空
front==rear
rear
0
1
2
3
4
front
(e)
,
队满
A
B
C
D
E
front==rear
队列的顺序存储结构及其实现--- 问题二
怎样区分队空与队满之间的差别呢?在入队时少用一个数据元素空间,以队尾指针加1等于队首指针判断队满,即队满条件为:
(q->rear+1) % MaxSize==q->front
队空条件仍为:
q->rear==q->front
1号题
2号题
温故知新环节
3号题
4号题
1号题
栈和队列都是()(南京理工)
顺序存取的线性结构
链式存储的非线性结构
限制存取点的线性结构
限制存取点的非线性结构
温故知新环节