package org.wesome.dsalgo;
import java.util.Stack;
public class MaxInStack {
// this is main stack
Stack<Integer> mainStack = new Stack<>();
// this is maxStack, with every put in mainStack, current max will be kept in sync
Stack<Integer> maxStack = new Stack<>();
public void insert(int push) {
if (mainStack.isEmpty()) {
// mainStack and maxStack is empty, so there is no max right now, so we will add push in both stack
mainStack.add(push);
maxStack.add(push);
} else {
// mainStack already have elements, so new maxStack top will be max of existing maxStack top and current push
int maxStackTop = maxStack.peek();
maxStack.add(Math.max(maxStackTop, push));
mainStack.add(push);
}
}
public int remove() {
if (!mainStack.isEmpty()) {
// if mainStack is not empty then we have to remove top of both mainStack and maxStack, to keep both stack in sync
maxStack.pop();
return mainStack.pop();
}
return 0;
}
public int getMax() {
return maxStack.peek();
}
}