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/> > > > 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> > >> . > >> 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. > > > -- > > 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.- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
