第4周栈和队列第3讲-队列的定义和顺序队.pdf
《第4周栈和队列第3讲-队列的定义和顺序队.pdf》由会员分享,可在线阅读,更多相关《第4周栈和队列第3讲-队列的定义和顺序队.pdf(32页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、队列简称队列简称队队,它也是一种运算受限的,它也是一种运算受限的线性表。线性表。 3.2.1 队列的定义队列的定义 队列只能队列只能选取一个端点进行插入操作,另一个端点进行选取一个端点进行插入操作,另一个端点进行 删除操作删除操作 端点端点1端点端点2 线线 性性 表表 把把进行插入的一端称做进行插入的一端称做队尾队尾(rear)。)。 进行进行删除的一端称做删除的一端称做队首队首或或队头队头(front)。)。 向向队列中插入新元素称为队列中插入新元素称为进队进队或或入队入队,新元素进队后就成为新,新元素进队后就成为新 的队尾的队尾元素。元素。 从从队列中删除元素称为队列中删除元素称为出队出
2、队或或离队离队,元素出队后,其后继元素,元素出队后,其后继元素 就成为队首元素。就成为队首元素。 队尾队尾队头队头 队列示意图队列示意图 出队出队 进队进队 队列的几个概念队列的几个概念 队列队列的主要特点是先进先出,所以又把队列称为的主要特点是先进先出,所以又把队列称为先进先出表先进先出表。 假如假如5个人个人 过独木桥过独木桥 只能按上桥的只能按上桥的 次序过桥次序过桥 这里独木桥就是一个队列这里独木桥就是一个队列 例如:例如: 队列的基本运算如下:队列的基本运算如下: InitQueue( 顺序队类型顺序队类型SqQueue定义如下:定义如下: 因为队列两端因为队列两端都在变化,所以需要
3、两个指针来标识队列的都在变化,所以需要两个指针来标识队列的 状态。状态。 队列队列 (a1, a2, ,ai, , an ) 映射映射 a1anf MaxSize-1 ff+1r data front 顺序顺序队队的示意图的示意图 逻辑结构逻辑结构 存储结构存储结构 0 r rear 例如:例如:MaxSize=5 4 3 2 1 0 rear (a)空队)空队(b)a进队进队 (c)b、c、 d、e进队进队 (d)全部出队)全部出队 总总 结结 约定约定rear总是指向队尾元素总是指向队尾元素 元素进队,元素进队,rear增增1 约定约定front指向当前队中队头元素的前一位置指向当前队中队
4、头元素的前一位置 元素出队,元素出队,front增增1 当当rear=MaxSize- -1时不能再进队时不能再进队 front 4 3 2 1 a0 front rear e4 d3 c2 b1 a0 front rear4 3 2 1 0 front rear 顺序队顺序队的的4要素要素(初始时(初始时front=rear=- -1):): 队队空条件空条件:front = rear 队队满条件满条件:rear = MaxSize1 元素元素e进队:进队:rear+; datarear=e; 元素元素e出队:出队:front+; e=datafront; 队列的各种状态队列的各种状态 4
5、3 2 1 0 rear front 4 3 2 1 a0 front rear e4 d3 c2 b1 a0 front rear4 3 2 1 0 front rear (a)空队)空队(b)a进队进队 (c)b、c、d、 e进队进队 (d)全部出队)全部出队 1、 顺序顺序队中队中实现队列的基本运算实现队列的基本运算 (1)初始化队列)初始化队列InitQueue(q) 构造构造一个空队列一个空队列q。将。将front和和rear指针均设置成初始状态即指针均设置成初始状态即- -1值。值。 void InitQueue(SqQueue * q-front=q-rear=-1; 4 3 2
6、 1 0 rear front (2)销毁队列)销毁队列DestroyQueue(q) 释放队列释放队列q占用的存储空间。占用的存储空间。 void DestroyQueue(SqQueue * (3)判断队列是否为空)判断队列是否为空QueueEmpty(q) 若若队列队列q满足满足q- -front=q- -rear条件,则返回条件,则返回true;否则返回;否则返回false。 bool QueueEmpty(SqQueue *q) return(q-front=q-rear); (4)进队列)进队列enQueue(q,e) 若队列不满,将若队列不满,将队尾指针队尾指针rear循环增循环
7、增1,然后将元素添加到该位置。,然后将元素添加到该位置。 bool enQueue(SqQueue * q-rear+; q-dataq-rear=e; return true; 4 3 2 1 a0 front rear 4 3 2 1 0 rear front 空队:空队: 元素元素a进队进队 (5)出队列)出队列deQueue(q,e) 若若队列队列q不空,不空,将队首指针将队首指针front循环增循环增1,并将该位置的元素值赋给,并将该位置的元素值赋给e。 bool deQueue(SqQueue * q-front+; e=q-dataq-front; return true; 4
8、d3 c2 b1 0 front rear出队一出队一个元素个元素b 4 d3 c2 1 0 front rear 2、环形、环形队列(或循环队列)中实现队列的基本运算队列(或循环队列)中实现队列的基本运算 c4 b3 a2 1 0 front rear 这这是因为采用是因为采用rear=MaxSize- -1作为队满条件的缺陷作为队满条件的缺陷。当当 队满条件为真时队满条件为真时,队中可能还有若干空位置队中可能还有若干空位置。 这种这种溢出并不是真正的溢出并不是真正的溢出溢出,称为称为假假溢出溢出。 还有两个位置,还有两个位置, 为何不能进队?为何不能进队? 把把数组的前端和后端连接起来数组
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 森林经营规划
限制150内