Queues Data Structure PDF

Queues Definition of Queues A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are analogous to real-world lines, such as a queue at a bank or a line at...

Queues Definition of Queues A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are analogous to real-world lines, such as a queue at a bank or a line at a supermarket, where the first person to enter the line is the first to be served. Applications of Queues Task Scheduling: In operating systems, queues are used to manage processes that are waiting for CPU time or other resources. Breadth-First Search (BFS): Queues are essential in graph traversal algorithms, such as BFS, where nodes are explored layer by layer. Print Spooling: When multiple documents are sent to a printer, they are placed in a queue. The first document in the queue is printed first. Network Traffic Management: In routers and  switches, data packets are stored in queues to ensure that they are processed in the order they were received. Asynchronous Data Transfer: Queues are used in scenarios where data is produced at one rate and consumed at another, like in producer-consumer problems or buffer implementations. Basic Operations of Queue Data Structure Enqueue (Insert): Adds an element to the rear of the queue. Dequeue (Delete): Removes and returns the element from the front of the queue. Peek: Returns the element at the front of the queue without removing it. Empty: Checks if the queue is empty. Full: Checks if the queue is full. Queue Operations Enqueue: This operation adds an element to the rear (or end) of the queue. If the queue is implemented using an array,  you move the rear pointer and insert the element at that index. In a linked list, you create a new node and link it to the previous rear element. Queue Operations Dequeue: This operation removes an element from the front of the queue. In an array implementation, the front pointer moves to the next index. In a linked list, the head node is removed, and the next node becomes the new head. Queue Operations Front: Retrieves the front element of the queue without removing it. This is the first element that was added and will be the next to be dequeued. Rear: Retrieves the rear element of the queue without removing it.  This is the last element that was added to the queue. Implementation of Queues Using Arrays Array-Based Queue: In an array implementation, we maintain two pointers, front and rear, to keep track of the start and end of the queue. Initially, both front and rear are set to -1 (empty queue). When an element is enqueued, the rear pointer is incremented. When an element is dequeued, the front pointer is incremented. The queue has a fixed size, so once the rear reaches the end of the array, no more elements can be added (unless we use a circular queue). Implementation of Queues Using Linked Lists In a linked list-based queue, each element is a node that points to the next node, with two pointers (front and rear) keeping track of the start and end of the queue. Enqueue: A new node is added at the rear, and the rear pointer is updated. Dequeue: The front node is removed, and the front pointer is updated to the next node. Variants of Queues Circular Queue: In a circular queue, the array wraps around when the rear reaches the end, reusing the free spaces at the beginning of the array. This prevents wastage of space in fixed-size array implementations. Variants of Queues Priority Queue: Elements are dequeued based on their priority rather than their insertion order. Applications include scheduling algorithms where processes with higher priority are executed first. Implemented using a heap or a sorted linked  list. Variants of Queues Deque (Double-Ended Queue): A deque allows insertion and deletion from both the front and rear. It can function as both a queue and a stack. Used in algorithms like the sliding window maximum, where both ends need to be accessed efficiently.