## Interview Practice 02 – 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

```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;

/**
* Class defining a new type of stack supporting any datatype.
*/
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:

/**
* 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.
*/
void push(T data) {
dataStack.push_back(data);
if (minStack.empty() || data < dataStack[minStack.back()])
minStack.push_back(dataStack.size()-1);
}

/**
* 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.
*/
void pop() {
assert(!dataStack.empty());
if (dataStack.back() == dataStack[minStack.back()])
minStack.pop_back();
dataStack.pop_back();
}

/**
* return the current minimum value.
*/
T min() {
assert(!dataStack.empty() && !minStack.empty());
return dataStack[minStack.back()];
}
};

/**
* Main program
*/
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!");
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;
}
}
}
```