A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)? A. Both operations can be performed in O(1) time. B. At most one operation can be performed in O(1) time but the worst case time for the other operation will be Omega(n). C. The worst case time complexity for both operations will be Omega(n). D. Worst case time for at least one of the operations will be Omega(log n).

GATE 2016 · Programming and Data Structures · Queue · medium

Answer: Option A: Both ENQUEUE and DEQUEUE can be performed in O(1) time using a circular array implementation.

1. Analyse naive vs. efficient array implementation: A naive implementation where DEQUEUE shifts all elements left is O(n). But the question specifies the queue is implemented so that ENQUEUE and DEQUEUE are performed EFFICIENTLY. The standard efficient method is a circular array with FRONT and REAR pointers.
2. Verify O(1) for ENQUEUE: ENQUEUE places the new element at arr[REAR] and increments REAR circularly. This is exactly 2 operations regardless of how many elements are in the queue. Time = O(1).
3. Verify O(1) for DEQUEUE: DEQUEUE reads the element at arr[FRONT] and increments FRONT circularly. This is exactly 2 operations regardless of n. Time = O(1).
4. Select the correct option: Both operations are O(1). Option A states 'Both operations can be performed in O(1) time' — this is correct. Options B, C, D all claim at least one operation is Omega(n) or Omega(log n), which is incorrect for a circular array implementation.