GATE CSE
First time here? Checkout the FAQ!
x
+8 votes
2k 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)   | 2k 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

+22 votes
Best answer

Answer A - Circular Queue Implementation

  • Both operations can be performed in O(1) time in Circular Queue implimentation where Enqueue and Dequeue operation are done at last node. Single pointer needed at last node.

Reffer : http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html

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.7k points)  
Answer:

Related questions



Top Users Jul 2017
  1. Bikram

    3782 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1832 Points

  4. joshi_nitish

    1494 Points

  5. Arnab Bhadra

    1096 Points

  6. Arjun

    1054 Points

  7. Hemant Parihar

    1050 Points

  8. Shubhanshu

    972 Points

  9. Ahwan

    876 Points

  10. akash.dinkar12

    642 Points


23,953 questions
30,895 answers
70,108 comments
29,273 users