数据结构英文课件：ch03 Queues

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

6、. Otherwise 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;pos

7、tcondition: 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 pub

8、lic:Queue( );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

9、rear or overflowExtended 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_a

10、nd_retrievedata 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

11、 our class Extended_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

12、 Queue Operationsint 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

13、of the Extended_queue to 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

14、 every Extended_queue object “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

15、student is a person, and 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 relationshi

16、p. The classes University 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 lay

17、ering the classes, that 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 im

18、plementation3. Circular 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 re

19、ar of the queue.(基本方法是相同的，我们使用一个数组来存放队列中的元素，为了方便操作，我们还保存了队列中的队头和队尾位置。)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 b

20、e very expensive indeed. (出队时，队列中所有元素都向前移动一个位置)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 t

21、he rear by one and put the 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

22、7 nProblem: not true overflow (假溢出）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.Adv

23、antage: for applications 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 s

24、paceA limited wayq 3.Circular 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 ha

25、ve overflow.(除非数组空间真正耗尽真溢出，否则不需担心假溢出。)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 ;fron

26、t和rear分别指示着队头和队尾元素的位置How 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 2

27、Job 3Job 4Job 5Job 6 1012345 append Job 7Job 7front=2rear=5rear=0nHow to append an entry Usually 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 entrynB

28、ut when the front is the last 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 serve

29、d from the queue, front+;AttentionWhen 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

30、queue?nfront=0;rear=-1; ornfront=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个位置

31、。在这个例子中，front=1，rear=0；Empty 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

32、 within two positions of the 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

33、the queue. special values（采用特殊值）（采用特殊值） 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 Sum

34、mary of ImplementationsTo summarize 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 po

35、or method for use in computers. 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 fron

36、t and rear indices and a flag 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

37、The implementation in a circular 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 wit

38、h the range 0 to (maxqueue - 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 co

39、unt;int front, rear;Queue_entry entrymaxqueue;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

40、= 0;CIRCULAR IMPLEMENTATION OF QUEUES 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) = ma

41、xqueue) ? 0 : (rear + 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) ?

42、0 : (front + 1);return 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 = maxqueue) return overflow;count

43、+;rear = (rear + 1) = maxqueue) ? 0 : (rear + 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 = (f

44、ront + 1) = maxqueue) ? 0 : (front + 1);return 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) retu

45、rn underflow;item = entryfront;return success;int 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 progra

46、m for the class Extended_queue.Uses: The class Extended_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 M

47、enu-driven demonstration programDEMONSTRATION AND 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,

48、if the command S is entered, then endl the program 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.

49、endl # - The current size of the extended queue 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_qu

50、eue &test_queue)/* Pre: c represents a valid command.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_

51、queue.retrieve(x) = underflow)cout Queue is empty. endl;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 i

52、t is not easy to distinguish between full and empty 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

53、 array based queue implementation is usually implemented 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 to experiment with the real system.仿真是指用一个系统模拟另一个系统的行为。经常使用于实际系统比较昂贵或危险的情形。Such as :wind tunnel 、flight simulatorscomputer simulatio