数据结构-队列课件.ppt

1、第二章第二章 队列队列吉林大学计算机学院谷方明例子：电话号码例子：电话号码p向计算机专业的同学要电话号码，他（她）不会向计算机专业的同学要电话号码，他（她）不会直接给你的，原因你懂的。直接给你的，原因你懂的。p他（她）会告诉你一串加密过的数字，同时告诉他（她）会告诉你一串加密过的数字，同时告诉你解密的规则。规则是这样的：首先将第你解密的规则。规则是这样的：首先将第1个数个数删除，紧接着将第删除，紧接着将第2个数放到这串数的末尾，再个数放到这串数的末尾，再将第将第3个数删除并将第个数删除并将第4个数放到这串数的末尾个数放到这串数的末尾，直到剩下最后一个数，把这个数也删除。按删除直到剩下最后一个数

2、，把这个数也删除。按删除的顺序将删除的数连在一起，就是电话号了。的顺序将删除的数连在一起，就是电话号了。p例如：例如：586591461.队列的定义队列的定义p队列（队列（queue）是一种操作受限的线性表，）是一种操作受限的线性表，它的所有它的所有插入都在表的一端进行，所有的删除都在表的另一端插入都在表的一端进行，所有的删除都在表的另一端进行进行。p例子例子食堂窗口进程调度p队列的特性：先进先出。队列的特性：先进先出。栈也称作后进先出表栈也称作后进先出表(First In First Out，FIFO)。p队头队头（frontfront）：进行删除的一端；p队尾队尾（rearrear）：进行

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

4、标元素的下标 rear 队尾队尾元素的元素的下标下标加加 1队列空：front=rear队列满：rear=MaxQSize 012MaxQsize-1front=0rear=0初始初始状态状态p插入队尾元素：插入队尾元素：rear=rear+1front=0rear=1a0012MaxQsize-1a0进队进队 front=0a0a1a2012MaxQsize-1a1 a2进队进队rear=3p删除队首元素：删除队首元素：front=front+1front=1a1a2012MaxQsize-1a0出队出队rear=3front=3012MaxQsize-1a1 a2出队出队rear=3假溢出

5、假溢出012MaxQsize-1rear=nfront=n-3 an-3an-2 无法利用的空间无法利用的空间循环队列循环队列front=n-3 an-3an-2012MaxQsize-1rear=n-1n-3rear=n-1an-3an-20.1.front=n-3n-2插入元素插入元素：rear顺时针移动一位顺时针移动一位front=n-3 an-3an-2012MaxQsize-1rear=0 xn-3an-3rear=0an-20.1n-1.front=n-3n-2xrear=(rear+1)MOD MaxQSize删除元素：删除元素：front顺时针移动一位顺时针移动一位front=

6、(front+1)MOD MaxQSize;rear0front=9.1.CD删除删除Crearfront=00.1.D循环队列循环队列pfront指定队首位置，删除一个元素就将指定队首位置，删除一个元素就将front顺顺 时针时针移动一位；移动一位；p rear指向元素要插入的位置，插入一个元素指向元素要插入的位置，插入一个元素就将就将rear顺时针顺时针移动一位；移动一位；p count存放队列中元素的个数，当存放队列中元素的个数，当count等于等于MaxQSize时，不可再向队列中插入元素。时，不可再向队列中插入元素。队空：count=0队满：count=MaxQSize顺序队列类顺序

7、队列类AQueue的类声明的类声明template class AQueue private:int front;/队首所在数组元素下标队首所在数组元素下标 int rear;/新元素要插入的位置（下标）新元素要插入的位置（下标）int count;/队列中元素个数队列中元素个数 T*QArray;/存放队列元素的数组存放队列元素的数组 int Size;/存放队列的数组规模存放队列的数组规模public:AQueue(int MaxQueueSize=10);/构造函数构造函数 AQueue()delete QArray;/析构析构void QInsert(const T&item);/向队

8、尾插入元素向队尾插入元素itemvoid QDelete(T&item);/删除队首元素并将该元素值保存至删除队首元素并将该元素值保存至itemT QFront()const;/存取队首元素值存取队首元素值bool isEmpty()const return count=0;/检测队列检测队列是否为空是否为空bool isFull()const return count=Size;/检测队检测队列是否为满列是否为满void QClear()front=rear=count=0;/清空队列清空队列；插入算法插入算法ADL描述描述算法算法QInsert(A,item)/在队列在队列A中将元素中将元

9、素item插入队尾插入队尾QI1.队列满？队列满？IF count size THEN(PRINT“队列已满无法插入队列已满无法插入”.RETURN.)QI2.元素插入元素插入 Arear item./将新元素插入队尾将新元素插入队尾QI3.更新更新 rearMOD(rear 1,size)./更新队尾下标更新队尾下标 countcount 1./更新队列长度更新队列长度 C+实现实现template void AQueue:QInsert(const T&item)QArrayrear=item;rear=(rear+1)%Size;删除算法删除算法ADL描述描述算法算法QDelete(A.

10、item)/删除队列删除队列A的队首元素，并将其元素值赋给变量的队首元素，并将其元素值赋给变量itemQD1.队列空？队列空？IF count 0 THEN(PRINT“队列空无法删除队列空无法删除”.RETURN.)QD2.出队出队 item Afront./将队首元素保存至将队首元素保存至itemQD3.更新更新 frontMOD(front 1,size)./更新队首元素下标更新队首元素下标 countcount-1./更新队列长度更新队列长度 C+实现实现template void AQueue:QDelete(T&item)item=QArrayfront;front=(front+

11、1)%Size;取队首算法取队首算法ADL描述描述算法算法QFront(A.item)/读取队列读取队列A的队首元素值，并将其赋给变量的队首元素值，并将其赋给变量itemQF1.队列空？队列空？IF count 0 THEN(PRINT“队列空无法读取队列空无法读取”.RETURN.)QF2.存取存取 item Afront./将队首元素保存至将队首元素保存至item C+实现实现template T AQueue:QFront()constreturn QArrayfront;验证：验证：#include aqueue.hint main()int n,i,x;AQueue s(100);c

12、inn;for(i=1;i=n;i+)s.QInsert(i);for(i=1;i=n;i+)s.QDelete(x);coutxendl;0123456a0123456FR(a)创建一个队列创建一个队列FR(b)插入元素插入元素 a队列运行示意图abc01234560123456FR(c)插入元素插入元素b、cFR(d)取出元素取出元素 a、b、chidefg0123456hijdefg0123456RF(e)插入元素插入元素d、e、f、g、h、iFR(f)插入元素插入元素 j3.队列的链接存储队列的链接存储template class NodeT data;Node*next;ana1a2

13、frontrear链队链队LQueue的类定义的类定义template class LQueue private:Node *front,*rear;/指向队首和队尾的指针public:LQueue(void)front=rear=NULL;/构造函数 LQueue(void)QClear();/析构函数void QInsert(const T&item);/向队尾插入元素向队尾插入元素itemvoid QDelete(T&item);/删除队首元素并将该元素值保存至删除队首元素并将该元素值保存至itemT QFront()const;/存取队首元素值存取队首元素值bool isEmpty()

14、const return front=0;/检测队列检测队列是否为空是否为空void QClear();/清空队列清空队列；插入算法插入算法ADL描述描述算法算法QInsert(item)/将元素将元素item插入队尾插入队尾QI1.创建新结点创建新结点 s AVAIL.data(s)item.next(s)NULL./为新结为新结点申请空间，令其字段值为点申请空间，令其字段值为item，指针域为空，指针域为空QI2.队空？队空？IF front NULL THEN fronts./若队列为空，令队首若队列为空，令队首指针指向指针指向s ELSE next(rear)s./若队列非空，令表尾结

15、点的若队列非空，令表尾结点的next指针指向指针指向sQI3.更新队尾指针更新队尾指针 rears./更新表尾指针更新表尾指针C+实现实现void LQueue:QInsert(const T&item)Node*p=new Node;p.data=item;p.next=0;if(rear)rear-next=p;rear=p;else front=rear=p;删除算法删除算法ADL描述描述算法算法QDelete(item)/删除队首结点并将其字段值存于删除队首结点并将其字段值存于itemQD1.队列空？队列空？IF front NULL THEN(PRINT“队列为空队列为空”.RETU

16、RN.)QD2.出队出队 qfront.itemdata(q)./令指针令指针q指向队首，并保存其指向队首，并保存其字段值字段值 frontnext(front)./令队首指针指向原队首结点之后继令队首指针指向原队首结点之后继结点结点 AVAILq./释放原队首结点的存储空间释放原队首结点的存储空间QD3.出队后队列空？出队后队列空？IF front NULL THEN rearNULL./若删除队首结点后队列为空，则令队尾指针修为空若删除队首结点后队列为空，则令队尾指针修为空C+实现实现template void LQueue:QDelete(T&item)Node*p;if(front)i

17、tem=front-data;p=front;front=front-next;delete p;if(front=0)rear=0;取队首算法取队首算法ADL描述描述算法算法QFront(item)/读取队首元素值，并将其赋给变量读取队首元素值，并将其赋给变量itemQF1.队列空？队列空？IF front NULL THEN(PRINT“队列空无法读取队列空无法读取”.RETURN.)QF2.存取存取 item data(front)./将队首元素保存至将队首元素保存至itemC+实现实现template T LQueue:QFront()const if(front)return fro

18、nt-data;验证：验证：#include“lqueue.hint 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;顺序队列与链式队列的比较顺序队列与链式队列的比较p在空间复杂性上，在空间复杂性上，顺序队列必须初始就申请固定顺序队列必须初始就申请固定的空间，当队列不满时，必然造成空间的浪费；的空间，当队列不满时，必然造成空间的浪费；链式队列所需空间是根据需要随时申请的，其代链式队列所需空间是根据需要随时申请的，其代价是为每个元素提供空间以存储其价是为

19、每个元素提供空间以存储其next指针域。指针域。p在时间复杂性上，在时间复杂性上，对于队列的基本操作（入队、对于队列的基本操作（入队、出队和存取），顺序队列和链式队列的时间复杂出队和存取），顺序队列和链式队列的时间复杂性均为性均为O(1).STL中关于栈的实现中关于栈的实现p#include pqueue s;/不用声明大小不用声明大小ps.push(x);ps.front();/取队首取队首ps.pop();/只弹出队首，与只弹出队首，与front合用合用课后练习课后练习ppoj.org 注册注册p数据较大时，使用数据较大时，使用scanf和和printfppoj1363 railsppoj3250 Bad Hair Day