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) ?
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)
@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]
The answer must be A).
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 ??