if two stacks then possible otherwise i dont think so On Mon, Apr 12, 2010 at 11:39 PM, Dheeraj Jain <dheerajj...@gmail.com>wrote:
> Here is code and explanation http://geeksforgeeks.org/?p=5009 > > > On Sat, Apr 10, 2010 at 10:18 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com > > 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 <dave_and_da...@juno.com> wrote: >> >>> 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/> >>> > >>>> <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> >>> > >>>> <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. >>> > >>> > >>>> > > -- >>> > >>>> > > 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> >>> > >>>> <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> >>> <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. >>> > >>> > >> -- >>> > >> 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> >>> <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. > -- Ashish Mishra http://ashishmishra.weebly.com/ -- 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.
