The GATE Grind

GATE 2016 CS – Question 20

Programming and Data Structures · Stacks and Queues · 1 mark · Multiple choice

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)?

  1. Both operations can be performed in $O(1)$ time
  2. At most one operation can be performed in $O(1)$ time but the worst case time for the other operation will be $\Omega(n)$
  3. The worst case time complexity for both operations will be $\Omega(n)$
  4. Worst case time complexity for both operations will be $\Omega(\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Both operations can be performed in $O(1)$ time

Explanation

Using the array as a circular buffer with a head index and a tail index, both enqueue and dequeue just update an index and one slot, so each takes constant time.