; min stack
(define empty (list (list)))
(define (empty? x) (equal? empty x))
(define (push lt? x min-stack)
(if (empty? min-stack)
(cons (list x) (list x))
(cons (cons x (car min-stack))
(if (lt? x (cadr min-stack))
(cons x (cdr min-stack))
(cdr min-stack)))))
(define (top min-stack)
(if (empty? min-stack)
(error 'top "empty stack")
(caar min-stack)))
(define (pop lt? min-stack)
(if (empty? min-stack)
(error 'pop "empty stack")
(cons (cdar min-stack)
(if (or (lt? (caar min-stack) (cadr min-stack))
(lt? (cadr min-stack) (caar min-stack)))
(cdr min-stack)
(cddr min-stack)))))
(define (minimum min-stack)
(if (empty? min-stack)
(error 'minimum "empty stack")
(cadr min-stack)))
(define x empty)
(set! x (push < 3 x))
(set! x (push < 4 x))
(set! x (push < 5 x))
(display (top x)) (newline) ; 5
(display (minimum x)) (newline) ; 3
(display x) (newline) ; ((5 4 3) 3)
(set! x (push < 1 x))
(set! x (push < 2 x))
(display (top x)) (newline) ; 2
(display (minimum x)) (newline) ; 1
(display x) (newline) ; ((2 1 5 4 3) 1 3)
(set! x (pop < x))
(set! x (pop < x))
(display x) (newline) ; ((5 4 3) 3)
(set! x (pop < x))
(display (top x)) (newline) ; 4
(display (minimum x)) (newline) ; 3
(set! x (pop < x))
(set! x (pop < x))
(display (empty? x)) (newline) ; #t
(display x) (newline) ; (())