# Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• `push(x)` — Push element x onto stack.
• `pop()` — Removes the element on top of the stack.
• `top()` — Get the top element.
• `getMin()` — Retrieve the minimum element in the stack.

Example 1:

```Input ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output [null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2```

Constraints:

• Methods `pop``top` and `getMin` operations will always be called on non-empty stacks.

​To make a constant time `getMin()`, we need to keep track of the latest minimum value for each element in the stack. We can solve the problem by defining the stack using a LinkedList. Following is the Node for the LinkedList.

```class Node {
int value;
int min;
}
```

An instance of Node is the entry of the `Stack`, where :

• value: Value of the Node or `Stack` element.
• min: Minimum value until this node is pushed into the `Stack`.

Following is the Implementation:

Note : `java.util.LinkedList` is Doubly-linked list implementation of the `List` and `Deque` interfaces.

```import java.util.*;

class Node {
int value;
int min;

public Node(int v, int m) {
value = v;
min = m;
}
}

class MinStack {

/**
* initialize your data structure here.
*/
public MinStack() {
}

public void push(int x) {
Node node = null;
if (data.isEmpty()) {
node = new Node(x, x);
} else {
Node prev = data.getLast();
node = new Node(x, Math.min(x, prev.min));
}
}

public void pop() {
if (!data.isEmpty()) data.removeLast();
}

public int top() {
return data.isEmpty() ? -1 : data.getLast().value;

}

public int getMin() {
return data.isEmpty() ? -1 : data.getLast().min;
}
}
```

Categories: Stack