3.2 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.

Use another stack maintaining min.

push(T t)
{
  mainStack.push(t);
  T curMin = minStack.peek();
  if (curMin == null || t < curMin)
  {
    minStack.push(t);
  }
}

T peek()
{
  return mainStack.peek();
}

T poll()
{
  T t = mainStack.poll();
  if (t == null)
    return t;
  
  if (t == minStack.peek())
    minStack.poll();

  return t;
}

T min()
{
  return minStack();
}


Stack<T> mainStack;
Stack<T> minStack;

CC150 3.2