The Gateway to Computer Science Excellence

+37 votes

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) ?

- Both operations can be performed in $O(1)$ time.
- At most one operation can be performed in $O(1)$ time but the worst case time for the operation will be $\Omega (n)$.
- The worst case time complexity for both operations will be $\Omega (n)$.
- Worst case time complexity for both operations will be $\Omega (\log n)$

+8

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.

+1

Although, Circular queue implementation is memory efficient but as far as this question is concerned, answer is A in either case!

+1

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.

Please let me know if I missed something.

+1

Arqam Circular array/LL is generally used for queues.

Even if you use simple arrays, you'd still get $O(1)$ for both the queue operations. Because to enqueue, we need to increment the rear and insert. To dequeue, we need to delete the front, then increment it. Both are constant-time operations.

It can be easily visualised that in a non-circular array, the initial indices of the array will be wasted as and when we dequeue. That's not space efficient.

In any case, Be it Linked Lists or Arrays, we'd get $O(1)$ time for both the operations (given that we have a head and tail pointer)

0

@JashanArora how is space wasted when dequeue is performed in non-circular array? We can make the value in front node as NULL, then make head point to the second node. So no space would be wasted.

The reason why circular linked list is preferred over singly linked list is that we need two pointers (for front and rear) in singly linked list, but circular linked list needs only one pointer (which acts like rear).

Linked List [check Circularly linked vs. linearly linked part]

+20 votes

+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.

+3 votes

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.

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.

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

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

ans will remains same

0

we are not using pointer here, we are using mod function. suppose the size of array is 5, front is at index 0, and rear is at index 4. suppose after doing a deletion, front will shift to( present.index +1)mod(5) positon. similarly when we do insertion, rear will do same operation (present.index + 1)mod5, which will be equal to zero index.

+2 votes

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

https://www.sqa.org.uk/e-learning/ArrayDS02CD/page_14.htm

52,217 questions

59,907 answers

201,098 comments

118,144 users