Queues are a fundamental linear data structure that follow the First-In First-Out (FIFO) principle. This means the first element added to the queue will be the first one to be removed. Queues are widely used in operating systems, network buffers, printers, and scheduling systems.
What is a Queue?
A queue is a linear structure where elements are inserted at one end called the rear and removed from the other end called the front. This order ensures that the element which has been in the queue the longest is processed first — just like a line of people waiting at a ticket counter.
front
rear
Key Features of Queues
1. FIFO Order
Queues follow First-In First-Out order. The earliest inserted element is always the first one to be removed. This behavior is ideal for handling tasks in the order they arrive.
2. Enqueue and Dequeue Operations
Queues support two main operations: enqueue() to add an element at the rear and dequeue() to remove the element from the front.
Enqueue
Dequeue
3. Front and Rear Access
Queues give access to two pointers — front and rear — representing the ends from which data is removed or added. You cannot directly access elements in between without dequeuing the earlier ones.
4. Efficient Linear Processing
Queues are perfect for problems requiring ordered processing — like scheduling print jobs or handling requests in the order they arrive. Each operation happens in constant time, making queues highly efficient.
5. Variants of Queues
Besides the basic queue, there are many variants like:
- Circular Queue: Reuses freed spaces to avoid shifting elements.
- Deque (Double-Ended Queue): Allows insertion/removal at both ends.
- Priority Queue: Elements are dequeued based on priority, not order.
Common Use Cases of Queues
1. Task Scheduling
Operating systems use queues to schedule tasks based on their arrival time. Each process is placed in a queue and executed in FIFO order unless priorities override it.
2. Print Job Management
When multiple print jobs are sent to a printer, they are queued up. The printer processes each job in the order it was received using a queue.
3. Breadth-First Search (BFS)
BFS in graphs or trees uses queues to explore nodes level by level. Nodes are enqueued as they are visited and dequeued for processing.
4. Buffer Handling in Networks
Data packets arriving at a network port are queued before being processed. This ensures packets are handled in the same order they arrive.
5. Event Handling in GUI
In graphical interfaces, events like mouse clicks and key presses are added to an event queue and processed sequentially by the event loop.