Queues Introduction

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.

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.