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