文档文本内容
本节内容
队列
顺序实现
王道考研/CSKAOYAN.COM知识总览
创、销、增、删、改、查
王道考研/CSKAOYAN.COM强调,当然也有别的设计方式,我们先按照这
种设计方式来分析
队列的顺序实现
内存
0
front
rear
5
data[9]
指向队尾元素
的后一个位置 data[8]
(下一个应该
data[7]
连续的存储空间,大小 插入的位置)
MaxSize*sizeof(ElemType) data[6]
Sq:sequence —— 顺序
rear
data[5]
e
data[4]
d
data[3]
c
data[2]
b
data[1]
指向队
front a
头元素 data[0]
王道考研/CSKAOYAN.COM初始化操作
内存
0
front
rear
1
0
data[9]
data[8]
data[7]
data[6]
data[5]
data[4]
data[3]
data[2]
data[1]
rear
a
data[0]
front
增删改查
王道考研/CSKAOYAN.COM只能从队尾入队(插入)
入队操作
内存
03
front
10
rear 1 0
队列已满的条件:
j
data[9]
rear==MaxSize ???
i
data[8]
h
data[7]
g
data[6]
f
data[5]
e
data[4]
d
data[3]
c
data[2]
b
data[1]
rear
a
data[0]
front
王道考研/CSKAOYAN.COM
备忘:删除队头元素后,可以像顺序表那样把后序元素都往前挪只能从队尾入队(插入)
入队操作
内存
3
front
rear 9
0
rear
j
data[9]
i
data[8]
h
data[7]
g
data[6]
f
data[5]
e
data[4]
d
data[3]
front
data[2]
模运算将无限的整数
域映射到有限的整数 data[1]
{0, 1, 2, …, MaxSize-1}
集合 {0, 1, 2, …, b-1} 上
将存储空间在逻辑上 data[0]
变成了“环状”
跨考Tips:取模运算,即取余运算。两个整数 a,b,a%b == a除以b的余数
在《数论》中,通常表示为 a MOD b
王道考研/CSKAOYAN.COM用模运算将存储空间在
循环队列
逻辑上变成了“环状”
内存
3
front
rear 0 29
rear
j
data[9]
k0
i
data[8]
9j 1l 队列已满的条件:队尾指针
h
的再下一个位置是队头,即 data[7]
(Q.rear+1)%MaxSize==Q.front g
rear data[6]
f
8i rear 2 data[5]
rear
e
代价:牺牲一 data[4]
个存储单元
front d
data[3]
front
data[2]
h d
7 3
l
data[1]
k
data[0]
6 g e4
f
5
王道考研/CSKAOYAN.COM循环队列 入队操作
——
k0
9j 1l
判断
队空
8i 2
rear
front
判断
h d
7 3
队满
6 g e4
f
5
用模运算将存储空间在
逻辑上变成了“环状”
王道考研/CSKAOYAN.COM循环队列 出队操作
—— 只能让队头元素出队
k0
9j 1l
判断队空
front
front
front
front
8i 2
rear
front
front
队头指针后移
front
h d
7 3
front
front
front
6 g e4
f
5
王道考研/CSKAOYAN.COM队列元素个数: 方案一:判断队列已满 / 已空
(rear+MaxSize-front)%MaxSize
初始化时
k0
rear=front=0
9j 1l
出题老师:不准
浪费这可怜孤独
的存储空间!!!
0
8i 2 9 1
rear
rear
front 8 2
h 7 d 3 front
队空条件:
7 3
Q.rear==Q.front
g
6 e4
f
5 6 4
队列已满的条件:队尾指针
5
的再下一个位置是队头,即
(Q.rear+1)%MaxSize==Q.front
王道考研/CSKAOYAN.COM方案二:判断队列已满 已空
/
队列元素个数 = size
插入成功 size++;
k0
删除成功 size--;
初始化时
rear=front=0;
9j 1l
size = 0;
0
8i m 2 size==MaxSize-1 9 1
rear
size==1
队空条件:
8 m2
front
rear size == 0;
h d size==MaxSize
7 3
front
rear
7 3
front
6 g e4 队满条件:
size==0
size==MaxSize
f
5 6 4
5
王道考研/CSKAOYAN.COM方案三:判断队列已满 已空
/
队列元素个数:
(rear+MaxSize-front)%MaxSize
每次删除操作成功时,都令tag=0;
每次插入操作成功时,都令tag=1;
k0 初始化时
rear=front=0;
9j 1l 只有删除操作,才可能导致队空
tag = 0;
只有插入操作,才可能导致队满
0
8i m2 tag==? 9 1
rear
tag=?
队空条件:
8 m2
front==rear &&ftraogn=t= 0
rear
h d tag==1
7 3
front
rear
7 3
front
队满条件:
g
6 e4
front==rear && tag == 1
tag==0
f
5 6 4
5
王道考研/CSKAOYAN.COM其他出题方法
内存
内存
0
0
front
front
初始时队尾指针指
rear
rear 4
5 向哪更合理?
入队操作: data[9]
指向队尾元素 data[9]
的后一个位置 data[8]
data[8]
(下一个应该
data[7]
data[7]
插入的位置)
data[6]
data[6] 入队导致
rear rear 后移 data[5]
data[5]
e 指向队尾元素 rear dat e a[4]
data[4]
d
d data[3]
data[3]
出队操作
c
c data[2]
data[2]
b
b data[1]
data[1]
指向队
front a
front a data[0]
头元素 data[0]
指向队
头元素
王道考研/CSKAOYAN.COM其他出题方法
内存
0
判空:
front
初始时队尾指针指
(Q.rear+1)%MaxSize==Q.front
rear
4
向哪更合理?
data[9]
0
data[8]
9 1
data[7]
front data[6]
指向队尾元素
8 2
data[5]
rear
rear dat e a[4]
d
data[3]
7 3
c
data[2]
b
data[1]
6 4
front a
data[0]
5
指向队
头元素
王道考研/CSKAOYAN.COM其他出题方法
方案一:牺牲一个存储单元
方案二:增加辅助变量
判空: 判满:
(Q.rear+1)%MaxSize==Q.front (Q.rear+1)%MaxSize==Q.front?
0 k0
9 1 9j 1 l
front front
8 2 8i m2
rear rear
h
7 3 7 d3
6 4 g 6 e4
5 f5
王道考研/CSKAOYAN.COM知识回顾与重要考点
思考:分别采用
①a、①b、①c
②a、②b、②c
策略时,这些操作怎么实现?
王道考研/CSKAOYAN.COM