Queues Data Structures Tutorial PDF

Queues Selected By: Dr. Asmaa Awad  What is a queue? Queue is a linear data structure that follows FIFO (First In First Out) Principle Queues have two ends: Elements are added at one end. Elements are removed from the other end. The element added first is also removed fir...

Queues Selected By: Dr. Asmaa Awad  What is a queue? Queue is a linear data structure that follows FIFO (First In First Out) Principle Queues have two ends: Elements are added at one end. Elements are removed from the other end. The element added first is also removed first (FIFO: First In, First Out).  In a queue data structure, the insertion operation is performed at a position which is known as 'rear' and the deletion operation is performed at a position which is known as 'front'. QUEUE  Operations on a Queue Enqueue: Add an element to the end of the queue Dequeue: Remove an element from the front of the queue IsEmpty: Check if the queue is empty Peek: Get the value of the front of the queue without removing it  Types of Queue Simple Queue or Linear Queue Linear queue inserts from one end while deletes from the other. Insertion occurs at the back end, while deletion occurs at the front end, following the FIFO principle.  Types of Queue Circular Queue In a circular queue, all nodes are circular. It is identical to a linear queue, except that the last part of the queue is connected to the first. A circular queue is also a ring buffer since all ends are linked.  Types of Queue Priority Queue As the name goes, in a priority queue, components are arranged as per their importance. Each piece in a priority queue is assigned a priority. Features with the same priority are sorted using the FIFO principle. Example In an ascending priority queue, components can be entered in any order, but only the smallest can be eliminated first. Assume an array with elements 7, 5, and 3 in that order. In this queue, insertion can be done using the same sequence, but elements are removed in the order of 3, 5, and 7  Types of Queue Dequeue (Double-Ended Queue) The dequeue can be used as a stack and a queue because it supports insertion and deletion on both ends. Deque may be compared to a stack since stacks adhere to the LIFO (Last In First Out) principle, where insertion and deletion can only be performed from one end.  Enqueue Operation for the first element, set the value of FRONT to 0 increase the REAR index by 1 add the new element in the position pointed to by REAR  Dequeue Operation check if the queue is empty return the value pointed by FRONT increase the FRONT index by 1 for the last element, reset the values of FRONT and REAR to -1  Queue data structure can be implemented in two ways. 1. Using Array  Queue data structure can be implemented in two ways. 2.Using Linked List  Working of Queue Queue operations work as follows: two pointers FRONT and REAR FRONT track the first element of the queue REAR track the last element of the queue initially, set value of FRONT and REAR to -1  Applications of Queue CPU scheduling, Disk Scheduling When data is transferred asynchronously between two processes. The queue is used for synchronization. For example: IO Buffers, pipes, file IO, etc Handling of interrupts in real-time systems. Call Center phone systems use Queues to hold people calling them in order.