Queue
A linear data structure that follows the FIFO (First In, First Out) principle.
Intuition
Imagine standing in line at a movie theater. The first person to arrive is the first one to buy a ticket and leave the line. New people join at the back. This is FIFO (First In, First Out).
Concept
A Queue is a linear data structure that follows the FIFO principle. Elements are added at one end (Rear) and removed from the other end (Front).
How it Works
We maintain two pointers: Front (for removal) and Rear (for insertion).
- Enqueue: Add element to Rear, increment Rear index.
- Dequeue: Remove element from Front, increment Front index.
- Peek: View element at Front.
Step-by-Step Breakdown
- Start Empty: Front = 0, Rear = -1.
- Enqueue(10): Rear becomes 0, Queue[0] = 10.
- Enqueue(20): Rear becomes 1, Queue[1] = 20.
- Dequeue(): Return Queue[0] (10), Front becomes 1.
Example Trace
Enqueue(A)
Person A joins the line.
[A]
Enqueue(B)
Person B joins behind A.
[A, B]
Dequeue()
Person A (Front) leaves. B is now Front.
[B]
When to Use
- Resource Sharing: Printer spooling, CPU task scheduling.
- Asynchronous Data: Handling data buffers (IO, pipes).
- BFS: Breadth-First Search in graphs.
When NOT to Use
- Random Access: Need to access elements in the middle? Use Array.
- Priority: If some items need to jump the line, use Priority Queue.
How to Identify
Look for problems involving "First come, first served", "Fairness", or "Level-order" processing. Keywords: "Buffer", "Stream", "Order preservation".
Frequently Asked Questions
What is FIFO in a Queue?
FIFO stands for First-In-First-Out, meaning the first element added to the queue is the first one to be removed.
What are the main operations in a Queue?
The primary operations are Enqueue (adding to the rear) and Dequeue (removing from the front).
Real-world examples of a Queue?
Queues are used in printer job scheduling, ticket booking systems, and request handling in web servers.