Here is code and explanation http://geeksforgeeks.org/?p=5009
On Sat, Apr 10, 2010 at 10:18 PM, Rohit Saraf <[email protected]>wrote: > hmm... that can always be done ! > > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > On Wed, Mar 24, 2010 at 6:24 PM, Dave <[email protected]> wrote: > >> Please post your results. I'd like to study your algorithm. >> >> On Mar 23, 11:15 pm, chitta koushik <[email protected]> >> wrote: >> > yeah i understand that ..... still wanted to attempt writing a recursive >> > reverse() stack operation. >> > >> > On Wed, Mar 24, 2010 at 9:21 AM, Rohit Saraf < >> [email protected]>wrote: >> > >> > >> > >> > > Even when you are writing a recursive function.. you are not using one >> > > stack. >> > > One stack is yours. Other used for recursion. >> > >> > > Making queue from a single stack <=> Making turing machine from CFG. >> > >> > > -Rohit >> > >> > > On Wed, Mar 24, 2010 at 9:18 AM, chitta koushik < >> > > [email protected]> wrote: >> > >> > >> 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 < >> [email protected]>wrote: >> > >> > >>> Thanks Dave, I didn't think about this... definitely better! >> > >> > >>> Sundeep. >> > >> > >>> On Mon, Mar 22, 2010 at 9:08 PM, Dave <[email protected]> >> 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 <[email protected]> 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 <[email protected]> >> 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/> >> > >>>> <http://web.iiit.ac.in/%7Eprakharjain/> >> > >> > >>>> > > On Mon, Mar 22, 2010 at 12:56 AM, Pushpesh Gupta < >> > >>>> [email protected]>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 >> [email protected]. >> > >>>> > >> To unsubscribe from this group, send email to >> > >>>> > >> [email protected]<algogeeks%[email protected]> >> <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 >> [email protected]. >> > >>>> > > To unsubscribe from this group, send email to >> > >>>> > > [email protected]<algogeeks%[email protected]> >> <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 >> [email protected]. >> > >>>> > > To unsubscribe from this group, send email to >> > >>>> > > [email protected]<algogeeks%[email protected]> >> <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 [email protected]. >> > >>>> To unsubscribe from this group, send email to >> > >>>> [email protected]<algogeeks%[email protected]> >> <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 [email protected]. >> > >>> To unsubscribe from this group, send email to >> > >>> [email protected]<algogeeks%[email protected]> >> <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 [email protected]. >> > >> To unsubscribe from this group, send email to >> > >> [email protected]<algogeeks%[email protected]> >> <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 [email protected]. >> > > To unsubscribe from this group, send email to >> > > [email protected]<algogeeks%[email protected]> >> <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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
