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