GATE CS 2016 Set 1 Q.20 (CS Q.10): Stacks and Queues

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

Both operations can be performed in $O(1)$ time

At most one operation can be performed in $O(1)$ time but the worst case time for the other operation will be $\Omega(n)$

The worst case time complexity for both operations will be $\Omega(n)$

Worst case time complexity for both operations will be $\Omega(\log n)$

Official answer and solution

Official answer: A
From: Official GATE 2016 answer key

Solution

Analyze the time complexity of queue operations implemented using a circular array.

A standard efficient array-based queue uses a circular buffer with two integer pointers/indices:

front: points to the head element to be dequeued.
rear: points to the tail location where the next element will be enqueued.

Operation execution:

ENQUEUE: Inserts an element at array[rear] and updates rear = (rear + 1) % capacity. This involves simple array indexing and arithmetic, running in $O(1)$ worst-case time.
DEQUEUE: Retrieves array[front] and updates front = (front + 1) % capacity. This also takes $O(1)$ worst-case time.

Neither operation requires shifting any elements. Thus, both operations are performed in $O(1)$ time.

Final answer

Common trap

Assuming a linear (non-circular) array where DEQUEUE requires shifting all $n$ remaining elements to the left taking $\Omega(n)$ time.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 20 of 65, printed as CS Q.10
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source