Stack operations

Is it possible to implement a stack in which push, pop, and min all
work in O(1) or constant number of steps.

push inserts element at the top of the stack.
pop removes element at the top of the stack.
min returns the element with minimum value in the stack.

There are no restrictions, i.e any amount of resouces (memory, cpu,
etc) can be used for implementation. The only requirement is that all
three operations must be O(1).

Stewart wrote:[color=blue]
> Is it possible to implement a stack in which push, pop, and min all
> work in O(1) or constant number of steps.
>
> push inserts element at the top of the stack.
> pop removes element at the top of the stack.
> min returns the element with minimum value in the stack.
>
> There are no restrictions, i.e any amount of resouces (memory, cpu,
> etc) can be used for implementation. The only requirement is that all
> three operations must be O(1).
>[/color]
Yes. Now what's your question about C++?

--ag

--
Artie Gold -- Austin, Texas
http://it-matters.blogspot.com (new post 12/5)
http://www.cafepress.com/goldsays

"Stewart" <pntva@yahoo.com> wrote in message
news:1120424800.376330.51930@o13g2000cwo.googlegro ups.com...[color=blue]
> Is it possible to implement a stack in which push, pop, and min all
> work in O(1) or constant number of steps.
>
> push inserts element at the top of the stack.
> pop removes element at the top of the stack.
> min returns the element with minimum value in the stack.
>
> There are no restrictions, i.e any amount of resouces (memory, cpu,
> etc) can be used for implementation. The only requirement is that all
> three operations must be O(1).
>[/color]

Yes! And believe it or not, it's easy! Hint: use the standard library.

ben