数据结构队列ppt课件.ppt

《数据结构队列ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构队列ppt课件.ppt（38页珍藏版）》请在三一办公上搜索。

1、第二章 队列,吉林大学计算机学院谷方明,例子：电话号码,向计算机专业的同学要电话号码，他（她）不会直接给你的，原因你懂的。他（她）会告诉你一串加密过的数字，同时告诉你解密的规则。规则是这样的：首先将第1个数删除，紧接着将第2个数放到这串数的末尾，再将第3个数删除并将第4个数放到这串数的末尾，直到剩下最后一个数，把这个数也删除。按删除的顺序将删除的数连在一起，就是电话号了。例如：58659146,1. 队列的定义,队列（queue）是一种操作受限的线性表，它的所有插入都在表的一端进行，所有的删除都在表的另一端进行。例子食堂窗口进程调度队列的特性：先进先出。栈也称作后进先出表(First In F

2、irst Out，FIFO)。,队头（front） ：进行删除的一端；队尾（rear） ：进行插入的一端；空队列：没有元素的队列。插入：入队删除：出队,术语,队列的基本操作,（1）队列初始化（2）入队 (插入）（3）出队（删除）（4）读取队首元素（5）判断队列是否空 （6）确定队列中元素个数 （7）置空队列,2.队列的顺序存储,按顺序存储方式存放队列元素，称为顺序队。存放队列元素的数组：T qlistMaxQSize front 队首元素的下标 rear 队尾元素的下标加 1队列空： front = rear队列满： rear = MaxQSize,插入队尾元素： rear=rear+1,删除

3、队首元素：front=front+1,假溢出,循环队列,插入元素 ： rear顺时针移动一位,rear = (rear+1) MOD MaxQSize,删除元素：front顺时针移动一位,front = (front+1) MOD MaxQSize;,循环队列,front指定队首位置，删除一个元素就将front顺 时针移动一位； rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位； count存放队列中元素的个数，当count等于MaxQSize时，不可再向队列中插入元素。 队空：count=0队满：count= MaxQSize,顺序队列类AQueue的类声明templat

4、e class AQueueprivate: int front ;/ 队首所在数组元素下标 int rear ; / 新元素要插入的位置（下标） int count ; / 队列中元素个数 T *QArray ; / 存放队列元素的数组 int Size ;/ 存放队列的数组规模public: AQueue ( int MaxQueueSize = 10 ); / 构造函数 AQueue () delete QArray ; / 析构,void QInsert ( const T/ 清空队列；,插入算法ADL描述,算法QInsert (A, item)/ 在队列A中将元素item插入队尾QI

5、1. 队列满？IF countsize THEN (PRINT“队列已满无法插入”. RETURN. )QI2. 元素插入 Arear item. / 将新元素插入队尾QI3. 更新 rearMOD(rear1, size). / 更新队尾下标 countcount1. / 更新队列长度 ,C+实现,template void AQueue:QInsert ( const T,删除算法ADL描述,算法QDelete (A. item)/ 删除队列A的队首元素，并将其元素值赋给变量itemQD1. 队列空？IF count0 THEN (PRINT “队列空无法删除”. RETURN. )QD2

6、. 出队 item Afront. / 将队首元素保存至itemQD3. 更新 frontMOD(front1, size). / 更新队首元素下标 countcount -1. / 更新队列长度 ,C+实现,template void AQueue:QDelete (T,取队首算法ADL描述,算法QFront (A. item) / 读取队列A的队首元素值，并将其赋给变量itemQF1. 队列空？IF count0 THEN (PRINT “队列空无法读取”. RETURN. )QF2. 存取 item Afront. / 将队首元素保存至item ,C+实现,template T AQue

7、ue:QFront () constreturn QArrayfront;,验证：#include aqueue.h,int main()int n,i,x;AQueue s(100);cinn;for(i=1;i=n;i+) s.QInsert(i);for(i=1;i=n;i+) s.QDelete(x); coutxendl; ,队列运行示意图,3.队列的链接存储,template class NodeT data; Node* next;,链队LQueue的类定义,template class LQueue private:Node * front, * rear ; / 指向队首和队

8、尾的指针public:LQueue ( void ) front = rear = NULL; / 构造函数 LQueue ( void ) QClear ( ) ; / 析构函数,void QInsert ( const T/ 清空队列；,插入算法ADL描述,算法QInsert (item) / 将元素item插入队尾QI1. 创建新结点 s AVAIL. data(s)item. next(s)NULL. / 为新结点申请空间，令其字段值为item，指针域为空QI2. 队空？ IF frontNULL THEN fronts. /若队列为空，令队首指针指向s ELSE next(rear)

9、s. /若队列非空，令表尾结点的next指针指向sQI3. 更新队尾指针 rears. / 更新表尾指针,C+实现,void LQueue:QInsert ( const T,删除算法ADL描述,算法QDelete (item) / 删除队首结点并将其字段值存于itemQD1. 队列空？ IF frontNULL THEN (PRINT “队列为空”. RETURN. )QD2. 出队 qfront. itemdata(q). / 令指针q指向队首，并保存其字段值 frontnext(front). / 令队首指针指向原队首结点之后继结点 AVAILq. / 释放原队首结点的存储空间QD3.

10、出队后队列空？ IF frontNULL THEN rearNULL. / 若删除队首结点后队列为空，则令队尾指针修为空,C+实现,template void LQueue:QDelete (T,取队首算法ADL描述,算法QFront (item) / 读取队首元素值，并将其赋给变量itemQF1. 队列空？ IF frontNULL THEN (PRINT “队列空无法读取”. RETURN. )QF2. 存取 item data(front). / 将队首元素保存至item,C+实现,template T LQueue:QFront () const if(front) return fr

11、ont-data;,验证：#include “lqueue.h,int main()int n,i,x;LQueue s;cinn;for(i=1;i=n;i+) s.QInsert(i);for(i=1;i=n;i+) s.QDelete(x); coutxendl; ,顺序队列与链式队列的比较,在空间复杂性上，顺序队列必须初始就申请固定的空间，当队列不满时，必然造成空间的浪费；链式队列所需空间是根据需要随时申请的，其代价是为每个元素提供空间以存储其next指针域。在时间复杂性上，对于队列的基本操作（入队、出队和存取），顺序队列和链式队列的时间复杂性均为O(1) .,STL中关于栈的实现,#include queue s; /不用声明大小s.push(x);s.front(); /取队首s.pop(); /只弹出队首，与front合用,课后练习,oj.org 注册数据较大时，使用scanf和printfpoj1363 railspoj3250 Bad Hair Day,