MinStack
May 19, 2020
Our strategy is to stack (value, minimum) pairs using Scheme’s normal list operations:
(define empty (list))
(define empty? null?)
(define (push x minstack)
(if (empty? minstack) (cons (cons x x) minstack)
(cons (cons x (min x (least minstack))) minstack)))
(define pop cdr)
(define top caar)
(define least cdar)
Here are some examples:
> (define ms empty) > (set! ms (push 4 ms)) > (set! ms (push 3 ms)) > (set! ms (push 7 ms)) > ms ((7 . 3) (3 . 3) (4 . 4)) > (top ms) 7 > (least ms) 3 > (set! ms (pop ms)) > (top ms) 3 > (least ms) 3 > (set! ms (pop ms)) > (empty? ms) #f > (top ms) 4 > (least ms) 4 > (set! ms (pop ms)) > (empty? ms) #t
You can run the program at https://ideone.com/rtMtFu.
Programming Praxis 
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