MinStack
May 19, 2020
[ My apologies that this exercise is so long delayed. We have been rewriting all of our business practices in the light of the pandemic, and work has been madness. The biggest projects are now complete, and we have retreated to merely super-busy, so maybe I will have time to write some more exercises. I hope everyone is well; I am. ]
Today’s task is to implement a minstack data structure that provides the normal stack operations push
, pop
and top
and also the operation least
which returns the smallest item in the stack without altering the stack in any way. All four operations must operate in O(1) time and O(n) space, where n is the size of the stack.
Your task is to implement a minstack as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Here’s a solution in R7RS Scheme. The main idea is the same as in the
solution by @programmingpraxis, but the implementation is a bit more
general in item-comparison predicates. As is often the case, the code
for the demo and test took longer than the main code. Wishing good
health to all…
Glad you’re back and well!
Here’s a solution in Python.
Output:
The
stack.pop()
call in my example code was intended to bestack.pop_()
, but it turns out to not matter in that example since the return value is not used. The former would return a pair, and the latter a single value.Hi, Here’s a closure based implementation in Commonlisp
A simple demo:
A Racket solution.
Same basic idea as what everyone else proposed above (in Haskell):