《数据结构与程序设计 第三章队列(Queue)》由会员分享，可在线阅读，更多相关《数据结构与程序设计 第三章队列(Queue)（46页珍藏版）》请在金锄头文库上搜索。
1、7/30/2024数据结构与程序设计1第三章 队列(Queue)nAll additions to the list are made at one end, called the rear or tail of the queue(队尾队尾), and all deletions from the list are made at the other end, called the front or head of the queue（队首）（队首）.nWith the property called first in, first out, or FIFOnSuch as a line o
2、f people waiting to purchase tickets.7/30/2024数据结构与程序设计2队列Queuen队列中的元素只能从队尾插入（称为入队操作），队列中的元素只能从队尾插入（称为入队操作），从队首删除（称为出队操作）。入队和出队操作可从队首删除（称为出队操作）。入队和出队操作可以按任意的次序连续或交替进行，但队列空时不能以按任意的次序连续或交替进行，但队列空时不能出队，队列满时不能入队。出队，队列满时不能入队。7/30/2024数据结构与程序设计3The Abstract Data Type QueuenADT queue operationsnCreate an e
3、mpty queue 创建队列创建队列nDetermine whether a queue is empty 判断队列是否为空判断队列是否为空nAdd a new item to the queue 入队入队nRemove the item that was added earliest 出队出队nRetrieve the item that was added earliest 访问队首元素访问队首元素7/30/2024数据结构与程序设计4The Abstract Data Type Queue关于队列的操作关于队列的操作n创建队列创建队列n入队入队Queue : Queue( );Post
4、: The Queue has been created and is initialized to be empty.Error code Queue : append(const Queue entry &x);Post: If there is space, x is added to the Queue as its rear. Otherwise an Error code of overflow is returned.7/30/2024数据结构与程序设计5The Abstract Data Type Queue关于队列的操作关于队列的操作n出队出队n访问队首的元素访问队首的元素E
5、rror code Queue : serve( );Post: If the Queue is not empty, the front of the Queue has been removed. Otherwise an Error code of underflow is returned.Error code Queue : retrieve(Queue entry &x) const;Post: If the Queue is not empty, the front of the Queue has been recorded as x. Otherwise an Error c
6、ode of underflow is returned.7/30/2024数据结构与程序设计6The Abstract Data Type Queue关于队列的操作关于队列的操作n判断队列是否为空判断队列是否为空bool Queue : empty( ) const;Post: Return true if the Queue is empty, otherwise return false.7/30/2024数据结构与程序设计7The Abstract Data Type Queue 队列的定义队列的定义const int maxqueue = 10; / small value for
7、testingclass Queue 成员函数成员函数:Queue( );bool empty( ) const;Error code serve( );Error code append(const Queue entry &item);Error code retrieve(Queue entry &item) const;成员数据成员数据:int count;int front, rear;Queue entry entrymaxqueue;7/30/2024数据结构与程序设计8思考：客户端如何使用Queue中的功能nq是是Queue类型的对象，是一个用于保存字符数据类型的对象，是一个用
8、于保存字符数据的队列。的队列。nchar c1 = A , c2 = R, c3;n/变量变量c1，c2入队的操作分别为：入队的操作分别为：nq.append(c1); q.append(c2);/队列为队列为A，Rn将队首的内容放入将队首的内容放入c3的操作为：的操作为：nq.retrieve(c3) /操作成功后，变量操作成功后，变量c3的内容为的内容为A； /队列为队列为A，Rn出队的操作为：出队的操作为：nq.serve();/此时队列中剩下一个字符此时队列中剩下一个字符R7/30/2024数据结构与程序设计9怎么在计算机中实现ADT Queue n顺序队列顺序队列n链接队列链接队列7
9、/30/2024数据结构与程序设计10队列Queue为空Count = 0front = 0Rear = -1012345MAX-17/30/2024数据结构与程序设计11队列Queue中append一个元素Count = 1front = 0Rear = 00 *12345MAX-17/30/2024数据结构与程序设计12队列Queue中append N个元素Count = n front = 0Rear = N-10 *1 * *N-1 *N5MAX-17/30/2024数据结构与程序设计13队列Queue中Serve 1个元素Count = N-1 front = 1Rear = N-1
10、01 * *N-1 *N5MAX-17/30/2024数据结构与程序设计14队列Queue经过出队后只剩下3个元素时Count = 3 front = N-3Rear = N-101N-3 *N-2 *N-1* NMAX-17/30/2024数据结构与程序设计15队列Queue中Serve N个元素Count = 0 front = NRear = N-101N-3 N-2 N-1NMAX-1 此时队列为空。此时队列为空。7/30/2024数据结构与程序设计16通用队列MyQueue的实现enum Error_codeunderflow, overflow, success;const int
11、 maxqueue = 5; / small value for testingtemplateclass MyQueue public: MyQueue(); bool empty() const; Error_code serve(); Error_code append(const Queue_entry &item); Error_code retrieve(Queue_entry &item) const; bool full() const; int size() const; void clear(); Error_code serve_and_retrieve(Queue_en
12、try &item);private: int count; int front, rear; Queue_entry entrymaxqueue;7/30/2024数据结构与程序设计17通用队列MyQueue的实现templateMyQueue:MyQueue()/*Post: The Queue is initialized to be empty.*/ count = 0; rear = -1; front = 0;7/30/2024数据结构与程序设计18通用队列MyQueue的实现templatebool MyQueue:empty() const/*Post: Return true
13、 if the Queue is empty, otherwise return false.*/ return count = 0;7/30/2024数据结构与程序设计19通用队列MyQueue的实现templateError_code MyQueue:append(const Queue_entry &item)/*Post: item is added to the rear of the Queue. If the Queue is fullreturn an Error_code of overflow and leave the Queue unchanged.*/队尾下标已经到达
14、数组的末尾。则溢出队尾下标已经到达数组的末尾。则溢出 if (rear = maxqueue-1) return overflow; count+; rear+; /队尾下标往后移队尾下标往后移 entryrear = item; /新的元素入队新的元素入队 return success;7/30/2024数据结构与程序设计20通用队列MyQueue的实现templateError_code MyQueue:serve()/*Post: The front of the Queue is removed. If the Queueis empty return an Error_code of
15、 underflow.*/ if (count = 0) return underflow; count-; front+;/ 队首下标直接往后移队首下标直接往后移 return success;7/30/2024数据结构与程序设计21通用队列MyQueue的实现templateError_code MyQueue :retrieve(Queue_entry &item) const/*Post: The front of the Queue retrieved to the output parameter item. If the Queue is empty return an Erro
16、r_code of underflow.*/ if (count = 0) return underflow; item = entryfront; /读取队首下标位置的值读取队首下标位置的值 return success;7/30/2024数据结构与程序设计22通用队列MyQueue的实现templateint MyQueue:size() const/*Post: Return the number of entries in the Queue.*/ return count;7/30/2024数据结构与程序设计23通用队列MyQueue的实现templatebool MyQueue:f
17、ull() const/*Post: Return true if the Queue is full, otherwise return false.*/ return(rear=maxqueue-1);7/30/2024数据结构与程序设计24通用队列MyQueue的实现templatevoid MyQueue:clear()/*Post: Return an empty Queue.*/ count = 0; rear = -1 ; front = 0;7/30/2024数据结构与程序设计25通用队列MyQueue的实现templateError_code MyQueue:serve_an
18、d_retrieve(Queue_entry &item)/*Post: The front of the Queue retrieved to the output parameter item. And also the front of the Queue is removed. If the Queue is empty return an Error_code of underflow.*/ if (count = 0) return underflow; item = entryfront; count-; front+; return success;7/30/2024数据结构与
19、程序设计26List in original order#include MyQueue.cpp /Attention especially for templatevoid main() int n; double item; MyQueue numbers; / declares and initializes a stack of double numbers cout Type in an integer n followed by n decimal numbers. endl The numbers will be printed in original order. n; for
20、 (int i = 0; i item; numbers.append(item); cout endl endl; while (!numbers.empty() numbers.serve_and_retrieve(item); cout item ; cout endl;7/30/2024数据结构与程序设计27上机作业n使用类模版完成通用队列MyQueue7/30/2024数据结构与程序设计28List in original ordern目录MyQueue下例程n问题：问题：nAs the queue moves down the array， the storage space at
21、 the beginning of the array is discarded and never used again.n队列为空，可能数组已经越界了。队列为空，可能数组已经越界了。Count = 0 front = NRear = N-101N-3 N-2 N-1NMAX-17/30/2024数据结构与程序设计29解决方案讨论n解决方案解决方案1： nAfter the first entry was served, all the remaining entries would need to be moved one position up the queue to fill in
22、the vacancy. With a long queue, this process would be slow.n解决方案解决方案2： 引入环行队列。引入环行队列。nP86 Figure 3.37/30/2024数据结构与程序设计30环行队列CirQueue为空7/30/2024数据结构与程序设计31环行队列CirQueue append one item7/30/2024数据结构与程序设计32环行队列CirQueue append MAXN items注意：通过count来区别队列空、满front = 0Rear = maxn-1此时此时font和和rear的值与队列为的值与队列为空时
23、的情况相同。无法区分空时的情况相同。无法区分7/30/2024数据结构与程序设计33环行队列CirQueue serve one item，剩下MAX-1个元素7/30/2024数据结构与程序设计34环行队列CirQueue的实现enum Error_codeunderflow, overflow, success;const int maxqueue = 10; / small value for testingtemplateclass CirQueue public: CirQueue(); bool empty() const; Error_code serve(); Error_co
24、de append(const Queue_entry &item); Error_code retrieve(Queue_entry &item) const; bool full() const; int size() const; void clear(); Error_code serve_and_retrieve(Queue_entry &item);private: int count; int front, rear; Queue_entry entrymaxqueue;7/30/2024数据结构与程序设计35环行队列CirQueue的实现templateCirQueue:Cir
25、Queue()/*Post: The Queue is initialized to be empty.*/ count = 0; rear = maxqueue - 1; front = 0;7/30/2024数据结构与程序设计36环行队列CirQueue的实现templatebool CirQueue:empty() const/*Post: Return true if the Queue is empty, otherwise return false.*/ return count = 0;7/30/2024数据结构与程序设计37环行队列CirQueue的实现templateErro
26、r_code CirQueue:append(const Queue_entry &item)/*Post: item is added to the rear of the Queue. If the Queue is fullreturn an Error_code of overflow and leave the Queue unchanged.*/ if (count = maxqueue) return overflow; count+; rear = (rear + 1) = maxqueue) ? 0 : (rear + 1); /处理队尾的下标处理队尾的下标 entryrea
27、r = item; return success;7/30/2024数据结构与程序设计38环行队列CirQueue的实现templateError_code CirQueue:serve()/*Post: The front of the Queue is removed. If the Queueis empty return an Error_code of underflow.*/ if (count = 0) return underflow; count-; front = (front + 1) = maxqueue) ? 0 : (front + 1); return succe
28、ss;7/30/2024数据结构与程序设计39环行队列CirQueue的实现templateError_code CirQueue:retrieve(Queue_entry &item) const/*Post: The front of the Queue retrieved to the output parameter item. If the Queue is empty return an Error_code of underflow.*/ if (count = 0) return underflow; item = entryfront; return success;7/30
29、/2024数据结构与程序设计40环行队列CirQueue的实现templateint CirQueue:size() const/*Post: Return the number of entries in the Queue.*/ return count;7/30/2024数据结构与程序设计41环行队列CirQueue的实现templatebool CirQueue:full() const/*Post: Return true if the Queue is full, otherwise return false.*/ return(count=maxqueue);7/30/2024数
30、据结构与程序设计42环行队列CirQueue的实现templatevoid CirQueue:clear()/*Post: Return an empty Queue.*/ count = 0; rear = maxqueue-1; front = 0;7/30/2024数据结构与程序设计43环行队列CirQueue的实现templateError_code CirQueue:serve_and_retrieve(Queue_entry &item)/*Post: The front of the Queue retrieved to the output parameter item. An
31、d also the front of the Queue is removed. If the Queue is empty return an Error_code of underflow.*/ if (count = 0) return underflow; item = entryfront; count-; front = (front + 1) = maxqueue) ? 0 : (front + 1); return success;7/30/2024数据结构与程序设计44List in original ordern目录CirQueue下例程n解决了问题：nAs the queue moves down the array， the storage space at the beginning of the array is discarded and never used again.n队列为空，可能数组已经越界了。n充分利用了数组的空间。7/30/2024数据结构与程序设计45上机作业n使用类模版完成环行队列CirQueue7/30/2024数据结构与程序设计46课后作业n（1） P84 E1n（2） P91 E4
