Min Stack

July 27, 2012

If you ignore the requirement that all three operations must perform in constant time, this is easy. One choice creates a stack in the normal way, with push and pop operating in constant time, then performs linear search when the minimum is requested. Another choice uses some kind of balanced tree in which each operation is performed in logarithmic time. But getting a constant-time set of operations is hard.

Our solution achieves constant time for all three operations at the expense of auxiliary space equal to the size of the stack. The idea is to keep two stacks, one for the stack itself and the other for the stack of minimums. The push operation puts the new item at the top of the regular stack and, if it is less than the item at the top of the minimums stack, put it on top of the minimums stack as well. The pop operation removes the item at the top of the regular stack; it also removes the item at the top of the minimums stack if it is the same as the item popped from the top of the regular stack. To find the minimum, simply inspect the top of the minimums stack.

We represent a min-stack as a cons pair with the regular stack in its car and the min-stack in its cdr; for instance, the min-stack that results from inserting 3, 4, 5, 1 and 2 in order is ((2 1 5 4 3) 1 3), where the entire input is stacked (in reverse order) in the car of the list and the two minimums, 3 and 1, are stacked (in reverse order) in the cdr of the list. Here is the empty min-stack:

(define empty (list (list)))

(define (empty? x) (equal? empty x))

The push operation first checks if the min-stack is empty, and returns a pair of two singleton lists if it is. Otherwise, the new item is stacked onto the regular stack, and stacked onto the minimum stack only if it is smaller than the current minimum:

(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)))))

Since we represent a min-stack as a pair of lists, we get a good opportunity for a workout on the compositions of car (the head of the list) and cdr (the rest of the list) provided by Scheme. The top of the regular stack is the car of the inner list stored in the car of the pair, the caar, which is 2 in the sample shown above. The top of the minimum stack is the car of the cdr of the pair, the cadr, which is 1 in the sample shown above (the second 1, not the 1 in the inner parentheses). Here are two access functions:

(define (top min-stack)
  (if (empty? min-stack)
      (error 'top "empty stack")
      (caar min-stack)))

(define (minimum min-stack)
  (if (empty? min-stack)
      (error 'minimum "empty stack")
      (cadr min-stack)))

All that’s left is the pop operation, which needs to check if the item being popped is the same as the current minimum, in which case the current minimum is also popped; since we only have a lt? comparison, we call it twice to check equality:

(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)))))

Here are some examples:

> (define x empty)
> (set! x (push < 3 x))
> (set! x (push < 4 x))
> (set! x (push < 5 x))
> (top x)
5
> (minimum x)
3
> x
((5 4 3) 3)
> (set! x (push < 1 x))
> (set! x (push < 2 x))
> (top x)
2
> (minimum x)
1
> x
((2 1 5 4 3) 1 3)
> (set! x (pop < x))
> (set! x (pop < x))
> x
((5 4 3) 3)
> (set! x (pop < x))
> (top x)
4
> (minimum x)
3
> (set! x (pop < x))
> (set! x (pop < x))
> (empty? x)
#t
> x
(())

You can run the program at http://programmingpraxis.codepad.org/EdKcpMok.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
14 Comments »

14 Responses to “Min Stack”

  1. Programming Praxis – Min Stack « Bonsai Code said
    July 27, 2012 at 10:41 AM

    […] today’s Programming Praxis exercise, our goal is to create s stack-like data structure that can push, pop […]

  2. Remco Niemeijer said
    July 27, 2012 at 10:41 AM

    My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/27/programming-praxis-min-stack/ for a version with comments):

    empty :: ([a], [a1])
empty = ([], [])

push :: Ord a => a -> ([a], [a]) -> ([a], [a])
push x (ms,xs) = (if null ms || x < head ms then x:ms else ms, x: xs)

pop :: Eq a => ([a], [a]) -> (Maybe a, ([a], [a]))
pop (m:ms,x:xs) = (Just x, (if m == x then ms else m:ms, xs))
pop s           = (Nothing, s)

min' :: ([a], [a]) -> Maybe a
min' (m:_, _) = Just m
min' _        = Nothing
  3. Christian Delahousse said
    July 28, 2012 at 12:44 AM

    Javascript. I used a function constructor.

    
function MinStack() {
	var pushPopStack= []
		, minimumsStack = []
		, n = 0 //Num of elems in structure
		, m = 0;// num of elems in min stack


	this.push = function (elem) {

		//If num of elems is zero, push to both stacks. 1st elem
		//is also a minimum
		if (n === 0) {
			minimumsStack.push(elem);
			m++;
		}
		//If new elem is lower than current min, we push a new min
		else if (elem < minimumsStack[m-1]) {
			minimumsStack.push(elem);
			m++;
		}

		pushPopStack.push(elem);
		n++;

	};

	
	this.pop = function () {

		if (n === 0) {
			throw "No elems";
		}

		var elem = pushPopStack.pop();
		n--;

		//If elem matches pop of min stack, pop that one
		//off too
		if (elem === minimumsStack[m-1]) {
			m--;
			minimumsStack.pop();
		}
		return elem;
	};

	//Return minimun
	this.min = function () {
		return minimumsStack[m-1];
	};

	this.toString = function () {
		var str = pushPopStack + " | " + minimumsStack;
		return str;
	};
}

var ms = new MinStack();
  4. Mike said
    July 28, 2012 at 5:28 PM

    Python version:

    class MinStack:
	def __init__(self):
		self.mins = []
		self.stack = []

	def push(self, item):
		self.stack.append(item)
		if not self.mins or item <= self.mins[-1]:
			self.mins.append(item)

	def pop(self):
		item = self.stack.pop()
		if item == self.mins[-1]:
			self.mins.pop()
		return item

	def min(self):
		return self.mins[-1]

    For the push operation, I think you need to add the new item to the min stack if it is returns 0, but also clears a 0 from the minimum stack
    minimum –> should still be zero

  5. Mike said
    July 28, 2012 at 5:33 PM

    Sorry, a less than symbol messed up my comment.

    I think the push operation needs to add the new item to the minimum stack when it is less than or equal to the current minimum. Otherwise, a minimum item could get popped off to soon. Consider this sequence of operations:

    push 5
push 3
push 3
pop          <- returns 3, but also removes 3 from the top of the min stack
minimum  <- should still return 3
  6. programmingpraxis said
    July 28, 2012 at 6:37 PM

    The problem text states that all items are distinct.

  7. madscifi said
    July 28, 2012 at 6:58 PM

    Mike, pushing 3 onto the stack twice is actually not legal according the specification: “You may assume that all elements are distinct”.

  8. kawas said
    July 29, 2012 at 8:18 PM

    Clojure solution almost similar to the Haskell one

    (defn empty' [] (vector '() '()))

(defn min' [[_ mins]] (first mins))
(defn peek' [[stack _]] (first stack))

(defn push' [[stack mins] x]
  (vector (conj stack x)
          (if (and (seq mins) (> x (first mins))) mins
            (conj mins x))))

(defn pop' [[stack mins]]
  (vector (rest stack)
          (if (not= (first stack) (first mins)) mins
            (rest mins))))

    Alternate solution, using protocol and an helper constructor

    (defprotocol IMinStack
  (min' [this])
  (peek' [this])
  (push' [this e])
  (pop' [this]))

(defrecord MinStack [_stack _mins]
  IMinStack
    (min' [this] (first _mins))
    (peek' [this] (first _stack))

    (push' [this e]
      (MinStack.
        (conj _stack e)
        (if (and (seq _mins) (> e (first _mins))) _mins
            (conj _mins e))))

    (pop' [this]
      (MinStack.
          (rest _stack)
          (if (not= (first _stack) (first _mins)) _mins
              (rest _mins)))))

(defn empty' [] (MinStack. '() '()))

    Whatever the solution you can use it the same way

    (empty')
(min' (empty'))
(peek' (empty'))
(pop' (empty'))
(push' (empty') 5)
(push' (push' (empty') 5) 3)
(peek' (push' (push' (empty') 5) 3))
(push' (push' (empty') 5) 7)
(peek' (push' (push' (empty') 5) 7))
(pop' (push' (push' (empty') 5) 3))
(pop' (push' (push' (empty') 5) 7))
(peek' (pop' (push' (push' (empty') 5) 7)))
  9. Catalin Cristu (@catalin_c) said
    July 30, 2012 at 10:14 AM

    A Go solution similar to the Python one:

    
package main

import "fmt"

type MinStack struct {
	stack []int
	mins  []int
}

func NewMinStack() *MinStack {
	return &MinStack{make([]int, 0), make([]int, 0)}
}

func (st *MinStack) String() string {
	if st.Empty() {
		return "empty stack"
	}
	return fmt.Sprintf("top=%d min=%d", st.Top(), st.Min())
}

func (st *MinStack) Empty() bool {
	return len(st.stack) == 0
}

func (st *MinStack) Push(n int) {
	st.stack = append(st.stack, n)
	if len(st.mins) == 0 || n <= st.mins[len(st.mins)-1] {
		st.mins = append(st.mins, n)
	}
}

func (st *MinStack) Top() int {
	if st.Empty() {
		panic("empty stack")
	}
	return st.stack[len(st.stack)-1]
}

func (st *MinStack) Pop() int {
	if st.Empty() {
		panic("empty stack")
	}
	n := st.stack[len(st.stack)-1]
	st.stack = st.stack[0 : len(st.stack)-1]
	if n == st.mins[len(st.mins)-1] {
		st.mins = st.mins[0 : len(st.mins)-1]
	}
	return n
}

func (st *MinStack) Min() int {
	if st.Empty() {
		panic("empty stack")
	}
	return st.mins[len(st.mins)-1]
}

func main() {
	st := NewMinStack()
	st.Push(3)
	st.Push(4)
	st.Push(5)
	fmt.Println(st)
	st.Push(1)
	st.Push(2)
	fmt.Println(st)
	st.Pop()
	st.Pop()
	fmt.Println(st)
}
  10. Ted said
    July 31, 2012 at 3:23 AM

    Learning a bit of c++:

    #ifndef CSTACK_H
    #define CSTACK_H
    using namespace std;

    struct node {
    int x;
    node *next;
    };

    class CStack {
    public:
    CStack();
    CStack(const CStack& orig);
    virtual ~CStack();
    void push(int x);
    int pop();
    int minimum();

    private:
    int min;
    node *head;
    };

    #endif /* CSTACK_H */

    #include “CStack.h”
    #include
    #include
    using namespace std;

    CStack::CStack() {
    min=1000;
    }

    CStack::CStack(const CStack& orig) {
    }

    CStack::~CStack() {
    }

    int CStack::minimum() {
    return min;
    }
    void CStack::push(int x) {
    node *current;
    if(head != NULL){
    current = new node;
    current->x=x;
    if(min>x){
    min=x;
    }
    current->next=head;
    head=current;
    }
    else{
    head = new node;
    min=x;
    head->x=x;
    }
    }

    int CStack::pop() {
    int ret = head->x;
    head=head->next;
    return ret;
    }

  12. swuecho said
    August 4, 2012 at 7:07 PM

    Perl6 version:

    class Min_stack {

    has @.stack;    
    has @.min;
    

    method push($item) {
	push @.stack, $item;  
	if @.min==0 or @.min[*-1] > $item {
	    push @.min, $item;
	}
    }

    method pop() {	
	my $item=pop @.stack;
	if $item == @.min[*-1] {
	    pop @.min;
	}
	return $item;
    }

    method min() {
	@.min[*-1];
    }

}
  13. Min Stack « Learning language said
    August 4, 2012 at 7:11 PM

    […] problem: Min Stack Design a data structure that provides push and pop operations, like a stack, plus a third operation […]

  14. swuecho said
    August 5, 2012 at 12:37 AM

    should rename the method name as http://swuecho.wordpress.com/2012/08/04/min-stack/, because of names conflict.

Leave a comment