数据结构英文课件：ch03 Queues

《数据结构英文课件：ch03 Queues》由会员分享，可在线阅读，更多相关《数据结构英文课件：ch03 Queues（74页珍藏版）》请在金锄头文库上搜索。

1、Chapter 3 QueuesA queue is a data structure modeled after a line of people waiting to be served. Along with stacks, queues are one of the simplest kinds of data structures. This chapter develops properties of queues, studies how they are applied, and examines different implementations. The implement

2、ations illustrate the use of derived classes in C+ and the important object-oriented technique of class inheritance.队列是一个模拟日常生活中人们排队等候服务的数据结构。与栈一样，队列是最简单的数据结构。本章描述了队列的性质、应用及不同的实现方法。描述了C+中派生类的使用和类的继承中重要的面向对象技术。Content PointsqDefinitions qImplementations of QueuesqCircular Implementation of Queues in

3、C+q Demonstration and TestingqApplication of Queues:Simulation DefinitionsqQueue ：we similarly define a queue to be a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end. q Queues are also called first-in, first-out lists, or FIFO（先进

4、先出（先进先出表）表） for short.Applications: a computer system ,queues of tasks waiting for printer,disk storage,with multitasking，use of the CPU.Front: the first entry in the queuerear: the last entry in the queue23411122front (head)rear (tail)Queue Operations（队列的基本操作）（队列的基本操作）qAs in our treatment of stacks

5、, we shall implement queues whose entries have a generic type, which we call Queue_entry.Queue : Queue( );postcondition: The Queue has been created and is initialized to be empty.Error_code Queue : append(const Queue_entry &x);postcondition: If there is space, x is added to the Queue as its rear. Ot

6、herwise an Error_code of overflow is returned.Error_code Queue : serve( );postcondition: If the Queue is not empty, the front of the Queue has been removed.Otherwise an Error_code of underflow is returned.Queue Operations（队列的基本操作）（队列的基本操作）Error_code Queue : retrieve(Queue_entry &x) const;postconditi

7、on: If the Queue is not empty, the front of the Queue has been recorded as x. Otherwise an Error_code of underflow is returned. （取队头元素）（取队头元素）bool Queue : empty( ) const;postcondition: Return true if the Queue is empty, otherwise return false.Queue Operations（队列的基本操作）（队列的基本操作）class Queue public:Queu

8、e( );bool empty( ) const;Error_code append(const Queue_entry &x);Error_code serve( );Error_code retrieve(Queue_entry &x) const;/ Additional members will represent queue data.;Queue Operations（队列的基本操作）（队列的基本操作）Remove front or underflowRecord front as xor underflowpushpopfrontAdd x to rear or overflow

9、Extended Queue OperationsExtended Queue Operations:full clear size serve_and_retrieveclass Queuemethods: Queue (constructor) append serve retrieve emptydata membersclass Queueclass Extended_Queuemethods: Extended_queue (constructor) append serve retrieve empty full clear size serve_and_retrievedata

10、membersadditional data membersinheritanceBase classDerived classExtended Queue Operationsclass Extended_queue: public Queue public:bool full( ) const;int size( ) const;void clear( );Error_code serve_and_retrieve(Queue_entry &item);Extended Queue Operationsq The new operations for our class Extended_

11、queue have the following specifications.bool Extended_queue : full( ) const;postcondition: Return true if the Extended_queue is full; return false otherwise.void Extended_queue : clear( );postcondition: All entries in the Extended_queue have been removed; it is now empty.Extended Queue Operationsint

12、 Extended_queue : size( ) const;postcondition: Return the number of entries in the Extended_queue.Error_code Extended_queue : serve_and_retrieve(Queue_entry &item);postcondition: Return underflow if the Extended_queue is empty. Otherwise remove and copy the item at the front of the Extended_queue to

13、 item and return success.Extended Queue OperationsEvery A “is a” Bclass A is derived from class BEvery A “has a” Bclass A has a data member of type Bq The relationship between the class Extended_queue and the class Queue is often called an is-a relationship. q This is because every Extended_queue ob

14、ject “is a” Queue object with other featuresnamely, the methods serve_and_retrieve, full,size, and clear.Cconsider C+ classes that might be used in a program to manage a university budget. Some of these classes are University, Student, University_president, and Person. Every student is a person, and

15、 therefore we might create the class Student as derived from the class Person to reflect the is-a relationship between the corresponding concepts. The class University_president could also be implemented as a derived class of Person to reflect another obvious is-a relationship. The classes Universit

16、y and University_president do not reflect an is-a relationship, however the classes are related, because every university does have a president. We shall say that these classes reflect a has-a relationship, and in an implementation we would make this relationship clear by layering the classes, that

17、is, by including a data member of type University_president in the definition of the class University.Outline nQueueConceptPropertyBasic operationsClass queueClass extended_queueIMPLEMENTATIONS OF QUEUESnContiguous implementation1.The physical model implementation2. Linear implementation3. Circular

18、array implementationnLinked implementation(We will discuss in the next chapter)Contiguous implementationnThe basic way is the same. We create a queue in memory by setting up an array to hold the entries. To facilitate the operations, we must keep track of the front and the rear of the queue.(基本方法是相同

19、的，我们使用一个数组来存放队列中的元素，为了方便操作，我们还保存了队列中的队头和队尾位置。)q1.The Physical Model（物理模型）（物理模型） The strategy（策略）（策略）is to keep the front of the queue always in the first location of the array. Contiguous implementation423111front2344rearrearTo remove an entry from the queue, however, would be very expensive indeed.

20、 (出队时，队列中所有元素都向前移动一个位置)Not a practical way An entry can be appended to the queue simply by increasing the rear by one and putting the entry in that location. (入队时元素添加到最后，队尾指示器增1)q 2. Linear Implementation（队列的顺序实现）（队列的顺序实现） To append an entry to the queue, we simply increase the rear by one and put t

21、he entry in that position. To serve an entry, we take it from the position at the front and then increase the front by one. Job 1Job 2Job 3Job 4Job 5Job 6 1012345 append Job 1 append Job 2 append Job 3 serve Job 1 append Job 4 append Job 5 append Job 6 serve Job 2 append Job 7 nProblem: not true ove

22、rflow (假溢出）happensnfault: discarded spaceThis method has a major defect（缺点）（缺点）: Both the front and rear indices are increased but never decreased. As the queue moves down the array, the storage space at the beginning of the array is discarded（丢弃）（丢弃） and never used again.Advantage: for applications

23、 where the queue is regularly emptied, then at a time when the queue is empty, the front and rear can both be reset to the beginning of the array, and the simple scheme of using two indices and straight-line storage becomes a very efficient implementation.inefficient use of spaceA limited wayq 3.Cir

24、cular Array（循环队列）（循环队列）qIn concept, we can overcome the inefficient use of space simply by thinking of the array as a circle rather than a straight line. (可以克服假溢出的问题),now we need not worry about running out of space unless the array is fully occupied,in which case we truly have overflow.(除非数组空间真正耗尽真

25、溢出，否则不需担心假溢出。)Job 1Job 2Job 3Job 4Job 5Job 6 1012345Job 7 append Job 7 5 4 3 2 1 0 Job3Job4Job5Job6Job7q Implementation of Circular Arrays（循环队列的实现）（循环队列的实现）An array hold all the entries and the first location is supposed the next of the last ;一个被认为是首尾相连的数组front and rear ;front和rear分别指示着队头和队尾元素的位置How

26、 to append an entry to the queue?How to serve an entry from the queue?How to init the front and rear?Job 1Job 2Job 3 1012 append Job 2 append Job 3front=0rear=0rear=2345nHow to append an entrynWhen an entry is appended to the queue, rear+;队尾指示器rear增1，front没有变化rear=1Job 1Job 2Job 3Job 4Job 5Job 6 101

27、2345 append Job 7Job 7front=2rear=5rear=0nHow to append an entryUsually when an entry is appended to the queue, rear+;But when the rear is the last position:maxqueue-1; rear=0;rear = (rear + 1) =maxqueue) ? 0 : (rear + 1);or rear=(rear+1)%maxqueue;nHow to sever an entrynBut when the front is the las

28、t position:maxqueue-1; front=0;nfront = (front + 1) =maxqueue) ? 0 : (front + 1);nor front=(front+1)%maxqueue; serve Job 3 serve Job 4 serve Job 5 serve Job 6Job 1Job 2Job 3Job 4Job 5Job 6Job 7front=2rear=0front=3 1012345front=4front=5front=0Usually when an entry is served from the queue, front+;Att

29、entionWhen an entry is appended to the queue, we must judge if the queue is full. (overflow) 入队需判别队满；When an entry is severed from the queue we must judge if the queue is empty. (underflow)出队需判别队空。Job 1 1012front=0rear=0345nHow to init the front and the rear for an empty queue?nfront=0;rear=-1; ornf

30、ront=0;rear=maxqueue-1;n经过一次入队后，可以得到这个状态。Job 1012front=0rear=0345 sever Job 1front=0 5 4 3 2 1 0 rear=0Job 1front=1 append Job 2队空时，rear和front相差1个位置。在这个例子中，front=1，rear=0；Job 2rear=1 append Job 3，4，5，6Job 3Job 4Job 5Job 6rear=5 append Job 7rear=0Job 7队满时，rear和front也相差1个位置。在这个例子中，front=1，rear=0；Empty

31、 and Full Boundary Conditions存在问题存在问题: 如何区别如何区别队空队空和和队满队满!IMPLEMENTATIONS OF QUEUESqPossible Solutions（解决方法）（解决方法）empty position（少用一个空间）（少用一个空间） One is to insist on leaving one empty position in the array, so that the queue is considered full when the rear index has moved within two positions of the

32、 front. a new variable （引入一个变量）（引入一个变量） A second method is to introduce a new variable. This can be a Boolean flag that is set as true when the rear comes just before the front to indicate that the queue is full or an integer variable that counts the number of entries in the queue. special values（采用

33、特殊值）（采用特殊值） The third method is to set one or both of the indices to some value(s) that would otherwise never occur in order to indicate an empty (or full) queue. For example, an empty queue could be indicated by setting the rear index to -1.IMPLEMENTATIONS OF QUEUESq Summary of ImplementationsTo su

34、mmarize the discussion of queues, let us list all the methods we have discussed for implementing queues. The physical model: a linear array with the front always in the first position and all entries moved up the array whenever the front is removed. This is generally a poor method for use in compute

35、rs. A linear array with two indices always increasing. This is a good method if the queue can be emptied all at once. A circular array with front and rear indices and one position left vacant.IMPLEMENTATIONS OF QUEUESq Summary of Implementations A circular array with front and rear indices and a fla

36、g to indicate fullness (or emptiness). A circular array with front and rear indices and an integer variable counting entries. A circular array with front and rear indices taking special values to indicate emptiness.CIRCULAR IMPLEMENTATION OF QUEUES IN C+（循环队列实现）（循环队列实现）q The implementation in a circ

37、ular array which uses a counter to keep track of the number of entries in the queue both illustrates techniques for handling circular arrays and simplifies the programming of some of the extended-queue operations.q We shall take the queue as stored in an array indexed with the range 0 to (maxqueue -

38、 1)CIRCULAR IMPLEMENTATION OF QUEUES IN C+const int maxqueue = 10; / small value for testingclass Queue public:Queue( );bool empty( ) const;Error_code serve( );Error_code append(const Queue_entry &item);Error_code retrieve(Queue_entry &item) const;protected:int count;int front, rear;Queue_entry entr

39、ymaxqueue;CIRCULAR IMPLEMENTATION OF QUEUES IN C+Queue : Queue( )/* Post: The Queue is initialized to be empty. */count = 0;rear = maxqueue - 1;front = 0;bool Queue : empty( ) const/* Post: Return true if the Queue is empty, otherwise return false. */return count = 0;CIRCULAR IMPLEMENTATION OF QUEUE

40、S IN C+Error_code Queue : append(const Queue_entry &item)/* Post: item is added to the rear of the Queue. If the Queue is full return an Error_code of overflow and leave the Queue unchanged. */if (count = maxqueue) return overflow;count+;rear = (rear + 1) = maxqueue) ? 0 : (rear + 1);entryrear = ite

41、m;return success;CIRCULAR IMPLEMENTATION OF QUEUES IN C+.Error_code Queue : serve( )/* Post: The front of the Queue is removed. If the Queue is empty return an Error_code of underflow. */if (count = 0) return underflow;count-;front = (front + 1) = maxqueue) ? 0 : (front + 1);return success;CIRCULAR

42、IMPLEMENTATION OF QUEUES IN C+Error_code Queue : 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 = maxqueue) return overflow;count+;rear = (rear + 1) = maxqueue) ? 0 : (rear

43、+ 1);entryrear = item;return success;CIRCULAR IMPLEMENTATION OF QUEUES IN C+.Error_code Queue : serve( )/* Post: The front of the Queue is removed. If the Queue is empty return an Error_code of underflow. */if (count = 0) return underflow;count-;front = (front + 1) = maxqueue) ? 0 : (front + 1);retu

44、rn success;CIRCULAR IMPLEMENTATION OF QUEUES IN C+Error_code Queue : 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;in

45、t Extended_queue : size( ) const/* Post: Return the number of entries in the Extended_queue. */return count;DEMONSTRATION AND TESTINGq Menu-driven demonstration programint main( )/* Post: Accepts commands from user as a menu-driven demonstration program for the class Extended_queue.Uses: The class E

46、xtended_queue and the functions introduction, get_command,and do_command. */Extended_queue test_queue;introduction( );while (do_command(get_command( ), test_queue);DEMONSTRATION AND TESTINGq Menu-driven demonstration programDEMONSTRATION AND TESTINGq Menu-driven demonstration programDEMONSTRATION AN

47、D TESTINGvoid help( )/* Post: A help screen for the program is printed, giving the meaning of each command that the user may enter. */cout endl This program allows the user to enter one command endl (but only one) on each input line. endl For example, if the command S is entered, then endl the progr

48、am will serve the front of the queue. endl endl The valid commands are: endl A - Append the next input character to the extended queue endlDEMONSTRATION AND TESTING S - Serve the front of the extended queue endl R - Retrieve and print the front entry. endl # - The current size of the extended queue

49、endl C - Clear the extended queue (same as delete) endl P - Print the extended queue endl H - This help screen endl Q - Quit endl Press to continue. flush;char c;do cin.get(c); while (c != n);DEMONSTRATION AND TESTINGbool do_command(char c, Extended_queue &test_queue)/* Pre: c represents a valid com

50、mand.Post: Performs the given command c on the Extended_queue test_queue. Returns false if c = q, otherwise returns true.Uses: The class Extended_queue. */bool continue_input = true;Queue_entry x;DEMONSTRATION AND TESTINGswitch (c) case r:if (test_queue.retrieve(x) = underflow)cout Queue is empty. e

51、ndl;elsecout endl The first entry is: x endl;break;case q:cout Extended queue demonstration finished. endl;continue_input = false;break;/ Additional cases will cover other commands.return continue_input;1、A circular queue has the problem in which it is not easy to distinguish between full and empty

52、queues. Draw two situations to illustrate this point. The front and rear pointers should be in the same position in each situation. 2、Evaluate the following sentence if it is true or false and simply explain why?A queue is a FILO data structure. An array based queue implementation is usually impleme

53、nted as a circular queue. An array based queue is better than a linked list implementation of a queue. APPLICATION OF QUEUES: SIMULATIONq Introduction Simulation is the use of one system to imitate the behavior of another system.Simulations are often used when it would be too expensive or dangerous

54、to experiment with the real system.仿真是指用一个系统模拟另一个系统的行为。经常使用于实际系统比较昂贵或危险的情形。Such as :wind tunnel 、flight simulatorscomputer simulation: uses the steps of a program to imitate the behavior of the system under study.In a computer simulation, the objects being studied are usually represented as data, of

55、ten as data structures given by classes whose members describe the properties of the objects.Actions being studied are represented as methods of the classes.And the rules describing these actions are translated into computer algorithms. By changing the values of the data or by modifying these algori

56、thms,we can observe the changes in the computer simulation, and then we can draw worthwhile inferences concerning the behavior of the actual system.(可以得到关于实际系统的有价值的结论)APPLICATION OF QUEUES: SIMULATIONHome work nP84 Exercise 3.1 E2 E3(b)(e)nP91 Exercise 3.1 E5 E6 E7n栈是一种特殊的线性表，允许插入和删除运算的一端称为 。对于顺序存储的

57、栈，因为栈的空间是有限的，在进行 运算时，可能发生栈的上溢（overflow）。n若一个栈的输入序列是1,2,3,n，输出序列的第一个元素是n，则输出序列的第i个元素是 。n一个中缀表达式为a+(3-x)*y，则其对应的后缀表达式为 。Write a function that will reverse the order of all the entries in a Queue .You can use the methods for queues and stacks developed in the textbook . In writing the function, be sure

58、 to check for empty and full structures as appropriate.POINTERS AND PITFALLS Before choosing implementations, be sure that all the data structures and their associated operations are fully specified on the abstract level. In choosing between implementations, consider the necessary operations on the

59、data structure. If every object of class A has all the properties of an object of class B, implement class A as a derived class of B. Consider the requirements of derived classes when declaring the members of a base class. Implement is-a relationships between classes by using public inheritance. Implement has-a relationships between classes by layering. Use Poisson random variables to model random event occurrences.