@Juvier, @yq Zhang
In your approach, when you are asked pop_front() you keep popping from
one stack and pushing them to another and then from the other pop the
top element. What happens is this top element happens to have been the
Min element?Example
stack1 {(2,2),(4,2),(3,2),(6,2)} (a,b) = ( element, min)
then you are asked pop_front(), you push to another stach like below
stck2: {(6,2),(3,2),(4,2),(2,2)}.
Then you remove (2,2)! Ok. But all elements in your stack2 still say
"2" is the min element. But "2" is no more in the "queue" (or for that
matter in the stacks we are using).
On Jan 4, 9:07 am, yq Zhang <[email protected]> wrote:
> @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.
