Can you please explain your Algorithm to implement queue using stack in O(1) time?
On Oct 18, 1:43 pm, "juver++" <avpostni...@gmail.com> wrote: > The amortized time is O(1) for extracting and pushing elements from/in > the queue. > > On 18 ÏËÔ, 12:01, Mallesh Kavuluri <mallesh...@gmail.com> wrote: > > > > > @Juver > > > Simulating queue with Stack takes O(n) time. If it takes O(1) time, then > > your solution is correct. > > > If simulating Queue with stack takes O(n) time, then your solution > > complexity will be O(n) and not O(1). > > > 2010/10/16 juver++ <avpostni...@gmail.com> > > > > Suppose you have a stack data structure which has additional > > > operation findMin() - returns smallest element on the stack. > > > This can be easily updated in O(1) while pushing new element onto the > > > stack. > > > > It is known that queue DS can be simulated by using two stacks (here > > > we use stacks which have findMin routine). > > > From this point we are able to retrieve smallest element from the > > > queue in O(1). > > > > On 13 ÏËÔ, 22:22, malli <mallesh...@gmail.com> wrote: > > > > A queue data structure has functions enqueue(int x) ( inserts element > > > > in right end), dequeue() ( deletes element from left end) functions. > > > > These operations take O(1) time. Modify this queue data structure, so > > > > that šit supports findmin() which returns minimum element of stack in > > > > O(1) time. > > > > -- > > > 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.
