/**************************************************************************
* 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:
* Remove and return the top element on the stack.
*
* Time Complexity of Solution:
* Best = Average = Worst = const.
*
* Technical Details: The minimum value on the stack must be tracked
* at all time. Hence, if the value popped was the minimum value
* on the stack, remove it so the next minimum value may now
* become the new minimum value.
*
***********************************************************************/
public Integer pop() {
Integer p = primary.pop();
if (p == minimums.peek()) {
minimums.pop();
}
return p;
}
}
import org.junit.Test;
import static org.junit.Assert.*;
public class StackWithGetMinTest {
/**
* Test of pop method, of class StackWithGetMin.
*/
@Test
public void testPop() {
System.out.println("pop");
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);
}
for (int i = inputs.length; i > 0; i--) {
assertFalse(stack.isEmpty());
assertEquals(i, stack.size());
stack.pop();
}
assertTrue(stack.isEmpty());
assertEquals(0, stack.size());
}
}