# 155. Min Stack (Easy)

https://leetcode.com/problems/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:

```MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.
```

## Solutions

### 1.

``````class MinStack {

Stack<Integer> stack;
Queue<Integer> queue;

public MinStack() {
stack = new Stack<>();
queue = new PriorityQueue<>();
}

public void push(int x) {
stack.push(x);
queue.offer(x);
}

public void pop() {
int value = stack.pop();
queue.remove(Integer.valueOf(value));
}

public int top() {
return stack.peek();
}

public int getMin() {
return queue.peek();
}
}
``````

### 2.

``````class MinStack {

Stack<Integer> stack;
Stack<Integer> min;

public MinStack() {
stack = new Stack<>();
min = new Stack<>();
}

public void push(int x) {
stack.push(x);
if (min.isEmpty() || x <= min.peek()) {
min.push(x);
}
}

public void pop() {
int value = stack.pop();
if (min.peek() == value) {
min.pop();
}
}

public int top() {
return stack.peek();
}

public int getMin() {
return min.peek();
}
}
``````

### 3.

``````class MinStack {
class ListNode {
int value = 0;
ListNode next = null;

public ListNode(int v) {
value = v;
}
}

ListNode stack;
ListNode queue;

public MinStack() {
stack = new ListNode(-1);
queue = new ListNode(-1);
}

public void push(int x) {
ListNode n1 = new ListNode(x);

n1.next = stack.next;
stack.next = n1;

ListNode n2 = new ListNode(x);
if (queue.next == null) {
queue.next = n2;
} else {
ListNode ptr = queue;
while (ptr.next != null) {
if (ptr.next.value < x) {
ptr = ptr.next;
continue;
}

n2.next = ptr.next;
ptr.next = n2;
break;
}
}
}

public void pop() {
ListNode val = null;
if (stack.next != null) {
val = stack.next;
stack.next = stack.next.next;
}

if (val != null) {
ListNode ptr = queue;
while (ptr.next != null) {
if (ptr.next.value != val.value) {
ptr = ptr.next;
continue;
}

ptr.next = ptr.next.next;
break;
}
}
}

public int top() {
if (stack != null) {
return stack.next.value;
}

return 0;
}

public int getMin() {
if (queue.next != null) {
return queue.next.value;
}

return 0;
}
}
``````