Please post your results. I'd like to study your algorithm. On Mar 23, 11:15 pm, chitta koushik <koushik.infin...@gmail.com> 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 > <rohit.kumar.sa...@gmail.com>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 < > > koushik.infin...@gmail.com> 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 > >> <singh.sund...@gmail.com>wrote: > > >>> 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<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> > > . > > 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.
