7k 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)$
in DS
edited | 7k views
+6
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
0
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.
0
Although, Circular queue implementation is memory efficient but as far as this question is concerned, answer is A in either case!
0
Am I the only one who is not able to understand why everyone is using a circular linked list for implementation when array is mentioned.

Please let me know if I missed something.

Answer (A) - Circular Queue Implementation

• Both operations can be performed in $O(1)$ time in Circular Queue implementation where Enqueue and Dequeue operation are done at last node. Single pointer is needed pointing to the last node. In the above figure the GRAY color part is the pointer pointing to the next node. With a single pointer pointing to the TAIL Node, we have access to the head node too (its next node is the head). Now

• ENQUEUE:
• Temp = TAIL -> Next;
• TAIL -> Next = NEWNODE(x);
• TAIL -> Next -> Next = Temp;
• TAIL = TAIL -> Next;
• DEQUEUE
• Temp = TAIL -> Next -> Next;
• Free(Tail -> Next);
• TAIL -> Next = Temp;
by Loyal (9.7k points)
edited by
0

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.

+5
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..
0
it may be B. as here it is not given any special case,so we cannot assume it to be  circular queue.
+20
Circular queue is not a special case.. it is the efficient implementation of a queue.. and in question it is mentioned operations performed efficiently..
+12
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
+31
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.
0

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

–2
@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
+2
It is not given that queue is circular.. Why u r assuming Circular Queue, although the answer is same with normal queue also
+6
why I'm seeing a circular linked list in this answer even though the question has mentioned an array to be used, I agree on the term efficient could mean circular here, but that can be achieved by the modular arithmetic on array and also we have two pointers FRONT AND REAR to delete and insert in Q (efficiently) both O(1).
0
It is clearly mentioned in the question that the queue is implemented using an array. Had it been mentioned that we have to choose efficient implementation of queue, then we would have taken the circular linked list. However using the array also we get O(1) time for insertion and deletion as we have FRONT and REAR pointers pointing to the appropriate indexes of array.
0
If the question wouldn't have asked about the efficiency or if we dont use circular linked list. What would have been the answer then in worst case scenario?

According to me in that case O(1) for Dequeue, since the elements are deleted from front end of the array,

and for enqueue it would be O(n), since we have the search until the last element and insert a new element..
0
How in circular link list with single pointer we can do both enqueue and dequeue in O(1) time?

0

@soumayan bandhu array implemented using circular queue here...circular queue perform addition & deletion O(1) at last node.

https://gateoverflow.in/118253/gate2017-2-13    this is similar question

0

What if i want to delete second last element from this queue? In that case time complexity will change to O(n)?

0
why O(n) time?
0

Those who are having doubt in why circular linked list is used rather than array, they can refer to the link below:

https://www.sqa.org.uk/e-learning/ArrayDS02CD/page_15.htm#ArrayImpQueue

Actually array is only used but your way of thinking is little bit different. by Active (3.8k points)
+1
I feel answer is simple as we can add and remove an element from an array in O(1) time by using appropriate index number. To implement queue we can maintain a negative counter K which will decrease everytime we enqueue an element. And to dequeue we can use absolute value of n-k where n is number of elements in an array.
0

@Srinath Jayachandran

In your implementation, if we use normal array then,

here for dequeue, it well take o(1) time and for enqueue, it will take o(n) time.

But if we use circular array instead of normal array, the time taken in both the case will be o(1).

Am I right ??

+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.
by Active (4.4k points)
0
@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
+2
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
+1 vote
Answer is A please refer this link I think it is best explanation I have found so far

https://www.sqa.org.uk/e-learning/ArrayDS02CD/page_14.htm
by Active (1.5k points)