Questions: Queue ADT: Circular Array and Linked-List Implementations

Question 1

A naive array-based queue always uses index 0 as the front and shifts all remaining elements left on every dequeue. After 10,000 enqueue-then-dequeue operations on a queue that never holds more than 5 elements at a time, what is the overall time complexity behavior?

• A. O(n) per dequeue due to shifting, where n is the current queue size — even if the queue is small, each shift still occurs
• B. O(1) per operation because the queue size stays bounded by 5
• C. O(log n) because the array shrinks as elements are removed
• D. O(n) per enqueue only; dequeue is always O(1)

Answer: (A)

In a naive implementation, dequeue from index 0 requires shifting every remaining element one position to the left. If the queue holds k elements, that is k shifts — O(k) work. Even if k stays small (like 5), the cost is still O(n) in the general case. The circular array eliminates this by moving a pointer instead of moving data.

Question 2

A circular array queue has capacity 5. The front index is 3 and the rear index is 1 (elements wrap around the array end). What index should the next enqueue write to, and how is it computed?

• A. Index 2, computed as (rear + 1) % capacity = (1 + 1) % 5
• B. Index 2, but only if there is a gap between rear and front — otherwise the queue must resize first
• C. Index 6, by extending the array past its current end
• D. Index 0, because rear has passed the midpoint of the array

Answer: (A)

The circular array uses modular arithmetic: next_rear = (rear + 1) % capacity. This wraps the index back to the beginning of the array when it reaches the end, treating the array as a ring. The key insight is that 'where the array ends' is arbitrary — the logical structure is circular, not linear.

Question 3

In a circular array queue, both enqueue and dequeue run in O(1) time.

• T. True
• F. False

Answer: True

True. Neither operation moves existing elements. Enqueue writes to the rear index and increments it (with wrap-around). Dequeue reads from the front index and increments it. All work is constant regardless of queue size — which is exactly the improvement over the naive shifting approach.

Question 4

A linked-list queue is typically more efficient than a circular array queue because it avoids the need for resizing.

• T. True
• F. False

Answer: False

False. The comparison is more nuanced. A linked-list queue avoids resizing but incurs per-element heap allocation overhead and stores data in non-contiguous memory, hurting cache performance. A circular array keeps all elements contiguous in memory, which is cache-friendly and avoids allocation costs — at the price of a fixed capacity or occasional resizing. Neither is universally superior.

Question 5

Why does a circular array solve the performance problem of a naive array-based queue, and what is the single conceptual shift that makes it work?

Model answer: A naive queue dequeues from index 0 and must shift every remaining element left — O(n) work. The circular array replaces 'shift the data' with 'move a pointer': front and rear are just indices that advance with modular arithmetic, (index + 1) % capacity, so they wrap around to the beginning when they reach the end. The conceptual shift is treating the array as a ring rather than a line — there is no fixed start or end, just two moving pointers. Both enqueue and dequeue become O(1) because no elements are ever moved.

The modular arithmetic is the mechanical implementation of the circular idea. Understanding this derivation (not just memorizing the formula) is what lets you handle the full vs. empty ambiguity and adapt the approach to related structures like deques.