Clear
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**************************************************************************
 * 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:
   *   Empty the stack.
   *
   * Technical Details: An empty stack has no real-valued minimum.
   *     Therefore in addition to emptying the primary stack,
   *     the minimums stack is also emptied.
   *
   **************************************************************/
  public void clear() {
    primary.clear();
    minimums.clear();
  }
}