Data Structures and Agorithm: DS 09 Queue.pptx

Data Structures and Agorithm: DS 09 Queue.pptx

1. Data Structure Lecture No. 9 Queue Engr . Rashid Farid Chishti http://youtube.com/rfchishti http://sites.google.com/site/chishti International Islamic University H-10, Islamabad, Pakistan Video Lecture

2. A stack is LIFO (Last-In First Out) structure. In contrast, a queue is a FIFO (First-In First-Out ) structure. A queue is a linear structure for which items can be only inserted at one end and removed at another end . Queue Operations Put(X) place X at the rear of the queue . Get() remove the front element and return it. Front() return front element without removing it. Is_Empty () return TRUE if queue is empty , FALSE otherwise Is_Full () return TRUE if queue is full, FALSE otherwise Queues

3. Implementing Queue using Array Index No. 1 2 3 Head Tail Count A Queue -1 -1 An empty queue Put(‘ A ’) A -1 1 Puts ‘ A ’ in Queue Put(‘ B ’) A B -1 1 2 Puts ‘ B ’ in Queue Put(‘ C ’) A B C -1 2 3 Puts ‘ C ’ in Queue Put(‘ D ’) A B C D -1 (3) → -1 4 Puts ‘ D ’ in Queue Put(‘ E ’) A B C D -1 -1 4 Error : Queue is full Get() B C D -1 3 Gets ‘ A ’ from Queue Put(‘ F ’) F B C D 4 Puts ‘F’ in Queue Get() F C D 1 3 Gets ‘ B ’ from Queue Get() F D 2 2 Gets ‘ C ’ from Queue Get() F (3) → -1 1 Gets ‘ D ’ from Queue Get() Gets ‘ F ’ from Queue Get() Error : Queue is empty

4. #include < iostream > using namespace std ; typedef char Type; #define MAX 4 class Queue{ private : Type qu [MAX ]; // array of any type int head ; //index of start of queue int tail ; // index of end of queue int count ; // number of items public : Queue ::Queue (); bool Is_Full (); bool Is_Empty (); void Put(Type var ); Type Get(); Type Front(); void Show(); }; 4 Example 1 : Implementing Queue using Array Queue::Queue (){ //constructor head = -1; tail = -1; count = 0; } bool Queue:: Is_Full (){ return count >= MAX-1; } bool Queue:: Is_Empty (){ return count <= 0; } 1 2

5. void Queue::Put(Type var ){ // insert at tail of Queue if (count >= MAX ) cout << "Error: Queue is full \n" ; else { qu [++tail] = var ; count++; } if (tail >=MAX-1) // wrap around if past array end tail = -1; } 5 Example 1: Implementing Queue using Array Type Queue::Get (){ // remove item from queue head if (count <= 0){ // if queue empty cout << "Error: Queue is Empty\n" ; return -1; } Type temp = qu [++head]; //store item count- -; if (head >= MAX-1){ // wrap around if past array end head = -1; } return temp; //return item } 3 4

6. Type Queue::Front(){ if (count <= 0){ // if queue empty cout << "Error: Queue is Empty\n" ; return -1; } Type temp = qu [++head ]; -- head; return temp; //return item } void Queue::Show(){ for ( int i = 0 ; i<MAX ; i++){ cout << qu [ i ] << " " ; } cout << "Head = " << head << " Tail = " << tail << endl ; } 6 Example 1: Implementing Queue using Array int main( ){ Queue q; cout << "Put A\n" ; q.Put ( 'A' ); cout << "Put B\n" ; q.Put ( 'B' ); cout << "Put C\n" ; q.Put ( 'C' ); cout << "Put D\n" ; q.Put ( 'D' ); cout << "Put E" ; q.Put ( 'E' ); cout << "Got " ; cout << q.Get () << endl ; cout << "Put F\n" ; q.Put ( 'F' ); cout << "Got " ; cout << q.Get () << endl ; cout << "Got " ; cout << q.Get () << endl ; cout << "Got " ; cout << q.Get () << endl ; cout << "Got " ; cout << q.Get () << endl ; cout << "Got " ; cout << q.Get () << endl ; system ( "PAUSE" ); return 0; } 5 6

7. Using linked List: Recall Insert works in constant time for either end of a linked list. Remove works in constant time only. Seems best that head of the linked list be the front of the queue so that all removes will be from the front. Inserts will be at the end of the list . Implementing Queue using Linked List front 2 5 7 1 1 7 5 2 front rear rear front 2 5 7 1 7 5 2 front rear rear get() front 2 5 7 9 7 5 2 front rear rear put(9 ) 9

8. #include < iostream > using namespace std ; typedef int Type; struct Node{ Type data ; Node *next ; }; class Queue{ private : Node *front, *rear ; public : Queue ( ) ; void Put ( Type Data ) ; Type Get( ) ; ~ Queue( ) ; }; 8 Example 2: Implementing Queue using Linked List Queue :: Queue( ){ front = rear = NULL ; } void Queue :: Put ( Type Data ){ Node * newNode ; newNode = new Node ; if ( newNode == NULL ) cout << "\ nQueue is full" ; newNode -> data = Data ; newNode -> next = NULL ; if ( front == NULL ){ rear = front = newNode ; return ; } rear -> next = newNode ; rear = rear -> next ; } 1 2

9. Type Queue :: Get( ){ if ( front == NULL ){ cout << "Queue is empty" ; return -1; } Node *current ; Type Data ; Data = front -> data ; current = front ; front = front -> next ; delete current ; if (front == NULL) rear = NULL; return Data ; } Queue :: ~Queue( ){ if ( front == NULL ) return ; Node *current ; while ( front != NULL ){ 9 Example 2: Implementing Queue using Linked List current = front ; front = front -> next ; delete current ; } } int main( ){ Queue a ; a.Put ( 11 ) ; a.Put ( -8 ) ; a.Put ( 23 ) ; a.Put ( 19 ) ; cout << a.Get ( ) << endl ; cout << a.Get ( ) << endl ; cout << a.Get ( ) << endl ; cout << a.Get ( ) << endl ; cout << a.Get ( ) << endl ; system ( "PAUSE" ); return 0; } 3 4

10. The queue data structure is used in various CPU and disk scheduling. Here we have multiple tasks requiring CPU or disk at the same time. The CPU or disk time is scheduled for each task using a queue. The queue can also be used for print spooling wherein the number of print jobs is placed in a queue. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e First come first served. Breadth-first Search in which the neighboring nodes of a tree are traversed before moving on to next level uses a queue for implementation. In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free. Applications of Queue

11. Double ended queue is a more generalized form of queue data structure which allows insertion and removal of elements from both the ends, i.e , front and back. Double Ended Queue 1 2 3 4 5 6 Front Rear Pop Back Push Back Push Front Pop Front

12. Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer ’. Circular Queue

13. In priority queue, data when inserted, is stored based on its priority . When we remove a data from a priority queue, the data with least priority, will get removed . Priority Queue 9 Index Number 7 1 7 2 6 3 5 4 3 5 1 6 Data with the highest priority Data with the least priority