Problem: You need to implement a stack data structure that can also report the minimum element in constant-time.

Solution: This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can't just add a new variable to track the minimum because when the stack is popped you wouldn't be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly. So we need to keep some auxiliary list of the stack items so we can update the minimum variable after we pop items. A clever way to do that is to use another stack that stores the minimum of all items in the stack. The minimum value is calculated when items are pushed to the stack and when items are popped from the stack we also pop from the minStack to reveal the new minimum value.

Here's some simple C# code to show this:

   1:  public class MinStack<T> where T:IComparable<T>
   2:      {
   3:          private readonly Stack<T> minStack = new Stack<T>();
   4:          private readonly Stack<T> stack = new Stack<T>();
   5:   
   6:          public T Minimum
   7:          {
   8:              get { return minStack.Peek(); }
   9:          }
  10:   
  11:          public void Push(T element)
  12:          {
  13:              stack.Push(element);
  14:              if (minStack.Count == 0 || element.CompareTo(minStack.Peek()) <= 0)
  15:              {
  16:                  minStack.Push(element);
  17:              }
  18:              else
  19:                  minStack.Push(minStack.Peek());
  20:          }
  21:   
  22:          public T Pop()
  23:          {
  24:              minStack.Pop();
  25:              return stack.Pop();
  26:          }
  27:      }

And here's my Java code to do it.

   1:  class MinStack  <T extends Comparable<T>>
   2:  {
   3:      private Stack<T> minStack = new Stack<T>();
   4:      private Stack<T> stack = new Stack<T>();
   5:   
   6:      public T getMinimum()
   7:      {
   8:          return minStack.peek(); 
   9:      }
  10:   
  11:      public void Push(T element)
  12:      {
  13:          stack.push(element);
  14:          if (minStack.size() == 0 || element.compareTo(minStack.peek()) <= 0)
  15:          {
  16:              minStack.push(element);
  17:          }
  18:          else
  19:              minStack.push(minStack.peek());
  20:      }
  21:   
  22:      public T Pop()
  23:      {
  24:          minStack.pop();
  25:          return stack.pop();
  26:      }
  27:  }
Bookmark and Share