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)?
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)$
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.
More Stacks and Queues questions
GATE 2016 CS (CS1) Q51– Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns…
GATE 2014 CS (CS2) Q51– A stack supports REVERSE (reverses all elements) in addition to PUSH and POP. Which is…
GATE 2012 CS Q45– A circular queue stores at most n−1 items in an n-element array. REAR and FRONT index…
GATE 2013 CS Q54– Along with Enqueue/Dequeue, a queue supports MultiDequeue(Q), which sets m=k and…