Queue: FIFO and Capacity

A queue stores elements in a FIFO manner: the first inserted element is the first to leave the structure. enqueue (or offer) adds to the back, while dequeue (or poll) removes from the front.

Example sequence: enqueue(A), enqueue(B), dequeue returns A, dequeue returns B.

With limited capacity (circular buffer), enqueue can fail when the buffer is full. Empty dequeue is the symmetrical error case.

Queues model print jobs, network packets, and breadth-first search in graphs.

Queue from two stacks: Implement Queue using Stacks [1].

$$i \equiv (h+k) \pmod{C}$$

Where used

Job queues, message brokers (Kafka/RabbitMQ idea), request buffers in front of workers, print spools, BFS. Limited capacity models backpressure: a full queue means rejecting or blocking load, not idly filling memory.

Depth

A FIFO storage maintains the order of arrival. A circular buffer uses a fixed array cyclically, so removals from the front do not shift remaining elements. Two indices typically mark the write and read positions.

If both indices are equal, the buffer can be either empty or full. This ambiguity is resolved by a separate counter, an additional state bit, or by intentionally leaving an unused space. The chosen variant determines the actually usable capacity.

In constrained memory, the overflow strategy must be part of the contract. Blocking, discarding the new element, and overwriting the oldest element have very different implications in messaging systems.

Difficulty levels

1. Track the read and write index of a circular buffer.
2. Encode empty and full state without ambiguity.
3. Justify an overflow strategy for a specific system.

Pitfalls

Modulo arithmetic eliminates shifting but not state ambiguity. Additionally, an array length of k is only usable for k - 1 elements when using the free space method.