Stack operations

[Stewart]

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).

 

[Artie Gold]

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).

Yes. Now what's your question about C++?

--ag

 

[benben]

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).

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

ben