Introduction to Queue A queue is an ordered collection of items in which deletion takes place at one which is called the front of the queue, and insertion at the other end, which is calledithe rear of the queue. The queue is a ‘First In First Out’ system (FIFO). In a time-sharing system, the be many tasks waiting in the queue, for access to disk storage or for using the The queues in a bank, or railway station counter are examples of queue. The person in the queue is the first to be attended. The two main operations in the queue are insertion and deletion of items. The has two pointers, the front pointer points to the first element of the queue and the! pointer points to the last element of the queue. iSTACKAND. QUEUE | Reet Enqueue Dequeue 3 Figure - 12: Queue 3.1] TYPES OF QUEUES J. Simple Queue — Elements are inserted at the rear and removed from the front. 2. Circular Queue — The rear wraps around to the front when it reaches the end of the array. 3, Priority Queue — Elements are dequeued based on priority instead of order. 4, Deque (Double-ended Queue) — Elements can be inserted and removed from both ends. EEEI OPERATIONS ON A QUEUE 1. Enqueue (Insertion) — Adds an element to the rear. 2. Dequeue (Removal) — Removes an element from the front. 3. Front (Peek) — Returns the front element without removing it. 4, isEmpty — Checks if the queue is empty. 5, isFull — Checks if the queue is full (in the case of a fixed-size implementation). 3.12.1 : Representation of Queue © Queue Representation using Array © — Queue Representation using Linked List 3.12.2 : Array Representation of Queue When the queue is represented using array. First size of the array is defined and let say 5. nt is initializing to -1.Figure 13 shows the array representation of the queue. [0] 1) 2) 1 [4] [5] 2] 6) L LL | Rear=1 Front=1. Figure - 13: Array Representation of Queue Rear and Fro.a 218 Enqueue (Insert at Rear End) © To insert an item into the queue, first it should be verified whether the queue ig, not. IFthe queue is full, a new item cannot be inserted into the queue, The equi FRONT=NULL indicates that the queue is empty. If the queue is not full, iter inserted at the rear end. When an item is added to the queue, the value of tae incremented by 1. Tis © In queue we need to maintain two data pointers, front and rear. Operations on, are comparatively difficult to implement than that of stacks Mere Algorithm for Insertion Step 1 - Check if the queue is full. Step 2 - If the queue is full, produce overflow error and exit. Step 3 - If the queue is not full, increment rear pointer to point the next empty space, Step 4 - Add data element to the queue location, where the rear is pointing. Step 5 - return success. Pseudo code: If Rear= Size-1 then print ‘Queue is Full” if Front—1 the update Front=0 Rear=Rear+1 Queue[Rear]=element ‘Where size is the maximum size of the queue Figure 14 shows the enqueue operation on the queue. Initially the queue is empty. So Frea is -1 and Rear is at -1, Insertion takes place at Rear. So the Rear is updated by ! when element was inserted. C Implementation for Insertion in Queue: void enqueue(int value) { if (rear == SIZE - 1) { printf("Queue is Full! Cannot enqueue %ad\n", value); return; } if (front = -1) front = 0; // Set front to 0 when first element is added reart+; queue[rear] = value; printf("Inserted %d into queue\n", value); }Alo) Any Ala Aly All ALS) Rear=-1 Front=1 Front. Rear Alo} Al) AR) AB) Ala] Als) 10 Enqueue 10 Front Rear Alo) All AR] ABL ata) ats Ti 7 Enqueue 20 —— Front Rear AO) alt) Al] Al) Ala) Als] aD oa 30 Enqueue 30 Ee, Figure - 14: Insert Operation on Queue Dequeue (Delete from Front End) To delete an item from the stack, first it should be verified that the queue is not empty. If the queue is not empty, the items are deleted at the front end of the queue. When an item is deleted from the queue, Dequeue operaticn includes two tasks: access the data where front is pointing and remove the data after access. Step 1 - Check if the queue is empty. Step 2 - If the queue is empty, produce underflow error and exit. Step 3 - If the queue is not empty, access the data where front is pointing. Step 4 - Increment front pointer to point to the next available data element. Step 5 - Return success. the value of the front is incremented by 1. Pseudo code: If Front==-1 or Front>Rear then Print “Queue is Empty Element=Queue[Front] Front=Front+1 If Front >RearFront =Rear =-1 C implementation for Dequeue Operation: void dequeue() { if (front = -1 || front > rear) { Printf{"Queue is Empty! Cannot dequeue\n"); return; } Printf("Removed %d from queue\n", queue[front]); front++; // Reset queue when all elements are dequeued if (front > rear) { front = rear = -1; } } Figure 15 shows the Dequeue operation on an array A of size 5.When an item is deleted from the queue Front is updated to Front + 1. Front Rear a ai) AR) ar) atl fay ats) 10 | 20 | 30 [40 [50 Rear=4 Front=0 Dequeue Operation Front Rear ato) | AB AB) |: AD) 20 | 30 [40 |50 Dequeue 10 Front Rear —T 30 740 [50 Dequeue 20 “ Front Rear a) Aa Pas) Hay as) 40 [50 Dequeve 30 ——— Figure - 15: Delete Operation on Queueam 8 wR ok SY AACN hI C code for the implementation of Queue with insertion and deletion operation. #include #define SIZE 5 // the maximum size of the queue to be 5 int queue[SIZE], front = -1, rear = -1; // Function to insert an element into the queue (Enqueue) void enqueue(int value) { if (rear == SIZE - 1) { printf(Queue is Full! %d\n", value); return; } if (front = -1) front = 0; // Set front to 0 when first element is added reart+; queue[rear] = value; printf("Inserted %d into queue\n", value); } // Function to remove an element from the queue (Dequeue) void dequeue() { if (front == -1 || front > rear) { printf("Queue is Empty! \n"); return; } printf("Removed %d from queue\n", queue[front]);" front++; // Reset queue when all elements are dequeued if (front > rear) { front = rear = -1; } } // Function to display the queue void display() { if (front = -1) { printf("Queue is Empty!\n"); return;} printf("Queue: "); for (int i= frot <= rear; i++) { printf("%d ", queue[i]); } printf("\n"); } // Main function to test the queue operations int main() { enqueue(10); enqueue(20); enqueue(30); enqueue(40); enqueue(50); display; // Show queue contents dequeueQ); // Removes 10 dequeue(); // Removes 20 display); // Show queue contents after deletion return 0; + 3.12.3 : Linked list-Representation of Queue Due to the drawbacks of array, the array implementation cannot be used for the scale applications where the queues are implemented. The alternative of implementation is linked list implementation of queue. Ina linked queue, each node of the queue consists of two parts i.e. data part next part. Each element of the queue points to its immediate next element in the In the linked queue, there are two pointers maintained in the memory i.e. front p and rear pointer. The front pointer contains the address of the starting element ¢ queue while the rear pointer contains the address of the last element of the quet There can be the two scenario of inserting this new node ptr into the linked q front = NULL becomes true. In the second case, the queue contains more element, The condition front = NULL becomes false. Deletion operation removes the element that is first inserted among all th elements. The condition front = NULL becomes true if the list is empty. Othe we will delete the element that is pointed by the pointer front. @STACK AND QUEUE i) ror creating a node in Linked list structure is use as follows: struct Node { : int data; struct Node* next; 1 // Front and Rear pointers struct Node* front = NULL; struct Node* rear = NULL; Here, front and rear is two pointers referring to the node for insertion and deletion. C functions to insert node in queue: void enqueue(int value) { struct Node* ptr = (struct Node*)malloc(sizeof{struct Node)); if (ptr == NULL) { printf("Memory allocation failed!\n"); return; } ptr->data = value; ptr->next = NULL; if (rear = NULL) { // If queue is empty front = rear = ptr; } else { rear->next = ptr; rear = ptr; } printf("Inserted %d into queue\n", value); } C Function to delete element from linked is as follows: void dequeue() { if (front = NULL) { printf("Queue is Empty! Cannot dequeue\n"); return; ‘ } struct Node* temp = front; printf("Removed %d from queue\n", front->data); front = front->next; if (front = NULL) // If queue becomes emptyeT rear = NULL; free(temp); } ERK) CIRCULAR QUEUE © — A more efficient queue representation is obtained by regarding the array Qy circular. Any number of items could be placed on the queue. This implementation queue is called a circular queue because it uses its storage array as if it were q instead of a linear list, © There are two problems associated with linear queue, They are: (a). Time consuming: linear time to be spent in shifting the elements to the of the queue. (b) Signaling queue fall even if the queue is having vacant position, Let us consider a linear queue as shown in figure 16 as follows: Front Rear Alo) An) [= AB) AL |e 30 =| 40 50 55 ] Figure - 16: Queue where front is at index 2 and rear is at index 5 queue is used. In circular queue if we reach the end or inserting elements to it, it is possible to i element at the beginning of the queue. 3.12.1 : Representation of Circular Queue Let us consider a circular queue as shown in figure 17, which can hold maximum six elements. Initially the queue is empty. FR cob, Queue Empty 4 1 MAX =6 FRONT = REAR COUNT =0 3 2 x Circular QueueFRONT =0 4 1 REAR = (REAR + 1) %6=5 COUNT = 5 3 as 2 Circular Queue Now, insert 11 to the circular queue. Then circular queue status will be: F 5 . o R a! FRONT=0 3 t REAR = (REAR + 1) %6 COUNT = 1 3 2 Circular Queue Insert new elements 22, 33, 44 and 55 into the circular queue. The circular queue status is Now, delete an element. The element deleted is the element at the front of the circular queue. So, 11 is deleted. The circular queue status is as follows: 5 F a! FRONT = (FRONT + 1)%6=1 1 REAR =5 COUNT = COUNT -1=4 3 Circular Queue Again, delete an element. The element to be deleted is always pointed to by the FRONT pointer, So, 22 are deleted. The circular queue status is as follows:FRONT = (FRONT + 1)%6=2 REAR COUNT = COUNT - 1 =3 Circular Queue Again, insert another element 66 to the circular queue. The status of the circular queue iy jf 3 FRONT=2 REAR = (REAR + 1) %6=0 COUNT = COUNT + 1=4 Circular Queue Now, insert new elements 77 and 88 into the circular queue. The circular queue status is: 88 |i FRONT = 2, REAR =2 ‘ REAR =REAR % 6=2 COUNT = 6 ‘ 2 KS R i Circular Queue j dd Now, if we insert an element to the circular queue, as COUNT = MAX we cannot ada element to circular queue. So, the circular queue is full. |r § qACKAND. QUEUE. #include Hinclude #define SIZE S$ // Define the maxi int queue[SIZE}, front = -1, year ji Function to check if t} ; int isFullQ { Tee i fal return ((rear + 1) % SIZE = front); } // Function to check if the queue is empty int isEmpty) { return (front == -1); } // Function to enqueue (insert) an element void enqueue(int value) { if (isFullO) { printf("Queue is Full! Cannot enqueue %d\n", value); i i < mum size of the circular queue return; } if (isEmpty() { front = rear = 0; // Initialize front and rear pelse { rear = (rear + 1) % SIZE; // Circular increment } queue[rear] = value; printf("Inserted %d into queue\n", value); } // Function to dequeue (remove) an element void dequeue() { if GsEmpty() { printf("Queue is Empty! Cannot dequeue\n"); return; printi("Removed %d from queue\n", queue[front]);yor 207 if (front == rear) {_// If only one element was present front = rear = -1; } else { front = (front + 1) % SIZE; // Circular increment } } // Function to display the queue void display() { if (isEmpty() { printf("Queue is Empty!\n"); return; } printf("Queue: "); int i= front; while (1) { printf{"%d ", queuefi); if (i = rear) break; i=(i+1)% SIZE; // Circular increment } printf("\n"); } // Main function to test the queue operations int main() { enqueue(10); enqueue(20); enqueue(30); ‘enqueue(40); enqueue(50); display; // Show queue contents dequeueQ); // Removes 10 dequeue(); // Removes 20 display();,// Show queue contents after deletion enqueue(60); enqueue(70); tsR ener display0; // Show queue aft ler addi return 0; ling new clements } EAT In the preceding secti from which ec Wwe saw that a queue in which we insert items at one end and Ve itemis at the other end. In this section we examine an extension of the queue, whi < queue, which provides a means to insert and remove items at both ends of the queue. This data st ; n double-ended pes ne is a deque. The word deque is an acronym derived from peque is shown in figure 18. Deletion s/ Be i> tree aA Ne inser Deletion front Figure 18: Representation of deque « A deque provides four operations enqueue_front: insert an element at front. dequeue_front: delete an element at front. enqueue_rear: insert element at rear. dequeue_rear: delete element at rear ti : enqueue_front(3 3) [|] enqueve_rear(44) [|| dequeue_front(33) enqueue_front(55) 22| dequeue_rear(44) , equeve.reat™) ; | Insertion and Deletion in DqeueHa DATA STRUCTURE . 3.14.1 3.14.2 : Types of Priority Queue There are two types of priority queue: There are two variations of deque. They are: (1) Input restricted deque (IRD) (2) Output restricted deque (ORD) An Input restricted deque is a deque, which allows insertions at one end but allows deletion, at both ends of the list. + An output restricted deque is a deque, which allows deletions at one end but allows insertion, at both ends of the list. ity Queue In priority queue, the clements are inserted and deleted based on their priority. Each elemeny is assigned a priority and the element with the highest priority is given importance ang processed first. Ifall the elements present in the queue have the same priority, then the first element is given importance. The priority queue moves the highest priority elements at the beginning of the priority queue and the lowest priority elements at the back of the priority queue. It supports only those elements that are comparable. Priority queue in the data structure arranges the elements in either ascending or descending order. (1) Ascending order priority queue: In ascending order priority queue, a lower priority number Q) is given as a higher priority in a priority. For example, we take the numbers from 1 to arranged in an ascending order like 1,2,3,4,5; therefore, the smallest number, i.e., 1 is given as the highest priority in a priority queue. ‘a element with the lowest priori element with the highest priority Figure 20: Representation of a Priority Queue Descending order priority queue: In descending order priority queue, a higher priority nunt arranged in descending order like 5, 4, 3, 2, 1; therefore, the largest number, i-e., 5 i as the highest priority in a priority queue.” og ND QUEUE gi Al i pplications of Queue Task Scheduling : Queues ¢ : S can be used to se ’ ity or the order ia which they were receives d to schedule tasks based on priority Resource Allocation : 7 wa . Queues can be used to manage and allocate resources, such as printers or CPU processing time. atch Processing : 7 Batch Processing Queues can be used to handle batch processing jobs, such as data analysis or image rendering. Message Buffering : bea M ; ae vee NE ? Queues can be used to buffer messages in communication systems, ae ‘Age qucues in messaging systems or buffers in computer networks. Event Handling + Queues can be used to handle events in event-driven systems, such as GUI applications or simulation systems, Traffic Management + Queues can be used to manage traffic flow in transportation systems, such as airport control systems or road networks. Operating systems : Operating systems often use queues to manage processes and resources. For example, a process scheduler might use a queue to manage the order in which processes are executed. Network protocols : Network protocols like TCP and UDP use queues to manage packets that are transmitted over the network. Queues can help to ensure that packets are delivered in the correct order and at the appropriate rate. Printer queues : In printing systems, queues are used to manage the order in which print jobs are processed. Jobs are added to the queue as they are submitted, and the printer processes them in the order they were received. Web servers : Web servers use queues to manage incoming requests from clients. Requests are added to the queue as they are received, and they are processed by the server in the order they were received. Breadth-first search algorithm : The breadth-first search algorithm uses a queue to explore nodes in a graph level-by-level. The algorithm starts at a given node, adds its neighbours to the queue, and then processes each neighbour in turn. aa 9