GATE CSE
First time here? Checkout the FAQ!
x
+8 votes
1.6k views

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)$
asked in DS by Boss (8.9k points)   | 1.6k views
A is the correct and becoz it is given efficient implementation is done so in case of circular queue they Can be implemented o(1) time
don't u people think B is the correct answer as it is mentioned specifically array, not circular array and efficiently means for every dequeue, elements have to be shifted one position to their leftside.

2 Answers

+21 votes
Best answer
answered by Boss (8.7k points)  
edited by

A Circular queue wont allow both operations to be perfomed in O(1) time when the complete array is full. (They never mentioned that the array is of fixed size) You will have to use the algorithm where the array size is doubled when no more space exists. To do this you will have to copy all the elements in the array into another array, so O(n). Thus Option A fails and thus seems wrong, in the worst case.

But it is also not given that we need to use the algorithm you mentioned.. We cannot assume anything which is not given in GATE. we need to stick with the question.. only.. if the array becomes full.. in general implementation we check and print error.. This is what i learnt from Horowitz & Sahani.. and Cormen..
it may be B. as here it is not given any special case,so we cannot assume it to be  circular queue.
Circular queue is not a special case.. it is the efficient implementation of a queue.. and in question it is mentioned operations performed efficiently..
Array is static contiguous memory allocation. But here array is implementing queue. and it can be performed Enqueue() and Dequeue() operations. So, there must be a front and rear pointer in the array. So, Front do deletion in O(1) time and Rear do insertion in O(1) time. right?

But not getting how it could be implemented as circular queue
In normal queue implementation, as we go on deleting elements, the front pointer keeps on moving forward, hence decreasing the size of array(because it is statically allocated as you said). Now this is not desirable. To restore full capacity of the queue, we may need to shift all the elements to the left with appropriate amount, which can take O(n) time in an array.
To prevent this, we can assume the queue wraps around. the modification is easy to implement using modular arithmetic.Now the size of queue remains n-1 throughout whole operation of the queue, making it efficient.

If efficient word were not there in question,then what will be the answer?

@ajit then does't make any sense but for ur doubt it will take O(n) bcz we need to be swap 'n-1' element to get empty sapce for one elemnt  .in it specially they want to test us for circular queue
+5 votes

The answer must be A).

 

answered by Loyal (3.3k points)  
Answer:

Related questions

Top Users Feb 2017
  1. Arjun

    5386 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2240 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,863 questions
26,022 answers
59,696 comments
22,133 users