@sourav, As Juvier++ pointed out, it's an **amortized** O(n) algorithm. That's because each element can be at most popped twice.
Thanks Yq On Mon, Jan 3, 2011 at 11:20 AM, sourav <souravs...@gmail.com> wrote: > @yq Zhang, > > To pop if you are going to "pop all from first stack and push into the > second stack", then does your operation remain "constant time"? Please > note that we need constant time implementation for the 3 functions > pop_front, push_rear and get_min(). Goint by your approach, not all of > them are constant time. > > Thanks, > Sourav > > On Jan 3, 9:44 pm, yq Zhang <zhangyunq...@gmail.com> wrote: > > Push into one stack. When pop first pop all from the first stack and push > > into the second stack. Then pop from the second stack > > On Jan 3, 2011 7:42 AM, "MOHIT ...." <mohit...@gmail.com> wrote: > > > > > if only two stack are used but how pop_front is get? > > > > > suppose if element comes in order > > > > > 12 15 4 3 7 20 > > > then in min queue > > > 1. 12 (12) > > > 2. 12 12 (12,15) > > > 3. 12 12 4 (12,15,4) > > > 4.12 12 4 3 (12,15,4,3) > > > 5.12 12 4 3 3 (12,15,4,3,7) > > > 6.12 12 4 3 3 3 (12,15,4,3,20) > > > > > we can get min in constant by pop of stack but how pop front will work > > using > > > two stack only in constant 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> > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
