edited by
23,133 views
61 votes
61 votes

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

  1. Both operations can be performed in $O(1)$ time.
  2. At most one operation can be performed in $O(1)$ time but the worst case time for the operation will be $\Omega (n)$.
  3. The worst case time complexity for both operations will be $\Omega (n)$.
  4. Worst case time complexity for both operations will be $\Omega (\log n)$
edited by

4 Answers

Best answer
21 votes
21 votes

Consider a normal array implementation of a queue. We’ll have $2$ pointers $\text{Front}$ and $\text{Rear}$ where $\text{Front}$ points to the first element of the queue and $\text{Rear}$ points to the next free space. When queue is full $\text{Rear}$ points to $\text{NULL}.$

The below figure depicts the Queue full condition and then a $\text{DEQUEUE}$ is performed which removes element $4.$ In the second part of the figure, all elements are shifted by one position or else we won’t be able to make use of the free space for the next element to be inserted. So, this means $\Theta(n)$ operations for $\text{DEQUEUE}$ where as $\text{ENQUEUE}$ can be done in $O(1).$ 

But we can in fact do both $\text{ENQUEUE}$ and $\text{DEQUEUE}$ operations in $O(1)$ and fully utlizie the array space by smartly using the $\text{Front}$ and $\text{Rear}$ pointers as shown in $\text{DEQUEUE}_{\text{opt}}.$ If $\text{MAX}$ denote the total size of the array, here,

  • for $\text{ENQUEUE}$
    • $\text{Rear} = (\text{Rear} + 1) \mod \text{MAX}$
  • for $\text{DEQUEUE}$
    • $\text{Front} = (\text{Front} + 1) \mod \text{MAX}$
  • Condition for $\text{QUEUE}$ Empty
    • $\text{Front} == \text{NULL}$ (Whenever after a $\text{DEQUEUE}$ operation $\text{Front}$ becomes equal to $\text{Rear}$ it means Queue is now empty and we make $\text{Front} = \text{NULL}$ to mark this condition as $\text{Rear} = \text{Front}$ is the condition we use for checking if $\text{QUEUE}$ is full
  • Condition for $\text{QUEUE}$ Full
    • $\text{Rear} == \text{NULL}$

So, correct answer: A.

selected by
26 votes
26 votes

The answer must be A).

edited by
6 votes
6 votes
how can you take circular queue, in ques it is not given to implement queue efficiently.in ques given is that ENQUEUE and DEQUEUE operations are performed efficiently.

to implement any data structure array is best but size is fixed.bcoz enqueue and dequeue both take O(1) in worst case.

so ans should be A.
Answer:

Related questions