Queue

Intuition

A queue is the line at a coffee shop. New customers join at the back, the next customer served is always the one at the front. The first one in is the first one out — FIFO, First-In-First-Out.

Anywhere "fairness" or "processing order matters" shows up — task schedulers, message buffers, breadth-first search, print spoolers — a queue is the natural fit. The discipline is what makes the whole system predictable: a job that arrived earlier won't be passed by a job that arrived later.

How It Works

A queue exposes two core operations on opposite ends:

• enqueue(val) — add val at the back. If the queue has a fixed capacity and is already full, raise an overflow error.
• dequeue() — remove and return the value at the front. If the queue is empty, raise an underflow error.

This two-end discipline is the entire idea: enqueue at one end, dequeue at the other. A stack uses one end for both — that's what distinguishes the two structures.

The displayed code uses a Python list with append (enqueue) and pop(0) (dequeue). That's pedagogically clear but pop(0) is actually O(n) — every other element shifts left by one. Production queues use a circular buffer (head and tail indices wrap around a fixed array) or a deque (Python's collections.deque) to make both ends O(1). The animation does not visualize that optimization; treat the displayed code as the conceptual queue, not the production-grade one.

Step By Step

Starting with an empty queue of capacity 5:

1. enqueue(3) → queue is [3]. Cell appears on the right (back).
2. enqueue(7) → queue is [3, 7]. 7 lands to the right of 3.
3. enqueue(1) → queue is [3, 7, 1].
4. dequeue() → returns 3. Queue is [7, 1]. The leftmost cell lifts off; the rest slide one slot left to fill the gap.
5. enqueue(9) → queue is [7, 1, 9]. 9 lands on the right.
6. dequeue() → returns 7. Queue is [1, 9].
7. dequeue() until empty → returns 1, then 9. One more dequeue() triggers underflow.

In the visualization, the queue is drawn horizontally with a "front mouth" on the left (where dequeue exits) and an "open back" on the right (where enqueue enters). The right-anchor header tracks size = N and front = arr[0] = V.

Complexity

For the production circular-buffer / deque implementation:

For the displayed list-based implementation, dequeue is O(n) due to the shift. The conceptual contract is identical; the implementation choice changes the constant factor.

Total space: O(n) where n is the number of elements currently queued.

Edge Cases

• Enqueue to a full queue — raises overflow. Real queues are often unbounded; capacity caps are usually a deliberate back-pressure mechanism (bounded message channels, fixed-size ring buffers).
• Dequeue from an empty queue — raises underflow. Calling code should guard with is_empty() or catch the exception. Some designs return None / a sentinel instead — the choice depends on whether "empty" is an expected control-flow signal or a bug.
• Single-element queue — enqueue then dequeue returns the same value; the front and back point at the same cell.
• Repeated dequeue without enqueue — drains in arrival order. Same FIFO discipline; nothing special.

Common Mistakes

• Mixing the ends. Enqueueing at the front and dequeueing at the back turns a queue into a queue-in-reverse — still FIFO if you swap both, but if you only swap one you get a stack (LIFO). Always enqueue at one end and dequeue at the other end.
• Using pop(0) in production code. Cheap mistake to write, expensive to run. Python's collections.deque is the safe default for any queue larger than a handful of elements.
• Forgetting that priority queues are not queues. A priority queue serves the highest-priority element next, not the earliest. Internally it's a heap, not a FIFO. Same word, different data structure.
• Treating queue and deque as interchangeable. A deque (double- ended queue) supports push/pop at both ends. Using a deque as a FIFO is fine; using a FIFO when you actually need both ends is not.
• Implementing a queue with two stacks but forgetting to drain. The classic interview answer: two stacks in and out. Push to in; pop from out, refilling out from in only when out is empty. The amortized cost is O(1) — but only if you respect the "refill only when empty" condition. Refilling on every pop makes it O(n).