Question? Leave a message!




Abstract Queue

Abstract Queue
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
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 © 2006-2013 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 first-in–first-out (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 client-server 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 Linked-List 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 Single_list Definition 3.3.3.1 The definition of single list class from Project 1 is: template typename Type class Single_list public: int size() const; bool empty() const; Type front() const; Type back() const; Single_nodeType head() const; Single_nodeType tail() const; int count( Type const & ) const; void push_front( Type const & ); void push_back( Type const & ); Type pop_front(); int erase( Type const & ); ;Queues 12 Queue-as-List 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: Single_listType list; public: bool empty() const; Type front() const; void push( Type const & ); Type pop(); ;Queues 13 Queue-as-List Class 3.3.3.1 The implementation is similar to that of a Stack-as-List 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.push_back( obj ); template typename Type Type QueueType::pop() if ( empty() ) throw underflow(); return list.pop_front(); Queues 14 Array Implementation 3.3.3.2 A one-ended 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 two-ended 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 queue_size; int ifront; // index of the front entry int iback; // index of the back entry – The capacity of the array int array_capacity;Queues 17 Queue-as-Array Class 3.3.3.2 The class definition is similar to that of the Stack: template typename Type class Queue private: int queue_size; int ifront; int iback; int array_capacity; 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 most-recently 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 Typearray_capacity makes a request to the operating system for array_capacity objects include algorithm // ... template typename Type QueueType::Queue( int n ): queue_size( 0 ), iback( -1 ), ifront( 0 ), array_capacity( std::max(1, n) ), array( new Typearray_capacity ) // 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 queue_size; template typename Type int iback; QueueType::Queue( int n ): int ifront; queue_size( 0 ), int array_capacity; Type array; iback( -1 ), public: ifront( 0 ), Queue( int = 10 ); array_capacity( std::max(1, n) ), Queue(); array( new Typearray_capacity ) bool empty() const; Type top() const; void push( Type const & ); // Empty constructor Type pop(); ;