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…
(import (scheme base) ;; The rest are only for demos and tests: (scheme write) (scheme char) (only (srfi 1) list-tabulate fold) (only (srfi 8) receive) (only (srfi 27) random-integer)) (define (make-min-stack item<) ;; s = ((stack-item . min-item) ...), top-to-bottom stack order. (let ((s '())) (define (push item) (set! s (cons (cons item (if (or (null? s) (item< item (cdar s))) item (cdar s))) s))) (define (top) (if (null? s) (error "stack is empty") (caar s))) (define (pop) (let ((t (top))) (set! s (cdr s)) t)) (define (least) (if (null? s) (error "stack is empty") (cdar s))) (values push pop top least))) (define (demo item< items verbose?) (receive (push pop top least) (make-min-stack item<) (when verbose? (display items) (newline)) (for-each push items) (let* ((rhistory (fold (lambda (i r) (let ((l (least))) (cons (cons l (pop)) r))) '() items)) (history (reverse rhistory))) (when verbose? (display (reverse rhistory)) (newline)) (and (equal? (map cdr rhistory) items) (equal? (map car history) (fold (lambda (item min-trace) (cons (if (or (null? min-trace) (item< item (car min-trace))) item (car min-trace)) min-trace)) '() items)))))) (demo < '(3 1 4 1 5 9 2 5 9) #t) (demo > '(3 1 4 1 5 9 2 5 9) #t) (demo < (list-tabulate 20 (lambda (i) (random-integer 100))) #t) (demo > (list-tabulate 20 (lambda (i) (random-integer 100))) #t) (let ((words '("Hello, World!" "Namaste" "नमस्ते" "OK" "Hellooo" "Oh" "oh" "ok"))) (demo string<? words #t) (demo string>? words #t) (demo string-ci>? words #t)) (define (test) (let loop ((i 1000) (ok #t)) (and ok (or (<= i 0) (loop (- i 1) (demo < (list-tabulate 100 (lambda (i) (random-integer 1000))) #f)))))) (display (test)) (newline)Glad you’re back and well!
Here’s a solution in Python.
class MinStack(list): def push(self, x): least = x if self: least = min((self[-1][1], least)) self.append((x, least)) def pop_(self): return self.pop()[0] def top(self): return self[-1][0] def least(self): return self[-1][1] if __name__ == '__main__': stack = MinStack() l = [9, 8, 2, 3, 1, 7, 4, 0, 5, 6] print('push') for x in l: stack.push(x) print(f' top: {stack.top()}, min: {stack.least()}') print('pop') while len(stack) > 0: print(f' top: {stack.top()}, min: {stack.least()}') stack.pop()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
(defun make-minstack (&key (comparison-function #'<)) (let ((stack nil)) (labels ((compare (a b) (funcall comparison-function a b)) (stack-empty-p () (null stack)) (stack-top () (caar stack)) (stack-pop () (pop stack)) (stack-least () (cadar stack)) (stack-push (x) (let ((y (stack-least))) (let ((z (or (and y (compare y x) y) x))) (push (list x z) stack))))) (list (cons 'least #'stack-least) (cons 'pop #'stack-pop) (cons 'top #'stack-top) (cons 'push #'stack-push) (cons 'emptyp #'stack-empty-p))))) (defun minstack-push (minstack x) "push the element x on to the minstack" (funcall (cdr (assoc 'push minstack)) x)) (defun minstack-pop (minstack) "pop the top of minstack" (funcall (cdr (assoc 'pop minstack)))) (defun minstack-top (minstack) "return the top of minstack" (funcall (cdr (assoc 'top minstack)))) (defun minstack-least (minstack) "return the least element of minstack" (funcall (cdr (assoc 'least minstack))))A simple demo:
MINSTACK> (let ((ms (make-minstack))) (minstack-push ms 5) (minstack-push ms 2) (minstack-push ms -1) (minstack-push ms 500)) ((500 -1) (-1 -1) (2 2) (5 5))A Racket solution.
Same basic idea as what everyone else proposed above (in Haskell):
data Entry a = Entry {value :: a, minValue :: a} type MinStack a = [Entry a] push :: Ord a => MinStack a -> a -> MinStack a push [] x = [Entry x x] push ys@(Entry{minValue = y}:_) x = (Entry x (if x < y then x else y)):ys pop :: MinStack a -> MinStack a pop [] = [] pop (_:xs) = xs top :: MinStack a -> Maybe a top [] = Nothing top (Entry{value = x}:_) = Just x least :: MinStack a -> Maybe a least [] = Nothing least (Entry{minValue = x}:_) = Just x