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/> >>> > >>> > > 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> >>> > >> . >>> > >> 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]<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]<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.
