4.51

If we are allowed to maintain a second stack on the side, this should be possible. The main stack is a regular stack that can be implemented using an array and an index to the top of the stack. The second stack will stack each entry when it becomes the new minimum, only. When an entry is popped from the main stack, it will be poped from the second stack only if identical. The minimum item is the top of the second stack.

I think the actual question was about ability of building the stack that has push/pop/extract-min operations as in the queues - the extract removes element. This is impossible - that would give us an opportunity to sort in O(n) time (n O(1) pushes to the data structure, and then n extract-min's) --Kubek2k 05:00, 6 November 2011 (EST)

Back to Chapter 4