Queues

FIFO · Operations · Implementations

1:00

How queues enforce fairness through FIFO ordering, the circular-array and linked-list implementations that make all operations O(1), and how queues power OS scheduling and breadth-first search.

By the end, you can

Explain FIFO and contrast it with LIFO (stack).
Trace enqueue, dequeue, and peek on a queue, identifying the front and rear at each step.
Implement enqueue and dequeue with a circular array, calculating the new pointer with `% SIZE`.
Explain why a plain array makes dequeue O(n) and how the circular array restores O(1).
Describe the full/empty ambiguity in a ring buffer and two standard ways to resolve it.
Compare circular-array and linked-list implementations on capacity, cache performance, and pointer overhead.
State the time complexity of all three queue operations and the space complexity.
Explain overflow and underflow and what a correct implementation does in each case.
Trace BFS on a small graph using a queue, listing the visit order level by level.
Distinguish a priority queue from a plain queue and name the data structure typically used to implement it.
Describe what a deque is and how it generalises both stacks and queues.

Up next in Linear Data Structures