+1 vote
228 views

$1)$How circular queue can be implemented?

$2)$ For which data structure circular queue cannot be implemented?

$(A)$Array $(B)$ Singly Linked List  $(C)$ Doubly Linked List  $(D)$ Stack

in DS | 228 views
0

1. Implementation of Circular Queue

https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/

2. It can be implemented using array,circular linked list and circular doubly linked list.

We use circular queue to reuse the memory space. So implementing it using multiple stacks makes no sense as it will waste memory.

So for 2 option D is correct.

0
Circular queue with stack can definitely be implemented.. Moreover the space will also be constant i.e. O(1), since 2 stacks of the same size that of queue will be taken. The implementation procedure for circular queue using stack will exactly be same as normal queue using stack.

.
0

@Hirak

Can u show ur implementation, of circular queue with stack??

0

I didn't understood your explanation. In the link they have implemented circular queue using circular singly linked list

0

@srestha

Will it be any different from normal queue using stacks?

Circular queue is used for space utilization to prevent compaction, ordinary queue using stacks serves the same purpose as the element next to the poped element is pushed at the bottom of the stack again thus freeing up a space and gauranting compaction.

0

@Satbir

ya but in the options circular link list is not mentioned..moreover all the implementations are possible, but for single link list one extra pointer is must..

0
circular singly linked list is a singly linked list with one extra pointer right ?
0

@Satbir

For singly link list without extra pointer it is also satisfying as popping from head and shifting it...

So, all the options should be correct.. I didn't understand why did you say that stack implementation is not possible.

0

@Hirak leave stacks just give me an algo to implement circular queue using singly linked list without extra pointer.

0

@Satbir

and travel to the last using doing next=current--> next and insert there. (we can easily insert this way)

if we want to delete, we can make temp=head and and head=head-> next, this will give pop..

the above code performs the same function that we need to do for a simple queue using link list, because the purpose of circular queue is for space utilization, and here we are doing the same, but the main thing is that the circular queue's typical data structure can never be maintained without a circular link list. So see that whatever implementations are there be it using single link list or doubly link list, to preserve that same data structure a circular link list is must.. even the links that u have provided doesn't even consider singly link list.

But the fact is that same purpose of circular queue can be satisfied by the naive approach of a singly link list.

0
0

For singly link list without extra pointer it is also satisfying as popping from head and shifting it

so you are trying to say that we can make circular queue with single linked list without using extra pointer right ?

and you have given proof for that

0
purpose of circular queue can be achieved....

not circular queue data structure itself..and without using extra pointers means like pointers provided to any other internal node or rear node
0

not circular queue data structure

means??

0
rear node pointing to front or in other words rear coming just before the front..
0

https://www.quora.com/What-is-the-need-for-a-circular-queue

The problem state in the first answer regarding normal queue can be overcome by using compaction but that is an overhead, so circular queue data structure was proposed..

Now aren't we preventing it even while implementing normal queue using link list or doubly link list..??

The purpose of circular queue is even satisfied there..but not the data structure.!

0

The purpose of circular queue is even satisfied there..but not the data structure.!

Question is asking for circular queue data structure not its purpose.

0
that means how it works

rt??
+1
yes
0
Here in the question, It is not said that we can take any no of stacks.
0
Yes but we have to choose the most appropriate option from the given choices.
0

@Satbir

So stack is the final answer here, right?