Data Structure and Algorithms |Unit-3 3 Queue > A Queues an ordered collection of items from which items may be deleted at one end (called the front of the queue) > > and into which items may be inserted at the other end (the rear of the queue), ‘The first element inserted into a queue is the first element to be removed. For this reason a queue is sometimes called FIFO (First In First Out). A good example of a queue is any queue of consumers for a resource where the consumer that eame first is served first. The difference between stacks and queues is in removing, In astack we remove the item the most recently added; in a queue, we remove the item the least recently added Queue Insertion and Deletion —_ happen on different ends " { a“ \ equa = From veaeue First in first out 3.1 The Queue ADT > Queues are containers, and they hold values of some type. We must therefore speak of the ADT queue of T, where T is the type of the elements held in the queue. The carrier set of this type is the set of all queues holding elements of type T. The carrier set thus includes the empty queue, the queues with one element of type T, the queues with two elements of type T, and so forth. ‘The basic operations (Primitive Operations) also called as Queue ADT that can be performed on queue are ‘+ MakeEmpty(q): To make q as an empty queue ‘+ IsEmpty(q): To check whether the queue q is empty. Return true if q is empty, return false otherwise. ‘+ IsFull(q): To check whether the queue q is full, Return true in q is full, return false otherwise. + Enqueue(q, x) or Insert(q,x) (or add): To insert an item x at the rear of the queue, if and only if q is not full. ‘+ Dequeue(q) or Delete(q) (or remove): To delete an item from the front of the queue q. if and only if q is not empty. ‘+ Traverse (q): To read entire queue that is display the content of the queue. 4 Applications of Queue: ‘© Task waiting for the printing ‘+ Time sharing system for use of CPU © Foraccess to disk storage ‘+ Task scheduling in operating system + Typesof Queue 32 ‘© Linear Queue or Simple queue © Circular queue + Double ended queue (de-queve) ‘© Priority queue: Priority queue is generally implemented using linked list Implementation of queue: ‘There are two techniques for implementing the queue: ‘Array implementation of queue(static memory allocation) ‘© Linked list implementation of queue(dynamic memory allocation) If Queue is implemented using arrays, we must be sure about the exact number of elements we want to store in the queue, because we huve to declare the size of the ray at design time or before the processing starts. In this ease, the beginning of the: array will become the front for the queue and the Last location of the array will act as rear for the queue, Compiled by:-Naresh Prasad Das Pege 1Data Structure and Algorithms |Unit-3 3.2.1 Linear Queue (Algorithm for Queue Operations) 4 Algorithm for insertion (or Enqueue QINSERT (Queue[MaxSize}, data) Step 1: if Rear = MaxSize -1 print“ Overflow” and Exit Step 2: if Front =-1 and Rear=-1 SET Front = Rear = 0 else SET Rear =Rear +1 [END OF IF| Step 3: SET QueuelRear] = data Step 4: Exit * stunt jon (or D QDELETE (Queue[MaxSize}) Step |: if Front =-1 OR Front > Rear print “Underflow” and Exit else SET data = Queue[Front] SET Front = Front + 1 TEND OF IF| Step 2: EXIT Declaration of a Queue: # define MaxSize 50 /* size of the queue items*/ struct QUEUE { int front, int rear int items{Max Size]; hs typedef struct QUEUE queue: Defining the operations of linear queue: © The MakeEmpty function: void initQueue(queue “q) { qorear q>ftont =-1 E © The isEmpty function: int sEmpty(queue *q) 1 Il q->tear front) Compiled by:-Naresh Prasad Das Poge2Data Structure and Algorithms |Unit-3 ©The isfull function int isFull(queue *) ( itt >rear==) return I else retum 0; ) © The Enqueue function: void Enqueue(queue *q, int data) { iftisFull(q)) ( printf(*quene is fall”); exit(1) } iffq->rear = -1 && q->fron ( qorear = 0; q>front = 0; } else gqereartt: gq items|q->rear] = data; , © The Dequeue function: int Dequeue(queve *q) { int data; iftisEmpty(q)) { printf(*queue is Empty”); exit(Ds } else ( data = q->items{q->front}: q->front++; return di ) 3.2.2. Problems with Linear queue implementation: > Both searand front indices are increased but never decreased. > As items are removed from the queue, the storage space at the beginning of the array is discarded and never used again. Wastage of the space is the main problem with linear queue which is illustrated by the following example. ni a3 | aa [ss 2 e = 2 eo from=2, rear=6 f : This queue is considered full, even though the space at beginning is vacant. > To remove this problem, the first and an obvious solution which comes into our mind is whenever an element is deleted, shift all afterward elements to the left by one position, But if the queue is too large of say 5000 elements it will be difficult job to do and time consuming too. To remove this problem we use circular queue. Compiled by:-Naresh Prasad Das Poge 3Data Structure and Algorithms |Unit-3 4 Representation of Queue in C Hinclude #include Hinclude Hdefine MaxSize 50 struet QUEUE { int items[MaxSize]; int rear; int front: k typedef struct QUEUE queue: void initQueue(queue 4) { qorea q>front = } int isEmpiy(queue *q) { iffq->front == -Ilq->rearcq>front) roturn 15, else return 0s } int isFull(queue *q) { iflq->rear—MaxSize-1) return 1; else return 0; J void Enqueue (queue int); int Dequeue (queue); void display(queue*): int main { int chdata,flag=1; queue las queue *q: = Klay initQueue(); print{("Menu for program:\n"); print{("1 insert \n2:delete\n3:cisplay\n4:exit\n" ); do { printi(*\nEnter youer choice\n"); seanfi"%ed" &ech): switeh(ch) { ease 1: data to be inserted\n"); scanf("ed" Sudata); Compiled by:-Naresh Prasad Das Pege +Data Structure and Algorithms |Unit-3 insert(g,data); break: case 2: data= Dequeue(q): printf( "Deleted item i printt("%ed\n" data); case 3: case 4: default printf("Your choice is wrong\n’); } Jwhile(flag): getch(); return 0; } [esunmme shingert function™seenreneenay void Enqueue(queve *q,int data) { iftisFull(q)) { printfe"Queue is fullwn"); exit(I); ) iffq->rear == -1 && q> front ==-1) { q>rear= 0 >> front, ) else g->rearts; q-items{q->rear] = data; } _poroeneceomidelete lunction™™ PENT HEN int Dequeue(queue *q) { int d; i'isEmpty(q)) + print{("Queue is empty\n"); exit(); J else { d=q-ritems{q->front]: qo>front+; return d; J | Compiled by:-Naresh Prasad Das PogeSData Structure and Algorithms |Unit-3 peeeenere terete display functions) void display(queue *q) { int is iflisEmpty(q)) { printi(” Queue is empty\n"); } else { printi(*\nltems in queue are:"); forlisq-frontsic=q->rearit+) { print" d\t".q->itemsfi); + } } Not “® Wastage of the space is the main problem with linear queue, 1, Tovemove this problem, the first and an obvious solution which comes into our mind is whenever an element is deleted, shift all afterward elements to the left by one position. soteeeeeet=Modified delete function**###=eeeerae 4447 int Dequewe(queue 4) ‘ int di; ifisEmpty(q)) { printf¢"Queue is empty\n"); exit(I); 4 else { deq->itemsiq->front); for(iag-Sfrontsicq->rearsit+) q->items{i}=q->itemsfi+ 11 rear return ds 1 J Tos ji tea st shift £ simply increasing front value but whenever an element need to be inserted, check if rear is equal to mavstze-1 and front is not equal to zero then shift all elements so that front start from zero position, [aveeee2%4 Modified isFull function****#44088404) isFull(queue *q) int if{q->rear==MaxSize-1 && q->front return 1: else return 0; Compiled by:-Naresh Prasad Das Poge 5Data Structure and Algorithms |Unit-3 peorenere++Modified insert funetiont#©#eereeres void Enqueue(queue *q,int data) { tigi iftisFull(q)) { printf” Queue is full\n"); exit(1): q>rear =0; >from = 0; } else if(q->rear MaxSize-1 && q->front != 0) t forti=q->front, j=0; i <= q->rear; itt, j++) q>items|j }=q->itemsfil; q->rear = q->rear- q->lronts q->front } else q>reart+; t ¢->items[q->rear] = data; “But if the queue is too large it will be difficult job to do shifting and time consuming too (Time Complexity high) ‘To remove this problem we use cireular queue, Compiled by:-Naresh Prasad Das Poge 7Data Structure and Algorithms |Unit-3 3.3. Circular Queue > Circular Queue is 4 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. > A circular queue is one in which the insertion of a new element is done at very first location of the queue if the last location of the queue is full, Q{0} (6) Olt] |_| Op O02 Qf] | Q(3} > A circular queue overcomes the problem of unutilized space in linear queue implementation as array. 3.3.1 Algorithm to insert an element in a circular queue ‘This algorithm is assume that rear and front are initially set to MaxSize-1. 1. if (front==(rear+1)% MaxSize) print Queue is full and exit else rear=(rear+1)% MaxSize: [inerement rear by 1] 2, equeuelrear]=dat 3.end 3.3.2. Algorithm to delete an clement from a circular queue This algorithm i assume that rear and front are initially set to MaxSize -1. Lif (rear==front) [checking empty condition] print Queue is empty and exit 2. front=(front+1)% MaxSize: [increment front by 1] 3. data=equee {front}; 4. return data: Send Declaration of a Circular Queue # define MaxSize 50 /* size of the circular queue items*/ struct circularQueue int fror int rears int items[MaxSize}; is typedef struct circularQueue equeve; 4 Qperations on Circular Queue: ‘The MakeEmpty function: void initQueue(cqueue *q) { q->rear= MaxSize -1; Compiled by:-Naresh Prasad Das Poge 8Data Structure and Algorithms |Unit-3 int isEmpty(cqueue “q) The En queue function: void Enqueue(cqueue 4g, int data) { if(IsFulliq)) printf(*queue is fall”); exits q->rears(q->reart 1) % MaxSize; q->items{q->rear}=data; ’ ‘The Dequeue functio int Dequeue(equeue *q) ( int data; if(IsEmpty(q)) ( printf(‘queue is Empty”); exit(D: 1 else ( ¢->front=(q->front+1)% MaxSize: data = q->items(q-afront}: return data; Compiled by:-Naresh Prasad Das Poge 9Data Structure and Algorithms |Unit-3 4 Representation of circular queue in C, with secrifving one cell (One Position Vacant! Hinclude #include define MaxSize 50 struct circularQueue { int items[MaxSize}; int rear; int front; ih typedef struct circularQueue cqueue: void initQueuetcqueue *q) { qr>rear= MaxSize -1; q->front= MaxSize ~ } int isEmpty(cqueue *q) ( if(q->rear—=q->front) return 1; else return 0; } int isFull(equeue *q) { if{q->front=(q->tear+1)% MaxSize) return 1 else return (); } void Enqueue(equeue*): void Dequeue(cqueue™); void Display(cqueue” void main() { int ch,flag=1; equeue *q; equeue og; q=&eq: {init Queue(q): print{(’Menu for program:\n"); print{("I insert\n2:delete\n3:display\n4:exit\n"); do [ printf("\nEnter youer choice\n"); scanfi"%ed" &ch); switeh(ch) { ease 1: Enqueue(q); break; case 2: Compiled by:-Naresh Prasad Das Page 10Data Structure and Algorithms |Unit-3 Dequeue(q); break; case 3: Display(q): break; case 4: flag = 0; break; default: printf" Your choice is wrone\n’ } )while(lag): getch(; } pecteere: insert function eee esy void Enqueue(equeue *q) { int; iftisFull(q)) printf" Queue is full"); ase { ->rear=(q->tear+1)% MaxSize; printf ("Enter data to be inserted\n"y; seanf("Yed",&d); q->items(q->rear}=d; + } peehnmmne te delete function # ern Hee IN, void Dequeue(cqueue *4) ( int data; if'isEmpty(q)) printi("Queue is empty\n"); else { q->front=(q->front+ 1 MaxSize; data = g->items| q->front}; printf("Deleted item is:"); printf("séd\n",data);, i } [ostensaeentenedisplay function settee] void Display(cqueue “q) { int i; iftisEmpry(q)) printf(*Queue is empty\n"); else { printf(“Items of queue are:\n"); for(i=(q->lront+ 1) %MaxSize:i !=y->rear { Compiled by:-Naresh Prasad Das Page 11Data Structure and Algorithms |Unit-3 printf("ed\",q->items{i)); } printf(“sdw" q->items{q->rear)); 4 Representation of circular queue in C, without secrifying one cell by using a count variable #include Hinclude define MaxSize 5 struct circularQueue { int items{MaxSize]; int rear; int fro int count; ik typedef struct circularQueue equeue: void initQueuetcqueue "q) { q->tear= MaxSize -1; q->front= MaxSize ~ ->count = 0; } int isEmpty(equeue *q) { if(q->count==0) return 1; ese return 0; } int isFull(cqueue *q) { if\q>count == MaxSize) return |; else return 0; J void Enqueue(cqueue™); void Dequeue(cqueue*); void Display(cqueue*); void main() { int ch.flag=1; equeue "4; equeue eq; q= &oq: init Queue(q): printf("Menu for program:\n"); printf(" L:insert\n2:delete\n3:display\n4:exit\n"); Compiled by:-Naresh Prasad Das Page 12Data Structure and Algorithms |Unit-3 do | printf((\nEnter youer choice\n"); seanf("Yed" &ch); switeh(ch) { cease |: Enqueue(q); break; case 2: Dequeue(q): break; case 3: Display(q): break; ease 4: flag = 0; break; default: printf(""Your choice is wrong\n"); 1 )while( ag); getch0; } pet tebeeeetinsert function seeeeeeenty void Enqueue(equeue "q) { int d: iftisFullq)) printi(*Queue is fullin"): ese ( q->rear=(q->reartl)% MaxSize; printf ("Enter data to be inserted\n"); seant("9éd" &d); qpitems(q->rearl=d; q>count+; y } peeorommne 8 delete function ere Hore NINE, void Dequeue(cqueue *4) { int data; iffisEmpty(q)) printi(” Queue is empty\n"); else { q>front=(q>front+ 1% MaxSize; data = q->items|q->front]; printf("Deleted item printf(“géd\n",data); q->count-; J | Compiled by:-Naresh Prasad Das Page 13Data Structure and Algorithms |Unit-3 peetenere eee display function® e227) void Display(equeue *q) { int i; iffisEmpty(q)) printi("Queue is empty\n"); else { printf(Items of queue aren"); fort i=(q->front+ 1)%MaxSizesi!=q->rear, { printf sed\".¢->items[i); } printf('sed".g->items|q->rear)); J } 4 Representation of eireutar quewe in C Finclude #ineludecconio.h> Finelude define MaxSize 10 struct CircularQueue { int items| MaxSize]; int rear front; i typedef struct CircularQueue cqueve: void initialize(cqueue *q); int isEmpty(equeue *a); int isFull(cqueue "q): void Insert(cqueue %q); void Delete(equeue *q): void display(equeue "q); int maing) { int ch,flag=15 ‘equeue eq; equeue "ag; ge &oq, initialize(q); printi("\Insert(Rear)n2,Delet(Front)\n5.Print\n6.Exitin"); do { print{\nEinter your choice: scant" edi" &chy: switch(eh) ( case | Insert(q)s break; case 2: Delete(q); break Compiled by:-Naresh Prasad Das Page 14Data Structure and Algorithms |Unit-3 case 3: display(q): printi(* Your choice is wrong\n"); Jwhile (flag); geteh(): return 0; 1 void initialize(equeve *q) { qerear=-1; qofront=-1; } int isEmpty(cqueue *q) { ifltq->rear==-1) return else return 0; } int isFull(equeue *q) { if((q->rear+1)%MaxSize==q-> front) return 1; else return 0: 1 ‘oid Insert(cquewe "q) { int ds iftisFull(q)) { print{(*Queue is Full"); return; } else iflisEmpty(q)) { >rear=0; q>tront=0: ) else { q->rear=(q->rear+l MaxSize; J printf ("Enter data to be insertedin"); seanl("ed" Sd); ->items{q->reari=d: } Compiled by:-Naresh Prasad Das Page 15Data Structure and Algorithms |Unit-3 void Delete(equeue *q) { int data; iffisEmpty(q)) { printi("Queue is Empty"); return; ) data = q->items{q->front|; if(q->front == q->rear) delete the last element initiatize(q): else q->front=(q->front+1)% MaxSize; printi("Deteted item is:%éd" data); 3 void display(equeue *q) { int iftisEmpry(q)) printi( Queue is empty\n"); else { printi(* tems of queue are: isq->front; { print("\nd%dl" g->itemsfil)s +1) % MaxSize; ) printi(*\wncedin® q->itemslq->rear); J J 3.3.3. Application of Circular Queue + Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues. ‘+ Traffic system: In computer controlled traffic system, circular queues are used to switch on the waffic lights one by one repeatedly as per the time set. + CPU Scheduling: Operating systems ofien mainiain a queue of processes that are ready to execute or that are waiting fora particular event to occur. Compiled by:-Naresh Prasad Das Page 15Data Structure and Algorithms |Unit-3 34 DEQUE A deque is a homogeneous list in which elements can be added or inserted (called Enqueue operation) and deleted or removed (called Dequeue operation) from both the ends. ie; we can add a new element at the rear or front end and also we can remove sn element from both front and rear end. Hence itis called Double Ended Queue. I _ Addition ot eid “& Deletion ‘There are two types of deque depending upon the restriction to perform insertion or deletion operations at the two ends. They are ‘+ Input restricted deque: An input restricted deque is a deque, which allows insertion at only 1 end, rear end, but allows deletion at both ends, rear and front end of the lists. + Output restricted deque: An output-restricted deque is a deque, which allows deletion at only one end, front end, but allows insertion at both ends, rear and front ends, of the lists Declaration of a Queue: # define MaxSize 50 /* size of the queue items"? struct QUEUE { int front; int rear; int items[MaxSize} i typedef struct QUEUE queue; ‘The possible operation (Deque formed on deque is ‘+ Insertion of an element at the REAR end of the queue ‘© Deletion of an element from the FRONT end of the queue ‘+ Insertion of an element at the FRONT end of the queue ‘+ Deletion of an clement from the REAR end of the queue + Functions to carry out these four operations using linear array are: ‘+ Insertion of an element at the Rear end of the queue void dginsert_rear(queue %q, int data) ifl(q>rear == (MaxSize - 1)) { rintf("Queue is full"); exit(D); ) else t q->tear = q>rear+ 1; q->items{q->rear] = data: ) | + Deletion of an element from the FRONT end of the queue {nt dqdelete_front(queue *q) { int ck iflg>front q>rear) printi(” Queue is empty") exit(); Compiled by:-Naresh Prasad Das Page 17Data Structure and Algorithms |Unit-3 J else { y>items|q->front); q->front = q->front + 1; return data; J } ‘+ Insertion of an element at the FRONT end of the queue void dginsert_front(queue "q, int data) { ilg>fron! { » printf("Queue is full"); exit(I); } else if(q->iront = -1 && q->rear =-1) { «->front = 0; q>rear=0; ' else qe>fiont = q->front - 1; gpitems{q->front] = data; of an element from the REAR end of the queue int dqdetete_rear(queve *q) { int data: iflq->front == q->rear) { printi("Queve is empty"); exit(I); } else 1 data = q->items{q->rear}; qorear = q->rear- 1; return data; J J ‘+ Function to display the contents (Status) of a queue void dq_display(queue “q) { inti; if(q>front <= q>rear) Compiled by:-Naresh Prasad Das Page 18Data Structure and Algorithms |Unit-3 { printi(*Status of the Queue"): fort ixq->frontsic=q->rearit+) printl("%ed",q->items|il); } else print{("Queue is Empty") 4 Implementation of Deque or Double Ended Queue using circular array #include #include Hinclude Hdefine MaxSize 5 struct Deque { int items{MaxSize}; int rear front; if typedef struct Deque deque: void initialize(deque *q): int isEmpty(deque *q); int isFull(deque *q); void insert_rear(deque *q); void insert_front(deque *q); void delete_front(deque *4); void delete reartdeque *4); void display(deque *q); int main) { int ch,flag=1 deque dq; deque *g; a= Ag; initialize(q) printi("\n Insert Rear)\n2.Jnsert(Front)\n3, Delete(Rear)\n4, Delet(Front)\n5.Print\n6.Exit\n"); do { print{(WnEnter your choice: seantt "ted", &ch): switeh(ch) { case | insert_rear(q); break; case 2: insert_front(q); break: case 3: delete_rear(q): breaks; case 4: delete_front(q); Compiled by:-Naresh Prasad Das Page 19Data Structure and Algorithms |Unit-3 breaks case 5: display(q): break; case 6: printf("Your choice is wrong\n’); 1 )while(flag); getch(); return 0; J void initialize(deque *q) { q>rew=-1; q>front=1; } int isEmpry(deque *a) { iflq->rear==-1) return 1; else rewurn 0; } int isFullideque *a) { ifl(q->rear+1)%MaxSize=q->iront) return 1; else return 0; } void insert_rear(deque *4) { int ds iflisFull(q)) { prind{(’Queue is Full” return; } else iftisEmpty(q)) { q>rea=0; a->front=0; ) else gr>tears(q->teart 1) %MaxSize; print’ ("Enter data to be inserted\n"), scanf("%ed" ed); q->items|q->rear}=d; J void insert_froni(deque *q) Compiled by:-Naresh Prasad Das Page 20Data Structure and Algorithms |Unit-3 { itd; ifisFull(q)) { printi(* Queue is Full"); return; J else iffisEmpty(q)) { q->rear=0; q->front=0: , else 4q->front=(q->front-1+ MaxSize) %MaxSize; printf ("Enter data to be inserted seant( "ed" ded); q->itemslq->fronti=d; } void delete_front(deque *4) { int data; iffisEmpty(q)) { printf("Queue is Empty"); return; ) data = g->items{q->front]; if(q->front == q->rear) delete the last element initiatizeq); else q->front=(q->front+1) MaxSize: printi(* Deleted item is:%d" data): } void delete_rear(deque "q) { int data: ifisEmpty(q)) { printi(” Queue is Empty"): return; } data=q->itemslq->rear; iffq>front == q->rear) delete the last element initialize(q): else q->rear=(q->rear-1+MaxSize)%MaxSize; printi(" Deleted item is:%d" data); } void display(deque *q) { iflisEmpty(q)) printi("Queue is empiy\n"); else. Compiled by:-Naresh Prasad Das Page 21Data Structure and Algorithms |Unit-3 printi(* ems of queue are-in") ieq->front whileG! { >rear) printf("\nséd" i#1)% MaxSize; Pitems|q->rear): ] 3.5 Priority Queues > A priority queue is a collection of elements such that each element has been assigned a priority and the order in which elements are deleted and processed comes from the following rules:. ‘+ Anelement of higher priority is processed before any element of lower priority. ‘+ Ievo elements has same priority then they are processed according to the orderin which they were added to the queue. > The best application of priority queue is observed in CPU scheduling. © The jobs which have higher priority are processed firs. © If the priority of two jobs is same this jobs are processed according to their position in queue. © A shor job is given higher priority over the longer one. ‘Types of priority queues: ‘+ Ascending priority queue(min priority queue): An ascending priority queue is a collection of items into which items can be inserted arbitrarily but from which only the smallest item can be removed. ‘+ Descending priority queue(max priority queue): An descending priority queue is a collection of items into which items can be inserted arbitrarily but from which only the largest item can be removed > The implementation of priority queue using array will yield n comparisons (in liner search), so the time complexity is uch higher than the other queue for inserting an element. So itis always better to implement the priority queue using linked list - where a node can be inserted at anywhere in the list. 3.6 APPLICATION OF QUEUES > Round robin techniques for processor scheduling is implemented using queue. Printer server routines (in drivers) are designed using queues. All types of customer service software (like Railway/Air ticket reservation) are designed using queue to give proper service to the customers, Disk Driver: maintains a queue od disk input/output requests Scheduler (e.g. in operating system): maintains a queue of processes awaiting a slice of machine time. Call center phone systems will use a queue to hold people in line until a service representative is free. Buffers on MP3 players and portable CD players, iPod playlist. Playlist for jukebox - add songs to the end, play from the front of the list, When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling. ‘When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include 10 Buffers, pipes, file 10, etc. vy vvvy vy Compiled by:-Naresh Prasad Das Page 22