COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
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 operations will be (n)
|
|
|
The worst case time complexity for both operations will be Ω(n)
|
|
|
Worst case time complexity for both operations will be Ω(log n)
|
Detailed explanation-1: -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)? Correct answer is option ‘A’.
Detailed explanation-2: -Similarly, whenever there will be one single element, F will be equal to R, that is, F and R will point to the same node. And F and R will point to NULL only when an empty circular queue is created. If a single element is enqueued and dequeued, it (F and R) can never point to NULL.
Detailed explanation-3: -Overall worst case time complexity of implementation of queue using array is O(N).
Detailed explanation-4: -But if we consider the circular array implementation of a queue, in this case, both enqueue and dequeue can be performed in O(1) time.
Detailed explanation-5: -Dequeuing has O(1) worst-case time complexity. Dequeuing from a static array where elements are shifted to the front has O(n) worst-case time complexity. With circular queues, enqueuing and dequeuing have worst-case time complexity of O(1).