Can we implement it using a single stack by writing a recursive reverse stack operation ?
On Tue, Mar 23, 2010 at 10:18 AM, Sundeep Singh <singh.sund...@gmail.com>wrote: > Thanks Dave, I didn't think about this... definitely better! > > Sundeep. > > > On Mon, Mar 22, 2010 at 9:08 PM, Dave <dave_and_da...@juno.com> wrote: > >> Better still. >> To enqueue: push onto stack A. >> For dequeuing: If stack B is empty, pop all items from stack A and >> push onto stack B. Then pop stack B. >> There is no need to push remaining items back to stack A. >> >> As every item passes through the queue, it is pushed onto stack A, >> then popped from stack A and pushed onto stack B, and finally popped >> from stack B. The time is roughly twice the time required for a direct >> implementation of a queue. >> >> There is room for a little optimization if both stacks are empty when >> enquing, as you can push the item directly onto stack B. Furthermore, >> when popping from stack A and pushing onto stack B, you don't need to >> push the last item popped, as it is the return value. >> >> Dave >> >> On Mar 22, 9:29 am, Sundeep Singh <singh.sund...@gmail.com> wrote: >> > Hey Brian, >> > >> > Better still, for inserting in queue, just keep pushing onto the stack >> A. >> > You need stack B only for dequeuing: for dequeuing, push all items into >> > stack B, pop as many as you want from stack B and then push back all >> > remaining items in stack A. >> > >> > Regards, >> > Sundeep. >> > >> > >> > >> > On Mon, Mar 22, 2010 at 6:56 PM, Brian <brianfo...@gmail.com> wrote: >> > > > How is it possible to implement a queue using a stack only? >> > >> > > Interesting, but tricky... You need two stacks as Prakhar stated... >> > > In general, if you have Stack A and Stack B, you should keep all the >> items >> > > in stack A and then use stack B for processing. >> > >> > > For example to insert an item: >> > > 1. Pop all the items from A and then push them into B (this should >> push >> > > the items into Stack B in reverse order) >> > > 2. Insert the new item into A >> > > 3. Pop all the items in B and push them back into A (again this will >> push >> > > them back into Stack B in reverse order) >> > >> > > Running time should be O(1)+O(2n), which is O(n) for larger values of >> n - >> > > which is not good... >> > >> > > To retrieve an item, pop the first item in stack A >> > >> > > Hope this helps - >> > > Regards >> > > B >> > >> > > On 3/22/2010 4:55 AM, Prakhar Jain wrote: >> > >> > > By a do u mean a single stack ? >> > > Otherwise if you use 2 its v simple >> > >> > > Best, >> > > Prakhar Jain >> > >http://web.iiit.ac.in/~prakharjain/<http://web.iiit.ac.in/%7Eprakharjain/> >> <http://web.iiit.ac.in/%7Eprakharjain/> >> > >> > > On Mon, Mar 22, 2010 at 12:56 AM, Pushpesh Gupta < >> pushpes...@gmail.com>wrote: >> > >> > >> How is it possible to implement a queue using a stack only? >> > >> > >> -- >> > >> You received this message because you are subscribed to the Google >> Groups >> > >> "Algorithm Geeks" group. >> > >> To post to this group, send email to algoge...@googlegroups.com. >> > >> To unsubscribe from this group, send email to >> > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> <algogeeks%2bunsubscr...@googlegroups.com> >> > >> . >> > >> For more options, visit this group at >> > >>http://groups.google.com/group/algogeeks?hl=en. >> > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups >> > > "Algorithm Geeks" group. >> > > To post to this group, send email to algoge...@googlegroups.com. >> > > To unsubscribe from this group, send email to >> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en. >> > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups >> > > "Algorithm Geeks" group. >> > > To post to this group, send email to algoge...@googlegroups.com. >> > > To unsubscribe from this group, send email to >> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> <algogeeks%2bunsubscr...@googlegroups.com> >> > > . >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - >> > >> > - Show quoted text - >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
