search
Log In
1 vote
311 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 311 views
0

1. Implementation of Circular Queue

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

https://www.geeksforgeeks.org/circular-queue-set-2-circular-linked-list-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

Head = Null (head being our only pointer)

assign first node to head

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

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

I suggest this link-->

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?

Please log in or register to answer this question.

Related questions

1 vote
2 answers
1
701 views
The initial configuration of circular queue as follows What is status of states of queue contents after the following sequence of steps enqueue x dequeue enqueue y dequeue dequeue a)x,y,____,_____,_____ b)x,___,y,____,____ c)____,_____,x,y,____ d)_____,x,y,_____,_____
asked Oct 29, 2017 in DS srestha 701 views
0 votes
1 answer
2
300 views asked Jan 30, 2017 in DS monty 300 views
0 votes
0 answers
3
301 views
Doubt: dequeue really deletes the element or just moves the pointer? I'm not getting the answer.
asked Jan 21, 2017 in DS target2017 301 views
0 votes
1 answer
4
521 views
#DS I have this confusion in concluding the overflow condition of a circular Queue i.e. when the circular queue will be considered full. As per the text i have, it says a circular queue is full when: Front=0 and Rear=MAX-1 ; which seems quite straight forward. eg: The queue [10,5, ... is shouldn't the overflow condition of a circular Queue be: if((Front==0 && Rear==MAX-1) || (Rear==Front-1)) ???
asked Oct 24, 2017 in Programming nick17india 521 views
...