Queue abstract data type

abstract data type in data structure ppt and queue abstract data type implementation
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
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(); ;