Queue

A queue is a linear data structure that adds elements at the back and removes them from the front, so the first value in is the first value out — FIFO. enqueue appends to one end, dequeue takes from the other, and that two-end discipline is the entire contract: arrival order is service order, always.

You already run this data structure every morning. The coffee line takes new customers at the back and serves whoever is at the front, and nobody negotiates. That single rule — join at one end, leave at the other — is why schedulers, message buffers, print spoolers, and breadth-first search all reach for a queue: work that arrived earlier never gets passed by work that arrived later.

How a Queue Works

Two operations, opposite ends. enqueue(val) appends val at the back. dequeue() removes and returns whatever sits at the front. The animated code is a bounded queue: if you enqueue when the queue already holds max elements, it raises Queue Full (overflow); dequeue an empty queue and it raises Queue Empty (underflow). Both guards are real lines in the displayed class — a rejected enqueue never modifies the queue.

Compare the stack, which pushes and pops at the same end. Swap one end of a queue and you have built a stack by accident; the opposite-ends rule is the whole difference between FIFO and LIFO.

One honesty note about cost. The displayed Python class stores elements in a plain list and dequeues with pop(0), which shifts every remaining element left by one — that is O(n), not O(1). The contract is right; the implementation is the teaching version. Production queues use a circular buffer (head and tail indices wrapping a fixed array) or collections.deque, which serve both ends in O(1).

Queue Operations Step by Step

The lesson starts from the default state: an empty queue with capacity 8. Run this sequence from the Inputs panel.

1. enqueue(3) — 3 joins the back. Queue is [3]; front and back are the same lone customer.
2. enqueue(7) — 7 lines up behind 3. Queue is [3, 7].
3. enqueue(1) — queue is [3, 7, 1].
4. dequeue() — the front leaves first, so it returns 3, the value that arrived first. Queue is [7, 1].
5. dequeue() — returns 7. Queue is [1].
6. dequeue() — returns 1. Queue is [] again.

Once those six operations finish, the queue is empty. Try one more dequeue() yourself: it raises Queue Empty and changes nothing — the underflow guard, which the lesson handles but the seeded demo stops short of.

Notice the departures — 3, then 7, then 1, the precise arrival order. That is the guarantee, not a coincidence of this trace.

On the canvas, the same trace plays out with a FRONT arrow pinned under the first cell and a BACK arrow tracking the last. Each dequeue slides the front cell off to the left while the survivors shift one slot over, and the header's running size, front, and back readouts update with every beat — a visual echo of the states you just walked on paper.

Time and Space Complexity

The conceptual queue promises O(1) at both ends; the time complexity you actually get depends on the storage underneath.

Space is O(n) for the n elements currently waiting, in either version.

Edge Cases

• Enqueue when full — overflow. The bound is genuinely in the displayed code (max is checked, then Queue Full is raised); bounded queues are a deliberate back-pressure tool. The capacity slider stopping at 10 is purely a canvas-width limit of the visualization, not a property of queues.
• Dequeue when empty — underflow. Guard with an emptiness check or catch the exception; some APIs return a sentinel instead, depending on whether "empty" is expected control flow or a bug.
• Single element — front and back point at the same cell; one dequeue returns it and empties the queue.
• Drain without refill — repeated dequeues replay arrival order until underflow.

Common Mistakes

• pop(0) in production. Cheap to type, O(n) to run. Reach for collections.deque once the queue outgrows a toy.
• Mixing the ends. Dequeue from the back and you have silently built a stack; the FIFO guarantee evaporates without an error message.
• Assuming a priority queue is a queue. It serves the highest priority next, not the earliest arrival — internally a heap, FIFO in name only.
• Two-stacks queue, refilled too eagerly. The classic interview construction is amortized O(1) only if you refill the out-stack when it is empty; refilling on every pop costs O(n).