Peek
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 51 52 53 54 | /************************************************************************** * 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: * Look at the element at the top of the stack without removing it * * Time Complexity of Solution: * Best = Average = Worst = const. * * Technical Details: The primary stack is the real (i.e. * representative) stack. The minimums stack exists only for the * getMinimum function. If getMinimum were not important, all * operations could as well be performed on the primary stack * alone. * ************************************************************************/ public Integer peek() { return primary.peek(); } } |
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 | import org.junit.Test; import static org.junit.Assert.*; public class StackWithGetMinTest { /** * Test of peek method, of class StackWithGetMin. */ @Test public void testPeek() { System.out.println( "peek" ); 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()); assertEquals(inputs[inputs.length - 1 ], stack.peek()); assertEquals(inputs[inputs.length - 1 ], stack.peek()); assertFalse(stack.isEmpty()); assertEquals(inputs.length, stack.size()); } } |