This is a variation on the a Leetcode question

### Question

Design a structure that is similar to a stack such that it supports `push`

, `pop`

, `top`

, and retrieving the minimum and maximum elements 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.
*getMax()* — Retrieve the maximum element in the stack.

### Solution

In a usual `stack`

data structure, time to fetch the `max`

or `min`

item would depend on the order in which elements had been `pushed`

into it. You would have to `pop`

out all items and find the minimum element, and push back all the items into it such that the items are not lost.

To implement it with constant retrieval time, you can use an additinoal `dequeue`

structure such that, the head of the queue gets the global minima, and the tail gets the global maxima. It stores duplicate values of the minima and maxima such that, even if a ‘max’ or ‘min’ element is popped out, you will still know the global maxima/minima.

Since JS doesn’t have a `queue`

structure, we use an array to achieve that behavior.

```
const MaxMinStack = function(){
let MAX = Number.MIN_SAFE_INTEGER;
let MIN = Number.MAX_SAFE_INTEGER;
let size = 0;
const itemStack = [];
const dequeue = [];
const push = (item) => {
if (item >= MAX){
MAX = item;
dequeue.push(item);
} else if (item <= MIN){
MIN = item;
dequeue.unshift(item);
}
itemStack.push(item);
size++;
}
const pop = () => {
if(!size) return;
const item = itemStack.pop();
if(item == MAX){
dequeue.pop();
MAX = dequeue[dequeue.length - 1];
} else if(item == MIN){
dequeue.shift();
MIN = dequeue[0];
}
size--;
return item;
}
const top = () => itemStack[size - 1];
const getMin = () => size ? dequeue[0] : 'Stack is empty';
const getMax = () => size ? dequeue[size - 1] : 'Stack is empty';
return {
push,
pop,
top,
getMin,
getMax,
}
};
```