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.

Pages: 1 2

6 Responses to “MinStack”

  1. chaw said

    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)
    

    (3 1 4 1 5 9 2 5 9)
    ((1 . 9) (1 . 5) (1 . 2) (1 . 9) (1 . 5) (1 . 1) (1 . 4) (1 . 1) (3 . 3))
    #t (3 1 4 1 5 9 2 5 9)
    ((9 . 9) (9 . 5) (9 . 2) (9 . 9) (5 . 5) (4 . 1) (4 . 4) (3 . 1) (3 . 3))
    #t (44 3 71 47 54 40 20 75 15 68 78 20 11 79 1 33 81 73 28 85)
    ((1 . 85) (1 . 28) (1 . 73) (1 . 81) (1 . 33) (1 . 1) (3 . 79) (3 . 11)
     (3 . 20) (3 . 78) (3 . 68) (3 . 15) (3 . 75) (3 . 20) (3 . 40) (3 . 54)
     (3 . 47) (3 . 71) (3 . 3) (44 . 44))
    #t (39 57 29 99 86 22 75 83 39 78 60 24 16 32 98 17 52 46 94 49)
    ((99 . 49) (99 . 94) (99 . 46) (99 . 52) (99 . 17) (99 . 98) (99 . 32)
     (99 . 16) (99 . 24) (99 . 60) (99 . 78) (99 . 39) (99 . 83) (99 . 75)
     (99 . 22) (99 . 86) (99 . 99) (57 . 29) (57 . 57) (39 . 39))
    #t (Hello, World! Namaste नमस्ते OK Hellooo Oh oh ok)
    ((Hello, World! . ok) (Hello, World! . oh) (Hello, World! . Oh)
     (Hello, World! . Hellooo) (Hello, World! . OK) (Hello, World! . नमस्ते)
     (Hello, World! . Namaste) (Hello, World! . Hello, World!))
    (Hello, World! Namaste नमस्ते OK Hellooo Oh oh ok)
    ((नमस्ते . ok) (नमस्ते . oh) (नमस्ते . Oh) (नमस्ते . Hellooo) (नमस्ते . OK)
     (नमस्ते . नमस्ते) (Namaste . Namaste) (Hello, World! . Hello, World!))
    (Hello, World! Namaste नमस्ते OK Hellooo Oh oh ok)
    ((नमस्ते . ok) (नमस्ते . oh) (नमस्ते . Oh) (नमस्ते . Hellooo) (नमस्ते . OK)
     (नमस्ते . नमस्ते) (Namaste . Namaste) (Hello, World! . Hello, World!))
    #t #t
    

  2. Daniel said

    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:

    push
      top: 9, min: 9
      top: 8, min: 8
      top: 2, min: 2
      top: 3, min: 2
      top: 1, min: 1
      top: 7, min: 1
      top: 4, min: 1
      top: 0, min: 0
      top: 5, min: 0
      top: 6, min: 0
    pop
      top: 6, min: 0
      top: 5, min: 0
      top: 0, min: 0
      top: 4, min: 1
      top: 7, min: 1
      top: 1, min: 1
      top: 3, min: 2
      top: 2, min: 2
      top: 8, min: 8
      top: 9, min: 9
    
  3. Daniel said

    The stack.pop() call in my example code was intended to be stack.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.

  4. Xero said

    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))
    
  5. Larry Lee said

    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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: