Track the Maximum Element in a Stack.

Objective: In a Stack, keep track of maximum value in it. It might be the top element in the stack but once it is poped out, the maximum value should be from the rest of the elements in the stack.

Approach:

  • Create another another Stack(call it as track) which will keep track of maximum in the given Stack(call it as main).
  • When you insert an element in the main stack for the first time ( means it is empty), insert it in the track Stack as well.
  • Now onwards when you insert a new element(say it is x) in the main Stack, peek() the element from the track Stack ( say it is ‘a‘). Compare x and a and which ever is greater, insert it into track Stack.
  • When you pop the element from the main stack, pop from the track Stack as well
  • So to get to know the maximum element in the main Stack, peek the element in the track Stack. . See Example below.

Thanks Gaurav Dey for suggesting this solution.

 

Track-the-Maximum-Element-in-a-Stack

Complete Code:

import java.util.Stack;
public class TrackMaxInStack {
// objective here is to keep track of maximum value in a stack of integers
// create another another Stack which will keep track of maximum
Stack<Integer> main = new Stack<>();
Stack<Integer> track = new Stack<>();
public void insert(int x) {
if (main.isEmpty()) { // if stack is empty, insert the number in both
// stacks
main.add(x);
track.add(x);
} else {
// check if number in Stack(track) is bigger than x
// which ever is bigger, insert it into Stack
int a = track.peek();
track.add(Math.max(a, x));
main.add(x); // insert it into main stack.
}
}
public int remove() {
if (!main.isEmpty()) { // pop the top elements
track.pop();
return main.pop();
}
return 0;
}
public int getMax() {
return track.peek();
}
public static void main(String[] args) {
TrackMaxInStack i = new TrackMaxInStack();
i.insert(4);
i.insert(2);
i.insert(14);
i.insert(1);
i.insert(18);
System.out.println("Max Element is " + i.getMax());
System.out.println("Removing Element " + i.remove());
System.out.println("Max Element is " + i.getMax());
}
}

view raw
TrackMaxInStack.java
hosted with ❤ by GitHub


Output:

Max Element is 18
Removing Element 18
Max Element is 14