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