Get Minimum
by Isai Damier

/**************************************************************************
 * Author: Isai Damier
 * Title: Stack With Get-Min
 * Project: geekviewpoint
 * Package: datastructure
 *
 * Description: Normally, only the top of a stack is available for
 *    peeking and popping. Here, however, the requirement is to make
 *    the minimum value on the stack always viewable in O(1).
 *    To that end, in addition to the primary stack of operation
 *    (called primary), a separate stack (called minimums) must be
 *    used to track the minimum value on the primary stack. The point
 *    is not to pop the minimum value in O(1); that would require a
 *    bit more work. Rather, the getMinimum function allows peeking
 *    into the stack, as it were, to see the minimum value on the
 *    stack.
 *
 *    Throughout the implementation it should be clear that the
 *    primary stack is the real (i.e. representative) stack and that
 *    the minimums stack is an auxiliary stack that exists only so
 *    the getMinimum() function may exist.
 *************************************************************************/ 
 import java.util.Stack;

public class StackWithGetMin {

  /**
   *  Stack<Integer> primary: where all the elements actually reside.
   */
  private final Stack<Integer> primary = new Stack<Integer>();
  /**
   *  Stack<Integer> minimums: used to track the minimum values on
   *  the stack. The most minimum value is always on top.
   */
  private final Stack<Integer> minimums = new Stack<Integer>();

 /***************************************************************
   * Statement:
   *   Indicate the minimum value on the stack.
   *
   * Time Complexity of Solution:
   *   Best = Average = Worst = const.
   *
   * Technical Details: This one-line function is the reason for this
   *     whole datastructure. Notice how the minimums stack is not
   *     maintained here. minimums is maintained by the push and the
   *     pop functions. The only operation in getMinimum is peeking
   *     into the minimums stack. Nonetheless, the minimums stack
   *     exists entirely for this function.
   *
   **************************************************************/
  public Integer getMinimum() {
    return minimums.peek();
  }
}
import org.junit.Test;
import static org.junit.Assert.*;

public class StackWithGetMinTest {

  /**
   * Test of getMinimum method, of class StackWithGetMin.
   */
  @Test
  public void testGetMinimum() {
    System.out.println("getMinimum");
    StackWithGetMin stack = new StackWithGetMin();
    assertTrue(stack.isEmpty());
    assertEquals(0, stack.size());
    Integer[] inputs = {40, 65, 5, 6, 32, 4, 7, 1, 2, 84, 9, 10};
    for (int i : inputs) {
      stack.push(i);
    }
    assertFalse(stack.isEmpty());
    assertEquals(inputs.length, stack.size());
    int[] mins = {40, 5, 4, 1};
    int min = mins.length - 1;
    for (int i = inputs.length - 1; i >= 0; i--) {
      assertEquals(inputs[i], stack.pop());
      if (!stack.isEmpty()) {
        if (stack.getMinimum() != mins[min]) {
          min--;
        }
        assertEquals(mins[min], (int) stack.getMinimum());
      }
    }
    assertTrue(stack.isEmpty());
    assertEquals(0, stack.size());
  }
}