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

2 Answers

+21 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 May 2017
  1. akash.dinkar12

    3338 Points

  2. pawan kumarln

    2108 Points

  3. Bikram

    1922 Points

  4. sh!va

    1682 Points

  5. Arjun

    1614 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1208 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1018 Points

  10. Arnab Bhadra

    812 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1008 Points

  2. pawan kumarln

    734 Points

  3. Arnab Bhadra

    726 Points

  4. Arjun

    342 Points

  5. bharti

    328 Points


22,893 questions
29,196 answers
65,302 comments
27,695 users