Queue

What is a Queue?

A Queue is an abstract, linear data structure that operates under the FIFO (First In, First Out) principle. This means that the first element added to the queue will be the first one to be removed.

Think of it like a real-world queue of people waiting in line at a movie theater or supermarket checkout: the person who gets in line first is served first, and new people join the line at the very back.

---

Memory Layout & Implementations

A Queue can be implemented in several ways, each with unique characteristics:

1. Array-Based Implementation (Linear Queue)

Uses a static array with two index pointers: front (tracks the first element) and rear (tracks the last element).

• Pros: Fast O(1) operations, cache-friendly.
• Cons: Lacks space reuse! As elements are enqueued and dequeued, the pointers drift to the right. Once rear reaches the end of the array, the queue is considered "full", even if there are empty slots at the beginning due to dequeues.

2. Circular Queue (Array-Based)

Solves the pointer-drift problem of linear queues by conceptually wrapping the array into a ring. When rear or front reaches the end of the array, they wrap around to index 0 using modulo arithmetic:

nextIndex = (currentIndex + 1) % capacity

• Pros: Dynamic circular reuse of space, extremely efficient for fixed buffers.

3. Linked List-Based Implementation

Uses a dynamic linked list where front points to the head node and rear points to the tail node.

• Pros: Dynamically grows/shrinks as needed; never overflows.
• Cons: Memory overhead due to node pointers (O(N) extra memory for links).

---

Core Operations

Operation	Description	Time Complexity
Enqueue	Add an element to the rear of the queue	O(1)
Dequeue	Remove and return the element at the front	O(1)
Front / Peek	Inspect the front element without removing it	O(1)
IsEmpty	Check if the queue contains zero elements	O(1)
IsFull	Check if the queue has reached capacity	O(1)

---

Real-World Applications

Queues are ubiquitous in systems programming, concurrency, and network architecture:

• Operating System Scheduling: Tasks waiting for CPU execution time, disk access, or printer queues are managed using scheduling queues (e.g. Round Robin).
• Network Buffering: Routers and switches buffer incoming packets in queues before processing or forwarding them to maintain order.
• Breadth-First Search (BFS): Graph traversal algorithms use a queue to explore nodes level-by-level.
• Message Brokers: Platforms like RabbitMQ, Apache Kafka, or Amazon SQS use distributed queues to decouple microservices and manage async job distribution.
• Async Event Loops: JavaScript engines use event/callback queues to coordinate execution of asynchronous code.

---

Interview Tips 💡

1. Circular Wrap-around Check: If asked about fixed-size queues, always implement a Circular Queue to prove you know how to avoid wasting memory.
2. Boundary Checks: Guard carefully against Queue Underflow (dequeueing from an empty queue) and Queue Overflow (enqueueing to a full queue).
3. Queue using Stacks: Be prepared to solve the classic puzzle of implementing a Queue using two Stacks.