{"id":165,"date":"2018-07-18T11:17:37","date_gmt":"2018-07-18T11:17:37","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=165"},"modified":"2018-12-12T09:34:34","modified_gmt":"2018-12-12T09:34:34","slug":"applications-of-queue-adt","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/applications-of-queue-adt\/","title":{"rendered":"Applications of Queue ADT"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/8krkHOhrDZo\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of an important ADT \u2013 the Queue ADT. In this module we will discuss some important applications of Queues.<\/p>\r\n&nbsp;\r\n\r\n<strong>Learning Objectives<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe learning objectives of the introductory module are as follows:\r\n\r\n&nbsp;\r\n\r\n\u2022 To discuss the different applications of Queue\r\n\r\n\u2022 To understand the use of queue for printing jobs &amp; customer service\r\n\r\n\u2022 To explain the simulation of Breadth First Search using Queues\r\n\r\n\u2022 To discuss the use of queues for encoding messages\r\n\r\n&nbsp;\r\n\r\n<strong>13.1 Applications of Queue ADT<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Queues are basically used in applications which require some kind of servicing in the order of arrival. Some typical scenarios include<\/p>\r\n\r\n<ul>\r\n \t<li>Customer servicing for any type application for example waiting for Printer service<\/li>\r\n \t<li>Operating Systems where processes need memory to be allocated in the order of arrival<\/li>\r\n \t<li>Round Robin scheduler where jobs are scheduled again in the order of arrival in a round robin manner<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">\u00a0 \u00a0 Queues are also used as buffer where the order of processing is dictated by First in First out (FIFO) manner. Some examples in this category include:<\/p>\r\n\r\n<ul>\r\n \t<li>Store the vertices yet to be processed in the case of Breadth First Search<\/li>\r\n \t<li>Storing characters for encoding messages<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nThe most common application of queues is in implementing <strong>client-server models.<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">For example multiple clients may be requesting services from one or more servers.I<span style=\"font-size: 1em\">n this situation some clients may have to wait while the servers are busy. These waiting clients are placed in a queue and serviced in the order of arrival. These type of situations occurs in our everyday life also such as in grocery stores, banks, &amp; airport queues.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>13.2\u00a0 Printing Job Management<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Another example that we will use to illustrate the use of queues is in the management of printer jobs. Many users send their printing jobs to a public printer. The printer will put them into a queue according to the arrival time and print the jobs one by one. Figure 13.1 shows the processing of printer jobs. Let us assume that the documents are A.doc, B.doc, C.doc first arrive for printing. Therefore the three jobs are enqueued and A.doc is sent for printing. Next A.doc finishes and is dequeued. Therefore B.doc starts printing. Meanwhile D.doc arrives and is enqueued. while B.doc is still printing. Next B.doc finishes and is dequeued. Now C.doc the document at the front of the queue is sent for printing. Next C.doc finishes and is dequeued. Now the final item in the queue, D.doc is sent for printing. This process will continue as long as documents arrive for printing.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-168 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-67.png\" alt=\"\" width=\"630\" height=\"375\" \/>\r\n\r\n<strong>13.3 Customer Service at State Bank of India<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us consider another example that of customer service in the State Bank of India. Let us assume that every 3 minutes, a new customer arrives at end of the waiting line. Now let us assume that each customer will need 5 minutes for the service. We want to print out the following information after the first 30 minutes that is the time of arrival and departure of each customer, the number of customers in the line, and the identity of the customer currently being served.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">For this purpose create a new queue and initialize the following parameters time, incomingcust and servicetime to 0. We will be servicing customers one by one from\u00a0<span style=\"font-size: 1em;text-align: initial\">the queue and putting customers into the queue as they arrive. We need to print the the status after 30 Minutes. The basic steps is given in Figure 13.2.<\/span><\/p>\r\n\r\n<\/div>\r\n<table style=\"border-collapse: collapse;width: 100%\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 100%\">While time \u2264 30\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2013 If Queue not empty - one customer service is working (use <strong>IsEmpty<\/strong> to check) and<\/p>\r\n<p style=\"text-align: justify\">\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Increment servicetime<\/p>\r\n<p style=\"text-align: justify\">\u2013\u00a0 Assume service time is 5 minutes<\/p>\r\n<p style=\"text-align: justify\">\u2013\u00a0 <strong>Dequeue<\/strong> the customer &amp;<\/p>\r\n<p style=\"text-align: justify\">\u2013\u00a0 Print deleted customer name &amp; time of finishing<\/p>\r\n<p style=\"text-align: justify\">\u2013\u00a0 Start servicetime for next customer<\/p>\r\n<p style=\"text-align: justify\">Every 3 minutes a customer arrives &amp; we need to insert customer to the queue<\/p>\r\n<p style=\"text-align: justify\">Increment incomingcust<\/p>\r\n<p style=\"text-align: justify\"><strong>Enqueue Customer<\/strong><\/p>\r\n<p style=\"text-align: justify\">Print Customer Name &amp; time of Entry (<strong>QueueRear<\/strong>)<\/p>\r\n<p style=\"text-align: justify\">Increment Time<\/p>\r\n<p style=\"text-align: justify\">Print the status after 30 minutes<\/p>\r\n<p style=\"text-align: justify\">If <strong>QueueSize()<\/strong> \u00b9 0<\/p>\r\n<p style=\"text-align: justify\">Size of Queue indicates number of customers waiting<\/p>\r\n<p style=\"text-align: justify\"><strong>QueueFront() <\/strong>\u2013 Indicates current serving Customer<\/p>\r\n<p style=\"text-align: justify\">Else No waiting customers<\/p>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Figure 13.2 Application of Queues for Customer Service<\/strong><\/p>\r\n&nbsp;\r\n\r\nQueue ADT for Customer Service Queue needs the following operations\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0 CreateQueue\r\n\r\n\u2022\u00a0 Enqueue\r\n\r\n\u2022\u00a0 Dequeue\r\n\r\n\u2022\u00a0 IsEmpty\r\n\r\n\u2022\u00a0 QueueFront\r\n\r\n\u2022\u00a0 QueueRear\r\n\r\n\u2022\u00a0 QueueSize\r\n\r\n&nbsp;\r\n\r\n<strong>13.3 Round-Robin Scheduler<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Round robin scheduler can be naturally implemented using a queue, <em>Q<\/em>, by repeatedly performing the following steps:<\/p>\r\n&nbsp;\r\n\r\n\u2022\u00a0\u00a0<em>e = Q.<\/em>dequeue();\u00a0 Service element<em> e;\u00a0 Q.<\/em>enqueue(<em>e<\/em>)\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-169 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-68.png\" alt=\"\" width=\"630\" height=\"196\" \/>\r\n\r\n<\/div>\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong style=\"text-align: initial;font-size: 1em\">13.5 Queue Application - Breadth First Search<\/strong>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us first discuss Breadth First Search (BFS) algorithm and see how queues are used to implement this algorithm.<\/p>\r\n&nbsp;\r\n\r\n<strong>13.5.1 Breadth First Search (BFS) Algorithm<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Breadth-first search (BFS) is a general technique for traversing a graph. One starts at some arbitrary node as the start node and expand shallowest unexpanded node before exploring deeper levels. The steps of the algorithm are explained in Figure 13.4. The algorithm uses a queue to keep track of nodes to visit where new successors go to the end of the queue. Each entry in the queue stores all edges of the node processed and new nodes are added to the rear of the queue.<\/p>\r\n\r\n<table style=\"border-collapse: collapse;width: 100%\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 100%\"><strong>\u00a0 \u00a0Step 1: <\/strong>Initially all nodes are undiscovered. Mark the start node as discovered Enqueue the start node S Front of queue which initially is the start node S . Now enqueue all neighbours of node S into the Queue*\/\r\n\r\n<strong>Step2: <\/strong>Repeat Until queue is Empty\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>a <\/strong>Select the node F in front of queue &amp; mark it as discovered and process it by examining its neighbours.<\/p>\r\n<strong>b <\/strong>Repeat until all neighbours of F have been processed\r\n\r\nIf a neighbour of F has not yet been discovered, add it to the rear of\r\n\r\nqueue\r\n\r\nelse do not add it to queue\r\n\r\n<strong>c <\/strong>Now delete the original node from the queue and go to step 2<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<p style=\"text-align: center\"><strong>Figure 13.4 Steps of the Breadth First Algorithm Using Queues<\/strong><\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-170 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-69.png\" alt=\"\" width=\"621\" height=\"337\" \/>\r\n\r\n<img class=\"alignnone size-full wp-image-171 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-70.png\" alt=\"\" width=\"623\" height=\"557\" \/>\r\n\r\n<img class=\"alignnone size-full wp-image-172 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-71.png\" alt=\"\" width=\"625\" height=\"396\" \/>\r\n\r\n&nbsp;\r\n\r\n(xi)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0(xii)\r\n\r\n<img class=\"alignnone size-full wp-image-173 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-72.png\" alt=\"\" width=\"638\" height=\"607\" \/>\r\n\r\n<img class=\"alignnone size-full wp-image-174 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-73.png\" alt=\"\" width=\"639\" height=\"421\" \/>\r\n\r\n<img class=\"alignnone size-full wp-image-175 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-74.png\" alt=\"\" width=\"636\" height=\"396\" \/>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"alignnone size-full wp-image-176 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-75.png\" alt=\"\" width=\"417\" height=\"246\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Figure 13.5 Running example for Breadth First Search using Queues<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>1.\u00a0<\/strong>Figure 13.5 (i) shows the initially empty queue and the legend shows that each node can be in four states \u2013 Undiscovered, Discovered, Front of Queue or Finished. The directed graph has nodes s,1,2,3,4, 5, 6, 7, 8, and 9. Initially all nodes are undiscovered. The algorithm starts with the start node s and will finally find the goal node or will discover all the nodes either because goal node is not found or we want to traverse the complete graph in breadth first manner.<strong>\u00a0<\/strong><\/p>\r\n<p style=\"text-align: justify\"><strong>2.\u00a0<\/strong>According to step 1 we <strong>dicover the start node s<\/strong> &amp; <strong>enqueue s<\/strong> Figure 13.5(ii). Now we are processing Level 0.<\/p>\r\n<p style=\"text-align: justify\"><strong>3.\u00a0<\/strong>Now we go to Step 2 and enqueue all the neighbours of s which are 2,3 and 5. We are processing at level 1. When all neighbours are enqueued we dequeue node s. (Figure 13.5 (iii-v)).<\/p>\r\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><strong>4.\u00a0<\/strong>Now we start processing node 2 which is the node in front of the queue and start processing the neighbours of 2 (Figure 13.5 (vi)). Now we are processing at level 2.<\/p>\r\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">5.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 2 (4,5) which have not yet been discovered (only 4 since 5 has already been discovered). When all undiscovered neighbours are enqueued, we dequeue node 2. (Figure 13.5 (vii)).<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">6.<\/strong><span style=\"text-align: justify;font-size: 1em\">Now we start processing node 3 which is the node in front of the queue and start processing the neighbours of 3 (Figure 13.5 (viii)). We are still processing at level 2.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">7.\u00a0<\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 3 (5,6) which have not yet been discovered (only 6 since 5 has already been discovered) (Figure 13.5 (ix)). When all undiscovered neighbours are enqueued, we dequeue node 3. (Figure 13.5 (x)).<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">8.\u00a0<\/strong><span style=\"font-size: 1em\">Now we start processing node 5 which is the node in front of the queue and start processing the neighbours of 3 (Figure 13.5 (xi)). We are still processing at level 2.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">9.\u00a0<\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 5 (only 6) which have not yet been discovered (no neighbour that has not been discovered) (Figure 13.5 xi)). When all undiscovered neighbours are enqueued, we dequeue node 5. (Figure 13.5 (xii)).<\/span><\/p>\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">1<\/span><strong style=\"font-size: 1em\">0. <\/strong><span style=\"font-size: 1em\">Now we start processing node 4 which is the node in front of the queue and start processing the neighbours of 4 (Figure 13.5 (xiii)). We are still processing at level 2.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">11. <\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 4 (5,8) which have\u00a0<\/span><span style=\"text-align: initial;font-size: 1em\">not yet been discovered (only 8 since 5 has already been discovered)) (Figure 13.5 xiv)). When all undiscovered neighbours are enqueued, we dequeue node 4. (Figure 13.5 (xv)). We are now processing at level 3<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">12.<\/strong><span style=\"font-size: 1em\">Now we start processing node 6 which is the node in front of the queue and start processing the neighbours of 6 (Figure 13.5 (xvi)). We are still processing at level 3.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">13. <\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 6 (7,9) which have not yet been discovered (7 &amp; 9)) (Figure 13.5 xvii)). When all neighbours are enqueued, we dequeue node 6. (Figure 13.5 (xviii)). We are now processing at level 3<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">14.<\/strong><span style=\"font-size: 1em\">Now we start processing node 8 which is the node in front of the queue and start processing the neighbours of 8 that are to be inserted. 8 has no neighbours (Figure 13.5 (xix)). We are still processing at level 3.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">15.<\/strong><span style=\"font-size: 1em\">Now we start processing node 7 which is the node in front of the queue and start processing the neighbours of 7 (Figure 13.5 (xx)). We are still processing at level 3.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">16. <\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 7 (4,5,8) which have not yet been discovered (no neighbour that has not been discovered) -(Figure 13.5 xxi-xxii)). Therefore we dequeue node 7. (Figure 13.5 (xxiii)). We are now processing at level 3<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">17. <\/strong><span style=\"font-size: 1em\">Now we start processing node 9 which is the node in front of the queue and start processing the neighbours of 9 (Figure 13.5 (xxiv)). We are still processing at level 3.<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">18. <\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 9 (7,8) which have not yet been discovered (no neighbour that has not been discovered) -(Figure 13.5 xxv-xxvi)). Therefore we dequeue node 9. (Figure 13.5 (xxvi)). We are now processing at level 3<\/span><\/p>\r\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">19. <\/strong><span style=\"text-align: initial;font-size: 1em\">Now all nodes have been traversed and the algorithm is completed according to step 2.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">As you can see the queue is the crucial data structure used in this algorithm for keeping track of nodes that are to be discovered.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">Using Queues: Coding Messages<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The queue is also used for encoding. In this example the coding is based on shifting a letter depending on where the letter is in the message. Here we use a <\/span><em style=\"font-size: 1em\">repeating<\/em> <em style=\"font-size: 1em\">key<\/em><span style=\"font-size: 1em\">, a sequence of integers to determine how much each character is to be shifted<\/span><\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Example: <\/strong>Consider the repeating key 3 1 7 4 2 5. The first character in the message is shifted by 3, the next by 1, the next by 7, and so on. The encoding and decoding using the repeating key is shown in Figure 13.6. When the key is exhausted, start over from beginning of the key. We can use a queue to store the values of the key, <em>dequeue<\/em> a key value when needed. After using it, <em>enqueue<\/em> it back onto the end of the queue so that the queue represents the constantly cycling values in the key. Note that there are <em>two<\/em> copies of the key, stored in two separate queues where the encoder has one copy and the decoder has a separate copy<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-177 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-76.png\" alt=\"\" width=\"610\" height=\"292\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n<ul>\r\n \t<li>Discussed the different applications of Queue<\/li>\r\n \t<li>Explained the use of queue for printing jobs &amp; customer service<\/li>\r\n \t<li>Explained through simulation the use of queues for Breadth First Search<\/li>\r\n \t<li>Discussed the use of queue for encoding messages using repeating key.<\/li>\r\n<\/ul>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Applications of Queue ADT<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/8krkHOhrDZo\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n<img class=\" wp-image-178 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-77.png\" alt=\"\" width=\"815\" height=\"643\" \/>","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/8krkHOhrDZo\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of an important ADT \u2013 the Queue ADT. In this module we will discuss some important applications of Queues.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Learning Objectives<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The learning objectives of the introductory module are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022 To discuss the different applications of Queue<\/p>\n<p>\u2022 To understand the use of queue for printing jobs &amp; customer service<\/p>\n<p>\u2022 To explain the simulation of Breadth First Search using Queues<\/p>\n<p>\u2022 To discuss the use of queues for encoding messages<\/p>\n<p>&nbsp;<\/p>\n<p><strong>13.1 Applications of Queue ADT<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Queues are basically used in applications which require some kind of servicing in the order of arrival. Some typical scenarios include<\/p>\n<ul>\n<li>Customer servicing for any type application for example waiting for Printer service<\/li>\n<li>Operating Systems where processes need memory to be allocated in the order of arrival<\/li>\n<li>Round Robin scheduler where jobs are scheduled again in the order of arrival in a round robin manner<\/li>\n<\/ul>\n<p style=\"text-align: justify\">\u00a0 \u00a0 Queues are also used as buffer where the order of processing is dictated by First in First out (FIFO) manner. Some examples in this category include:<\/p>\n<ul>\n<li>Store the vertices yet to be processed in the case of Breadth First Search<\/li>\n<li>Storing characters for encoding messages<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>The most common application of queues is in implementing <strong>client-server models.<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For example multiple clients may be requesting services from one or more servers.I<span style=\"font-size: 1em\">n this situation some clients may have to wait while the servers are busy. These waiting clients are placed in a queue and serviced in the order of arrival. These type of situations occurs in our everyday life also such as in grocery stores, banks, &amp; airport queues.<\/span><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>13.2\u00a0 Printing Job Management<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Another example that we will use to illustrate the use of queues is in the management of printer jobs. Many users send their printing jobs to a public printer. The printer will put them into a queue according to the arrival time and print the jobs one by one. Figure 13.1 shows the processing of printer jobs. Let us assume that the documents are A.doc, B.doc, C.doc first arrive for printing. Therefore the three jobs are enqueued and A.doc is sent for printing. Next A.doc finishes and is dequeued. Therefore B.doc starts printing. Meanwhile D.doc arrives and is enqueued. while B.doc is still printing. Next B.doc finishes and is dequeued. Now C.doc the document at the front of the queue is sent for printing. Next C.doc finishes and is dequeued. Now the final item in the queue, D.doc is sent for printing. This process will continue as long as documents arrive for printing.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-168 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-67.png\" alt=\"\" width=\"630\" height=\"375\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-67.png 630w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-67-300x179.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-67-65x39.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-67-225x134.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-67-350x208.png 350w\" sizes=\"auto, (max-width: 630px) 100vw, 630px\" \/><\/p>\n<p><strong>13.3 Customer Service at State Bank of India<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us consider another example that of customer service in the State Bank of India. Let us assume that every 3 minutes, a new customer arrives at end of the waiting line. Now let us assume that each customer will need 5 minutes for the service. We want to print out the following information after the first 30 minutes that is the time of arrival and departure of each customer, the number of customers in the line, and the identity of the customer currently being served.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For this purpose create a new queue and initialize the following parameters time, incomingcust and servicetime to 0. We will be servicing customers one by one from\u00a0<span style=\"font-size: 1em;text-align: initial\">the queue and putting customers into the queue as they arrive. We need to print the the status after 30 Minutes. The basic steps is given in Figure 13.2.<\/span><\/p>\n<\/div>\n<table style=\"border-collapse: collapse;width: 100%\">\n<tbody>\n<tr>\n<td style=\"width: 100%\">While time \u2264 30<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2013 If Queue not empty &#8211; one customer service is working (use <strong>IsEmpty<\/strong> to check) and<\/p>\n<p style=\"text-align: justify\">\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Increment servicetime<\/p>\n<p style=\"text-align: justify\">\u2013\u00a0 Assume service time is 5 minutes<\/p>\n<p style=\"text-align: justify\">\u2013\u00a0 <strong>Dequeue<\/strong> the customer &amp;<\/p>\n<p style=\"text-align: justify\">\u2013\u00a0 Print deleted customer name &amp; time of finishing<\/p>\n<p style=\"text-align: justify\">\u2013\u00a0 Start servicetime for next customer<\/p>\n<p style=\"text-align: justify\">Every 3 minutes a customer arrives &amp; we need to insert customer to the queue<\/p>\n<p style=\"text-align: justify\">Increment incomingcust<\/p>\n<p style=\"text-align: justify\"><strong>Enqueue Customer<\/strong><\/p>\n<p style=\"text-align: justify\">Print Customer Name &amp; time of Entry (<strong>QueueRear<\/strong>)<\/p>\n<p style=\"text-align: justify\">Increment Time<\/p>\n<p style=\"text-align: justify\">Print the status after 30 minutes<\/p>\n<p style=\"text-align: justify\">If <strong>QueueSize()<\/strong> \u00b9 0<\/p>\n<p style=\"text-align: justify\">Size of Queue indicates number of customers waiting<\/p>\n<p style=\"text-align: justify\"><strong>QueueFront() <\/strong>\u2013 Indicates current serving Customer<\/p>\n<p style=\"text-align: justify\">Else No waiting customers<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Figure 13.2 Application of Queues for Customer Service<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Queue ADT for Customer Service Queue needs the following operations<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0 CreateQueue<\/p>\n<p>\u2022\u00a0 Enqueue<\/p>\n<p>\u2022\u00a0 Dequeue<\/p>\n<p>\u2022\u00a0 IsEmpty<\/p>\n<p>\u2022\u00a0 QueueFront<\/p>\n<p>\u2022\u00a0 QueueRear<\/p>\n<p>\u2022\u00a0 QueueSize<\/p>\n<p>&nbsp;<\/p>\n<p><strong>13.3 Round-Robin Scheduler<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Round robin scheduler can be naturally implemented using a queue, <em>Q<\/em>, by repeatedly performing the following steps:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0\u00a0<em>e = Q.<\/em>dequeue();\u00a0 Service element<em> e;\u00a0 Q.<\/em>enqueue(<em>e<\/em>)<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-169 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-68.png\" alt=\"\" width=\"630\" height=\"196\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-68.png 630w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-68-300x93.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-68-65x20.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-68-225x70.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-68-350x109.png 350w\" sizes=\"auto, (max-width: 630px) 100vw, 630px\" \/><\/p>\n<\/div>\n<p><strong>\u00a0<\/strong><\/p>\n<p><strong style=\"text-align: initial;font-size: 1em\">13.5 Queue Application &#8211; Breadth First Search<\/strong><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us first discuss Breadth First Search (BFS) algorithm and see how queues are used to implement this algorithm.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>13.5.1 Breadth First Search (BFS) Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Breadth-first search (BFS) is a general technique for traversing a graph. One starts at some arbitrary node as the start node and expand shallowest unexpanded node before exploring deeper levels. The steps of the algorithm are explained in Figure 13.4. The algorithm uses a queue to keep track of nodes to visit where new successors go to the end of the queue. Each entry in the queue stores all edges of the node processed and new nodes are added to the rear of the queue.<\/p>\n<table style=\"border-collapse: collapse;width: 100%\">\n<tbody>\n<tr>\n<td style=\"width: 100%\"><strong>\u00a0 \u00a0Step 1: <\/strong>Initially all nodes are undiscovered. Mark the start node as discovered Enqueue the start node S Front of queue which initially is the start node S . Now enqueue all neighbours of node S into the Queue*\/<\/p>\n<p><strong>Step2: <\/strong>Repeat Until queue is Empty<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>a <\/strong>Select the node F in front of queue &amp; mark it as discovered and process it by examining its neighbours.<\/p>\n<p><strong>b <\/strong>Repeat until all neighbours of F have been processed<\/p>\n<p>If a neighbour of F has not yet been discovered, add it to the rear of<\/p>\n<p>queue<\/p>\n<p>else do not add it to queue<\/p>\n<p><strong>c <\/strong>Now delete the original node from the queue and go to step 2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p style=\"text-align: center\"><strong>Figure 13.4 Steps of the Breadth First Algorithm Using Queues<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-170 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-69.png\" alt=\"\" width=\"621\" height=\"337\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-69.png 621w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-69-300x163.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-69-65x35.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-69-225x122.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-69-350x190.png 350w\" sizes=\"auto, (max-width: 621px) 100vw, 621px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-171 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-70.png\" alt=\"\" width=\"623\" height=\"557\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-70.png 623w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-70-300x268.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-70-65x58.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-70-225x201.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-70-350x313.png 350w\" sizes=\"auto, (max-width: 623px) 100vw, 623px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-172 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-71.png\" alt=\"\" width=\"625\" height=\"396\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-71.png 625w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-71-300x190.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-71-65x41.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-71-225x143.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-71-350x222.png 350w\" sizes=\"auto, (max-width: 625px) 100vw, 625px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>(xi)\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0(xii)<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-173 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-72.png\" alt=\"\" width=\"638\" height=\"607\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-72.png 638w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-72-300x285.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-72-65x62.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-72-225x214.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-72-350x333.png 350w\" sizes=\"auto, (max-width: 638px) 100vw, 638px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-174 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-73.png\" alt=\"\" width=\"639\" height=\"421\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-73.png 639w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-73-300x198.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-73-65x43.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-73-225x148.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-73-350x231.png 350w\" sizes=\"auto, (max-width: 639px) 100vw, 639px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-175 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-74.png\" alt=\"\" width=\"636\" height=\"396\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-74.png 636w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-74-300x187.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-74-65x40.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-74-225x140.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-74-350x218.png 350w\" sizes=\"auto, (max-width: 636px) 100vw, 636px\" \/><\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-176 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-75.png\" alt=\"\" width=\"417\" height=\"246\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-75.png 417w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-75-300x177.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-75-65x38.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-75-225x133.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-75-350x206.png 350w\" sizes=\"auto, (max-width: 417px) 100vw, 417px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Figure 13.5 Running example for Breadth First Search using Queues<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>1.\u00a0<\/strong>Figure 13.5 (i) shows the initially empty queue and the legend shows that each node can be in four states \u2013 Undiscovered, Discovered, Front of Queue or Finished. The directed graph has nodes s,1,2,3,4, 5, 6, 7, 8, and 9. Initially all nodes are undiscovered. The algorithm starts with the start node s and will finally find the goal node or will discover all the nodes either because goal node is not found or we want to traverse the complete graph in breadth first manner.<strong>\u00a0<\/strong><\/p>\n<p style=\"text-align: justify\"><strong>2.\u00a0<\/strong>According to step 1 we <strong>dicover the start node s<\/strong> &amp; <strong>enqueue s<\/strong> Figure 13.5(ii). Now we are processing Level 0.<\/p>\n<p style=\"text-align: justify\"><strong>3.\u00a0<\/strong>Now we go to Step 2 and enqueue all the neighbours of s which are 2,3 and 5. We are processing at level 1. When all neighbours are enqueued we dequeue node s. (Figure 13.5 (iii-v)).<\/p>\n<p style=\"text-align: justify\"><strong>\u00a0<\/strong><strong>4.\u00a0<\/strong>Now we start processing node 2 which is the node in front of the queue and start processing the neighbours of 2 (Figure 13.5 (vi)). Now we are processing at level 2.<\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">5.\u00a0<\/strong><span style=\"text-align: justify;font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 2 (4,5) which have not yet been discovered (only 4 since 5 has already been discovered). When all undiscovered neighbours are enqueued, we dequeue node 2. (Figure 13.5 (vii)).<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: justify;font-size: 1em\">6.<\/strong><span style=\"text-align: justify;font-size: 1em\">Now we start processing node 3 which is the node in front of the queue and start processing the neighbours of 3 (Figure 13.5 (viii)). We are still processing at level 2.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">7.\u00a0<\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 3 (5,6) which have not yet been discovered (only 6 since 5 has already been discovered) (Figure 13.5 (ix)). When all undiscovered neighbours are enqueued, we dequeue node 3. (Figure 13.5 (x)).<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">8.\u00a0<\/strong><span style=\"font-size: 1em\">Now we start processing node 5 which is the node in front of the queue and start processing the neighbours of 3 (Figure 13.5 (xi)). We are still processing at level 2.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">9.\u00a0<\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 5 (only 6) which have not yet been discovered (no neighbour that has not been discovered) (Figure 13.5 xi)). When all undiscovered neighbours are enqueued, we dequeue node 5. (Figure 13.5 (xii)).<\/span><\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">1<\/span><strong style=\"font-size: 1em\">0. <\/strong><span style=\"font-size: 1em\">Now we start processing node 4 which is the node in front of the queue and start processing the neighbours of 4 (Figure 13.5 (xiii)). We are still processing at level 2.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">11. <\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 4 (5,8) which have\u00a0<\/span><span style=\"text-align: initial;font-size: 1em\">not yet been discovered (only 8 since 5 has already been discovered)) (Figure 13.5 xiv)). When all undiscovered neighbours are enqueued, we dequeue node 4. (Figure 13.5 (xv)). We are now processing at level 3<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">12.<\/strong><span style=\"font-size: 1em\">Now we start processing node 6 which is the node in front of the queue and start processing the neighbours of 6 (Figure 13.5 (xvi)). We are still processing at level 3.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">13. <\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 6 (7,9) which have not yet been discovered (7 &amp; 9)) (Figure 13.5 xvii)). When all neighbours are enqueued, we dequeue node 6. (Figure 13.5 (xviii)). We are now processing at level 3<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">14.<\/strong><span style=\"font-size: 1em\">Now we start processing node 8 which is the node in front of the queue and start processing the neighbours of 8 that are to be inserted. 8 has no neighbours (Figure 13.5 (xix)). We are still processing at level 3.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">15.<\/strong><span style=\"font-size: 1em\">Now we start processing node 7 which is the node in front of the queue and start processing the neighbours of 7 (Figure 13.5 (xx)). We are still processing at level 3.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">16. <\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 7 (4,5,8) which have not yet been discovered (no neighbour that has not been discovered) -(Figure 13.5 xxi-xxii)). Therefore we dequeue node 7. (Figure 13.5 (xxiii)). We are now processing at level 3<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">17. <\/strong><span style=\"font-size: 1em\">Now we start processing node 9 which is the node in front of the queue and start processing the neighbours of 9 (Figure 13.5 (xxiv)). We are still processing at level 3.<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"font-size: 1em\">18. <\/strong><span style=\"font-size: 1em\">Now we go to Step 3 and enqueue all the neighbours of 9 (7,8) which have not yet been discovered (no neighbour that has not been discovered) -(Figure 13.5 xxv-xxvi)). Therefore we dequeue node 9. (Figure 13.5 (xxvi)). We are now processing at level 3<\/span><\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">19. <\/strong><span style=\"text-align: initial;font-size: 1em\">Now all nodes have been traversed and the algorithm is completed according to step 2.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">As you can see the queue is the crucial data structure used in this algorithm for keeping track of nodes that are to be discovered.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">Using Queues: Coding Messages<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The queue is also used for encoding. In this example the coding is based on shifting a letter depending on where the letter is in the message. Here we use a <\/span><em style=\"font-size: 1em\">repeating<\/em> <em style=\"font-size: 1em\">key<\/em><span style=\"font-size: 1em\">, a sequence of integers to determine how much each character is to be shifted<\/span><\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Example: <\/strong>Consider the repeating key 3 1 7 4 2 5. The first character in the message is shifted by 3, the next by 1, the next by 7, and so on. The encoding and decoding using the repeating key is shown in Figure 13.6. When the key is exhausted, start over from beginning of the key. We can use a queue to store the values of the key, <em>dequeue<\/em> a key value when needed. After using it, <em>enqueue<\/em> it back onto the end of the queue so that the queue represents the constantly cycling values in the key. Note that there are <em>two<\/em> copies of the key, stored in two separate queues where the encoder has one copy and the decoder has a separate copy<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-177 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-76.png\" alt=\"\" width=\"610\" height=\"292\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-76.png 610w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-76-300x144.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-76-65x31.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-76-225x108.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-76-350x168.png 350w\" sizes=\"auto, (max-width: 610px) 100vw, 610px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<ul>\n<li>Discussed the different applications of Queue<\/li>\n<li>Explained the use of queue for printing jobs &amp; customer service<\/li>\n<li>Explained through simulation the use of queues for Breadth First Search<\/li>\n<li>Discussed the use of queue for encoding messages using repeating key.<\/li>\n<\/ul>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Applications of Queue ADT<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/8krkHOhrDZo\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-178 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-77.png\" alt=\"\" width=\"815\" height=\"643\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-77.png 653w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-77-300x237.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-77-65x51.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-77-225x177.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-77-350x276.png 350w\" sizes=\"auto, (max-width: 815px) 100vw, 815px\" \/><\/p>\n","protected":false},"author":3,"menu_order":13,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-t-v-geetha"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-165","chapter","type-chapter","status-publish","hentry","contributor-dr-t-v-geetha"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/165","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":14,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/165\/revisions"}],"predecessor-version":[{"id":922,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/165\/revisions\/922"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/165\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/media?parent=165"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapter-type?post=165"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/contributor?post=165"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/license?post=165"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}