Question

JAVA PROGRAM

Design a stack that supports push, pop, top, and retrieving the minimum element 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. Example 1: Input ["MinStack", "push", "push","push", "getMin","pop","top", "getMin"] [1], [-2], [0], [-3],[1,1],[1, [1] Output [null, null, null,null,-3, null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return minStack.getMin(); // return -2 Constraints: • Methods pop, top and getMin operations will always be called on non-empty stacks.

Answer 1

import java.util.*;

public class MinStack
{
Stack<Integer> s;
Integer minEle;
  
MinStack() { s = new Stack<Integer>(); }
  
void getMin()
{
if (s.isEmpty())
System.out.println("Stack is empty");
  
else
System.out.println("Minimum Element in the " +
" stack is: " + minEle);
}
  
void top()
{
if (s.isEmpty())
{
System.out.println("Stack is empty ");
return;
}
Integer t = s.pop(); // Top element
System.out.print("Top Most Element is: ");
  
if (t < minEle)
System.out.println(minEle);
else
System.out.println(t);
}
  
void pop()
{
if (s.isEmpty())
{
System.out.println("Stack is empty");
return;
}
  
System.out.print("Top Most Element Removed: ");
Integer t = s.pop();
  
if (t < minEle)
{
System.out.println(minEle);
minEle = 2*minEle - t;
}
  
else
System.out.println(t);
}
  
void push(Integer x)
{
if (s.isEmpty())
{
minEle = x;
s.push(x);
System.out.println("Number Inserted: " + x);
return;
}
  
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
  
else
s.push(x);
  
System.out.println("Number Inserted: " + x);
}

public static void main(String[] args)
{
MinStack s = new MinStack();
String[][] opr ={ {"push","push","push", "getMin","pop", "top", "getMin"},{"-2","0","-3","","","",""}};
String[] op= {"","","","","","",""};
for(int i=0; i< 7; i++)
{
       if(opr[0][i].equals("push"))
   {
       int x= Integer.parseInt(opr[1][i]);
       s.push(x);
       String y = Integer.toString(x);
       op[i]=y;
   }
   else if(opr[0][i].equals("pop"))
   {
       s.pop();
       op[i]="null ";
   }
   else if(opr[0][i].equals("getMin"))
   {
       s.getMin();
        op[i]="null ";
   }
   else if(opr[0][i].equals("top"))
   {
       s.top();
       op[i]="null ";
   }
   else
   {
       op[i]="null ";
   }    
}
for(int i=0;i<op.length;i++)
{
   System.out.print(op[i] +" ");
}
}
}