O(1) Stack

How would you design a stack which, in addition, to push and pop, also has a function min which returns the minimum element?

Push, pop and min should all operate in O(1) time.

Scala

/**
  * 3.2
  * @param value
  * @param min
  */
case class Frame(value: Int, min: Int)

class Stack {
  var elems:List[Frame] = Nil
  def push(elem: Int): Unit = this.elems = this.elems match {
    case Nil => Frame(elem, elem) :: this.elems
    case _ => Frame(elem, elems.head.min min elem) :: this.elems
  }
  def pop: Int = this.elems match {
    case Nil => -1
    case x :: xs => {
      this.elems = xs
      x.value
    }
  }
  def min: Int = this.elems match {
    case Nil => -1
    case x :: xs => x.min
  }
}

val s = new Stack
s.push(5)
s.push(3)
s.push(99)
s.min
s.pop
s.pop
s.min

Second Tab