Project ForgeData Structures
Arrays & Linked Lists
GATE 2016
Easy
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
- BAt most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
- CThe worst case time complexity for both operations will be Ω(n)
- DWorst case time complexity for both operations will be Ω(log n)
Explanation
Using a circular array with separate front and rear index pointers (wrapping around with modulo arithmetic), both ENQUEUE (write at rear, advance rear) and DEQUEUE (read at front, advance front) are simple O(1) constant-time index updates — no shifting of elements is required.
Source: GATE CS 2016 (Session 1 / Set A) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.