You implement a queue using a plain array: enqueue adds to the end, and dequeue removes from the front by shifting all remaining elements left. What is the time complexity of dequeue?
AO(1), because you are only accessing the first element
BO(log n), because the shift operation uses binary search
CO(n), because shifting all remaining elements requires touching each one
DO(1) amortized, because shifts are rare in practice
Shifting all remaining elements after removing the front element requires touching every remaining element — that's O(n). This makes the naive array queue inefficient for large queues or frequent dequeue operations. The fix is a circular buffer, which uses two index pointers that advance without ever shifting elements, achieving O(1) dequeue. Python's collections.deque similarly provides O(1) pops from both ends.
Question 2 Multiple Choice
A circular buffer has capacity 5 and holds [_, A, B, C, _] with front=1 and rear=4. After one enqueue (D) and two dequeues, what are the new front and rear indices?
Afront=3, rear=0 (rear wrapped around using modular arithmetic)
Bfront=1, rear=5 (rear advanced past the end)
Cfront=3, rear=5 (both advanced without wrapping)
Dfront=0, rear=4 (elements were shifted to fill the gap)
After enqueueing D: rear advances to index 4, placing D there, then rear becomes (4+1)%5 = 0, wrapping around. After two dequeues: front advances from 1 to 2 (removing A), then to 3 (removing B). Result: front=3, rear=0. No elements shifted — both indices simply advance with modular arithmetic. This is the core efficiency of the circular buffer: O(1) operations with no element movement.
Question 3 True / False
A queue and a stack differ primarily in which end elements are added to — both structures remove elements from the same (front) end.
TTrue
FFalse
Answer: False
Stacks use LIFO (last-in, first-out): elements are added and removed from the same end (the top). Queues use FIFO (first-in, first-out): elements are added to the back and removed from the front. They enforce fundamentally different orderings. A stack reverses insertion order; a queue preserves it. This distinction is why stacks work for depth-first search and function call tracking, while queues work for breadth-first search and scheduling.
Question 4 True / False
Using a linked list with both head and tail pointers to implement a queue allows O(1) enqueue and O(1) dequeue with no fixed-capacity limitation.
TTrue
FFalse
Answer: True
With both head and tail pointers: enqueue appends a new node at the tail (update the tail pointer — O(1)), and dequeue removes the node at the head (update the head pointer — O(1)). No shifting is ever needed. Unlike a circular buffer, a linked-list queue has no fixed capacity — it grows dynamically. The tradeoff is extra memory per node for the pointer storage, but the O(1) performance guarantee holds.
Question 5 Short Answer
Why is a circular buffer the preferred array-based implementation of a queue, and what problem does it solve over a naive array approach?
Think about your answer, then reveal below.
Model answer: A naive array queue makes dequeue O(n) because removing the front element requires shifting all remaining elements left. A circular buffer solves this by maintaining two indices — front and rear — that advance through the array using modular arithmetic (wrapping from the last index back to 0). Enqueue places a new element at rear and advances rear; dequeue reads from front and advances front. Neither operation touches any other element, so both are O(1). The array's physical positions are reused in a cycle, hence 'circular.'
The key insight is that you don't need elements to be at physical position 0 to be logically 'first' — you just need a pointer to wherever the front currently is. By separating the logical front from the physical array position, you eliminate all shifting and achieve constant-time operations at the cost of a fixed capacity.