1 votes 1 votes $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 DS data-structures circular-queue + – srestha asked May 24, 2019 srestha 1.3k views answer comment Share Follow See all 22 Comments See all 22 22 Comments reply Satbir commented May 24, 2019 reply Follow Share 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 votes 0 votes Hirak commented May 24, 2019 i edited by Hirak May 24, 2019 reply Follow Share 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 votes 0 votes srestha commented May 24, 2019 reply Follow Share @Hirak Can u show ur implementation, of circular queue with stack?? 0 votes 0 votes Satbir commented May 24, 2019 reply Follow Share I didn't understood your explanation. In the link they have implemented circular queue using circular singly linked list 0 votes 0 votes Hirak commented May 24, 2019 reply Follow Share @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 votes 0 votes Hirak commented May 24, 2019 reply Follow Share @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 votes 0 votes Satbir commented May 24, 2019 reply Follow Share circular singly linked list is a singly linked list with one extra pointer right ? 0 votes 0 votes Hirak commented May 24, 2019 reply Follow Share @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 votes 0 votes Satbir commented May 24, 2019 reply Follow Share @Hirak leave stacks just give me an algo to implement circular queue using singly linked list without extra pointer. 0 votes 0 votes Hirak commented May 24, 2019 reply Follow Share @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 votes 0 votes Hirak commented May 24, 2019 reply Follow Share @Satbir https://www.google.com/search?client=firefox-b-d&biw=1366&bih=654&tbm=isch&sa=1&ei=cDDoXKK3Kdr1rQHd7a6YAQ&q=circular+queue+using+doubly+linked+list+in+c&oq=circular+queue+using+doubl&gs_l=img.1.0.0i24.461652.463668..464848...0.0..0.252.1518.0j1j6......0....1..gws-wiz-img.......35i39j0.YtasM6qOYJw see that all these implementations are basically circular link list.. 0 votes 0 votes Satbir commented May 24, 2019 reply Follow Share 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 votes 0 votes Hirak commented May 24, 2019 reply Follow Share 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 votes 0 votes srestha commented May 24, 2019 reply Follow Share not circular queue data structure means?? 0 votes 0 votes Hirak commented May 24, 2019 reply Follow Share rear node pointing to front or in other words rear coming just before the front.. 0 votes 0 votes Hirak commented May 24, 2019 reply Follow Share 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 votes 0 votes Satbir commented May 25, 2019 reply Follow Share 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 votes 0 votes srestha commented May 25, 2019 reply Follow Share that means how it works rt?? 0 votes 0 votes Satbir commented May 25, 2019 reply Follow Share yes 1 votes 1 votes Gupta g commented Sep 16, 2019 reply Follow Share Here in the question, It is not said that we can take any no of stacks. 0 votes 0 votes Satbir commented Sep 16, 2019 reply Follow Share Yes but we have to choose the most appropriate option from the given choices. 0 votes 0 votes `JEET commented Nov 19, 2019 i edited by srestha Nov 20, 2019 reply Follow Share @Satbir So stack is the final answer here, right? 0 votes 0 votes Please log in or register to add a comment.