@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 <[email protected]> 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 <[email protected]> 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 ...." <[email protected]> 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 > [email protected]. > > > To unsubscribe from this group, send email to > > > > [email protected]<algogeeks%[email protected]> > <algogeeks%[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]<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.
