# Stack With Minimum Function

## Question

Define a stack structure with “min” function — a function to get the minimum value within the stack. The time complexity of min, push and pop functions must be O(1).

## Solution

Push data to the stack at the same time update the minimum stack if the
new data is smaller then the current minimum value. Throw exception if stack is empty.

Pop data to the stack at the same time pop from the min stack if it is popping the minimum value. Throw exception if stack is empty.

And then return the current minimum value.

0: 10 -> NULL (MIN=10, POS=0) 1: 7 -> [0] (MIN=7, POS=1) // 用數組表示堆棧，第0個元素表示棧底 2: 3 -> [1] (MIN=3, POS=2) 3: 3 -> [2] (MIN=3, POS=3) 4: 8 -> NULL (MIN=3, POS=3) // 技巧在這裡，因為8比當前的MIN大，所以彈出8不會影響當前的MIN 5: 5 -> NULL (MIN=3, POS=3) 6: 2 -> [2] (MIN=2, POS=6) // 如果2出棧了，那麼3就是MIN 7: 6 -> [6]

### Samples

The following is an optimized implementation. Repeated minimum value will not be stored through comparing values while pushing or popping values.

``````#include <vector>
#include <cassert>

using namespace std;

template < typename T > class StackWithMin {

private:

vector < T > dataStack; // stacks to store data
vector < size_t > minStack; // stack to store position of minimum value

public:

void push(T data) {
dataStack.push_back(data);
if (minStack.empty() || data < dataStack[minStack.back()]) minStack.push_back(dataStack.size() - 1);
}

void pop() {
assert(!dataStack.empty());
if (dataStack.back() == dataStack[minStack.back()]) minStack.pop_back();
dataStack.pop_back();
}

T min() {
assert(!dataStack.empty() && !minStack.empty());
return dataStack[minStack.back()];
}
}

int main() {
StackWithMin < int > stack = StackWithMin < int > ();
stack.push(10);
stack.push(7);
stack.push(3);
stack.push(3);
stack.push(8);
stack.push(5);
stack.push(2);
stack.push(6);
printf("Minimum value: %dn", stack.min());
}
``````
``````import java.util.Stack;

public class Pactice02 {

public static void main(String[] args) {
System.out.println("Hello World!");
AdvancedStack stack = new AdvancedStack();
stack.push(10);
stack.push(7);
stack.push(3);
stack.push(3);
stack.push(8);
stack.push(5);
stack.push(2);
stack.push(6);
System.out.println("Minimum value: " + stack.getMinimum());
stack.pop();
System.out.println("Minimum value: " + stack.getMinimum());
stack.pop();
System.out.println("Minimum value: " + stack.getMinimum());
stack.pop();
System.out.println("Minimum value: " + stack.getMinimum());
}

public static class AdvancedStack extends Stack {
private Stack mMinimumStack = new Stack();
@Override public E push(E item) {
if (mMinimumStack.empty() || item.doubleValue() 0) {
return mMinimumStack.peek();
}
return null;
}
}
}
``````