The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
2.8k 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 (9.2k points) | 2.8k 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.

3 Answers

+26 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 (9.2k 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
It is not given that queue is circular.. Why u r assuming Circular Queue, although the answer is same with normal queue also
+10 votes

The answer must be A).

 

answered by Loyal (3.8k points)
+1 vote
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.
answered by Boss (5.8k points)
@rajoramanoj  

to perform enqueue and dequeue efficiently means  (here) .... implementation  of queue using an array  efficiently.but to implement  circular  queue at least 1 pointer is needed  . and how will we implement pointer here. . that is the question  .. so if u have some idea then pls do share
if it is given in the ques to implement queue efficiently then we go with circular queue bcoz in linear queue eventhough space is available we can not store one more element further bcoz rear reached rightmost place and it cannot go back.

ans will remains same
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,017 questions
36,844 answers
91,378 comments
34,721 users