How to track the Maximum Element in a Stack ?

 In a Stack, keep track of the max­i­mum element value in it. It might be the top ele­ment in the stack but once it the current max is poped out from the stack then the max­i­mum value should be the second maximum element in the stack.

Algorithm:

  • We will maintain 2 Stacks to solve the problem. The first one main stack will contains the elements and the second stack named as the track stack will keep track of the maximum element in each step.
  • When we insert an ele­ment 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 ) in the main Stack, peek() the ele­ment from the track Stack ( say it is Y). Com­pare X and Y and which ever is greater, push() it into track Stack.
  • When you pop the ele­ment from the main stack, pop from the track Stack as well
  • So to get to know the max­i­mum ele­ment in the main Stackpeek the ele­ment in the track Stack. .

** The peek() method is used to look at the object at the top of this stack without removing it from the stack.

Check the following diagram to have a real example of the algorithm :

 

Now let us implement the algorithm :

package com.tuturself.algorithm;

import java.util.Stack;

public class MaxInStack {

 // objective here is to keep track of maximum value in a stack of integers
 // create another Stack which will keep track of maximum
 Stack < Integer > mainStack = new Stack < > ();
 Stack < Integer > trackStack = new Stack < > ();

 public void insert(int x) {
  if (mainStack.isEmpty()) { // if stack is empty, insert the number in both
   mainStack.push(x);
   trackStack.push(x);
  } else {
   // check if number in Stack(track) is bigger than x
   // which ever is bigger, insert it into Stack

   int a = trackStack.peek();
   trackStack.push(Math.max(a, x));
   mainStack.push(x); // insert it into main stack.
  }
 }

 public int remove() {
  if (!mainStack.isEmpty()) { // pop the top elements
   trackStack.pop();
   return mainStack.pop();
  }
  return 0;
 }

 public int getMax() {
  return trackStack.peek();
 }

 public static void main(String[] args) {
  MaxInStack maxInStack = new MaxInStack();
  maxInStack.insert(10);
  maxInStack.insert(2);
  maxInStack.insert(11);
  maxInStack.insert(12);
  System.out.println("Max Element is " + maxInStack.getMax());
  maxInStack.remove();
  System.out.println("Max Element is " + maxInStack.getMax());
  maxInStack.remove();
  System.out.println("Max Element is " + maxInStack.getMax());
 }
}

Output

Max Element is 12
Max Element is 11
Max Element is 10

 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself