Min-Max Stack

Here I am designing a data structure that supports the following operations in O(1) time.

1) Get Minimum

2) Get Maximum

3) Insert Minimum

4) Insert Maximum

5) Delete Minimum

6) Delete Maximum

Approach :→

1 → Make Two Stack 1.minStack & 2.maxStack.

2 → minStack contains the min elements and maxStack contain max elements at the top of the stack.

3 →When Insert an element in the stack at 1st check the element is grater than the maxStack top element or less than the minStack top element.

4 →If it is grater than maxStack top element→then add the element to the maxStack. else it is less than minStack top element→then add the element to the minStack.

5 →When Pop an element 1st popped the element then check that the popped element is minStack top element or maxStack top element →if minStack then popped the top of minStack & if maxStack then popped the top of maxStack.

6 →getMin() →min element is the top element of minStack.

7 →getMax() →max element is the top element of maxStack.

Get Anilabha Baral’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

So let’s see the Implementation Using Java: →

import java.util.Stack;
public class MinMaxStack extends Stack<Integer> {
/**
* Created By Anilabha Baral
*/
private Stack<Integer> minStack;
private Stack<Integer> maxStack;
public MinMaxStack() {
minStack = new Stack<Integer>();
maxStack = new Stack<Integer>();
}
public void push(int value) {
if (value <= min()) { // Note the '=' sign here
minStack.push(value);
}
if (value >= max()) {
maxStack.push(value);
}
super.push(value);
}
public Integer pop() {
int value = super.pop();
if (value == min()) {
minStack.pop();
}
if (value == max()) {
maxStack.pop();
}
return value;
}
public int min() {
if (minStack.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return minStack.peek();
}
}
public int max() {
if (maxStack.isEmpty()) {
return Integer.MIN_VALUE;
} else {
return maxStack.peek();
}
}
public static void main(String[] args) {
MinMaxStack ms = new MinMaxStack();
ms.push(18);
ms.push(5);
ms.push(14);
ms.push(55);
ms.push(16);
ms.push(51);
ms.push(11);
ms.push(53);
System.out.println("MAX Value In the Stack = "+ms.max());
System.out.println("MIN Value In the Stack = "+ms.min());
}
}

Output:

MAX Value In the Stack = 55
MIN Value In the Stack = 5