Question? Leave a message!




Abstract Queue

Abstract Queue
ECE 250 Algorithms and Data Structures Queues Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Queues 2 Outline This topic discusses the concept of a queue: – Description of an Abstract Queue – List applications – Implementation – Queuing theory – Standard Template LibraryQueues 3 Abstract Queue 3.3 An Abstract Queue (Queue ADT) is an abstract data type that emphasizes specific operations: – Uses a explicit linear ordering – Insertions and removals are performed individually – There are no restrictions on objects inserted into (pushed onto) the queue—that object is designated the back of the queue – The object designated as the front of the queue is the object which was in the queue the longest – The remove operation (popping from the queue) removes the current front of the queueQueues 4 Abstract Queue 3.3.1 Also called a firstin–firstout (FIFO) data structure – Graphically, we may view these operations as follows:Queues 5 Abstract Queue 3.3.1 Alternative terms may be used for the four operations on a queue, including:Queues 6 Abstract Queue 3.3.1 There are two exceptions associated with this abstract data structure: – It is an undefined operation to call either pop or front on an empty queueQueues 7 Applications 3.3.2 The most common application is in clientserver models – Multiple clients may be requesting services from one or more servers – Some clients may have to wait while the servers are busy – Those clients are placed in a queue and serviced in the order of arrival Grocery stores, banks, and airport security use queues The SSH Secure Shell and SFTP are clients Most shared computer services are servers: – Web, file, ftp, database, mail, printers, WOW, etc.Queues 8 Applications 3.3.2 For example, in downloading these presentations from the ECE 250 web server, those requests not currently being downloaded are marked as ―Queued‖Queues 9 Implementations 3.3.3 We will look at two implementations of queues: – Singly linked lists – Circular arrays Requirements: – All queue operations must run in Q(1) timeQueues 10 LinkedList Implementation 3.3.3.1 Removal is only possible at the front with Q(1) run time st th Front/1 Back/n Find Q(1)Q(1) Insert Q(1)Q(1) EraseQ(1)Q(n) The desired behaviour of an Abstract Queue may be reproduced by performing insertions at the backQueues 11 Singlelist Definition 3.3.3.1 The definition of single list class from Project 1 is: template typename Type class Singlelist public: int size() const; bool empty() const; Type front() const; Type back() const; SinglenodeType head() const; SinglenodeType tail() const; int count( Type const ) const; void pushfront( Type const ); void pushback( Type const ); Type popfront(); int erase( Type const ); ;Queues 12 QueueasList Class 3.3.3.1 The queue class using a singly linked list has a single private member variable: a singly linked list template typename Type class Queue private: SinglelistType list; public: bool empty() const; Type front() const; void push( Type const ); Type pop(); ;Queues 13 QueueasList Class 3.3.3.1 The implementation is similar to that of a StackasList template typename Type template typename Type bool QueueType::empty() const Type QueueType::front() const return list.empty(); if ( empty() ) throw underflow(); return list.front(); template typename Type void QueueType::push( Type const obj ) list.pushback( obj ); template typename Type Type QueueType::pop() if ( empty() ) throw underflow(); return list.popfront(); Queues 14 Array Implementation 3.3.3.2 A oneended array does not allow all operations to occur in Q(1) time st th Front/1 Back/n Find Q(1)Q(1) Insert Q(n)Q(1) Erase Q(n)Q(1)Queues 15 Array Implementation 3.3.3.2 Using a twoended array, Q(1) are possible by pushing at the back and popping from the front st th Front/1 Back/n Find Q(1)Q(1) Insert Q(1)Q(1) Remove Q(1)Q(1)Queues 16 Array Implementation 3.3.3.2 We need to store an array: – In C++, this is done by storing the address of the first entry Type array; We need additional information, including: – The number of objects currently in the queue and the front and back indices int queuesize; int ifront; // index of the front entry int iback; // index of the back entry – The capacity of the array int arraycapacity;Queues 17 QueueasArray Class 3.3.3.2 The class definition is similar to that of the Stack: template typename Type class Queue private: int queuesize; int ifront; int iback; int arraycapacity; Type array; public: Queue( int = 10 ); Queue(); bool empty() const; Type front() const; void push( Type const ); Type pop(); ;Queues 18 Constructor 3.3.3.2 Before we initialize the values, we will state that – iback is the index of the mostrecently pushed object – ifront is the index of the object at the front of the queue To push, we will increment iback and place the new item at that location – To make sense of this, we will initialize iback = 1; ifront = 0; – After the first push, we will increment iback to 0, place the pushed item at that location, and now Queues 19 Constructor 3.3.3.2 Again, we must initialize the values – We must allocate memory for the array and initialize the member variables – The call to new Typearraycapacity makes a request to the operating system for arraycapacity objects include algorithm // ... template typename Type QueueType::Queue( int n ): queuesize( 0 ), iback( 1 ), ifront( 0 ), arraycapacity( std::max(1, n) ), array( new Typearraycapacity ) // Empty constructor Queues 20 Constructor 3.3.3.2 Reminder: – Initialization is performed in the order specified in the class declaration template typename Type class Queue private: int queuesize; template typename Type int iback; QueueType::Queue( int n ): int ifront; queuesize( 0 ), int arraycapacity; Type array; iback( 1 ), public: ifront( 0 ), Queue( int = 10 ); arraycapacity( std::max(1, n) ), Queue(); array( new Typearraycapacity ) bool empty() const; Type top() const; void push( Type const ); // Empty constructor Type pop(); ;Queues 21 Destructor 3.3.3.2 The destructor is unchanged from StackasArray: template typename Type QueueType::Queue() delete array; Queues 22 Member Functions 3.3.3.2 These two functions are similar in behaviour: template typename Type bool QueueType::empty() const return ( queuesize == 0 ); template typename Type Type QueueType::front() const if ( empty() ) throw underflow(); return arrayifront; Queues 23 Member Functions 3.3.3.2 However, a naïve implementation of push and pop will cause difficulties: template typename Type void QueueType::push( Type const obj ) if ( queuesize == arraycapacity ) throw overflow(); template typename Type Type QueueType::pop() if ( empty() ) ++iback; throw underflow(); arrayiback = obj; ++queuesize; queuesize; ++ifront; return arrayifront 1; Queues 24 Member Functions 3.3.3.2 Suppose that: – The array capacity is 16 – We have performed 16 pushes – We have performed 5 pops • The queue size is now 11 – We perform one further push In this case, the array is not full and yet we cannot place any more objects in to the arrayQueues 25 Member Functions 3.3.3.2 Instead of viewing the array on the range 0, …, 15, consider the indices being cyclic: …, 15, 0, 1, …, 15, 0, 1, …, 15, 0, 1, … This is referred to as a circular arrayQueues 26 Member Functions 3.3.3.2 Now, the next push may be performed in the next available location of the circular array: ++iback; if ( iback == capacity() ) iback = 0; Queues 27 Exceptions 3.3.3.2 As with a stack, there are a number of options which can be used if the array is filled If the array is filled, we have five options: – Increase the size of the array – Throw an exception – Ignore the element being pushed – Put the pushing process to ―sleep‖ until something else pops the front of the queue Include a member function bool full()Queues 28 Increasing Capacity 3.3.4 Unfortunately, if we choose to increase the capacity, this becomes slightly more complex – A direct copy does not work:Queues 29 Increasing Capacity 3.3.4 There are two solutions: – Move those beyond the front to the end of the array – The next push would then occur in position 6Queues 30 Increasing Capacity 3.3.4 An alternate solution is normalization: – Map the front back at position 0 – The next push would then occur in position 16Queues 31 Application 3.3.5 Another application is performing a breadthfirst traversal of a directory tree – Consider searching the directory structureQueues 32 Application 3.3.5 We would rather search the more shallow directories first then plunge deep into searching one subdirectory and all of its contents One such search is called a breadthfirst traversal – Search all the directories at one level before descending a levelQueues 33 Application 3.3.5 The easiest implementation is: – Place the root directory into a queue – While the queue is not empty: • Pop the directory at the front of the queue • Push all of its subdirectories into the queue The order in which the directories come out of the queue will be in breadthfirst orderQueues 34 Application 3.3.5 Push the root directory AQueues 35 Application 3.3.5 Pop A and push its two subdirectories: B and HQueues 36 Application 3.3.5 Pop B and push C, D, and GQueues 37 Application 3.3.5 Pop H and push its one subdirectory IQueues 38 Application 3.3.5 Pop C: no subdirectoriesQueues 39 Application 3.3.5 Pop D and push E and FQueues 40 Application 3.3.5 Pop GQueues 41 Application 3.3.5 Pop I and push J and KQueues 42 Application 3.3.5 Pop EQueues 43 Application 3.3.5 Pop FQueues 44 Application 3.3.5 Pop JQueues 45 Application 3.3.5 Pop K and the queue is emptyQueues 46 Application 3.3.5 The resulting order A B H C D G I E F J K is in breadthfirst order:Queues 47 Standard Template Library 3.3.6 An example of a queue in the STL is: include iostream include queue using namespace std; int main() queue int iqueue; iqueue.push( 13 ); iqueue.push( 42 ); cout "Head: " iqueue.front() endl; iqueue.pop(); // no return value cout "Head: " iqueue.front() endl; cout "Size: " iqueue.size() endl; return 0; Queues 48 Summary The queue is one of the most common abstract data structures Understanding how a queue works is trivial The implementation is only slightly more difficult than that of a stack Applications include: – Queuing clients in a clientserver model – Breadthfirst traversals of treesQueues 49 References rd Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3 Ed., Addison Wesley, 1997, §2.2.1, p.238. Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, §11.1, p.200. rd Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §3.6, p.94. Koffman and Wolfgang, ―Objects, Abstraction, Data Strucutes and Design using C++‖, John Wiley Sons, Inc., Ch. 6. Wikipedia, http://en.wikipedia.org/wiki/Queue(abstractdatatype) These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017