A queue is implemented using an array such that ENQUEUE and DEQUEUE operations…
2016
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\(Ω(n)\) - C.
The worst case time complexity for both operations will be
\(Ω(n)\) - D.
Worst case time complexity for both operations will be
\(Ω(logn)\)
Attempted by 752 students.
Show answer & explanation
Correct answer: A
Key idea: implement the array as a circular buffer with head and tail indices.
ENQUEUE: place the new item at the tail index, set tail = (tail + 1) mod capacity, and update the size/count.
DEQUEUE: remove the item at the head index, set head = (head + 1) mod capacity, and update the size/count.
Complexity: Both operations perform a constant number of simple steps (read/write and index updates), so each is O(1) time in the worst case for a fixed-size array.
Note: if you allow dynamic resizing when the array is full, ENQUEUE becomes amortized O(1) (occasional O(n) when resizing), while DEQUEUE remains O(1).
A video solution is available for this question — log in and enroll to watch it.