Write a method that adds an element to a stack but ensures t

Write a method that adds an element to a stack, but ensures that the smallest element is always at the top of the stack.

Note: the stack is not in full sorted order. It\'s only true that the smallest element is at the top.

For full credit, the method should be O(1).

The method header is: public void addToMinStack(StackInterface<Integer> stack, int newNum)

Solution

import java.util.Scanner;

interface StackInterface<Integer>
{
   int getTop(); // return the top item without removing it from stack
   int pop(); // return the top item and removes it from stack
    void push(int itm); // adds an item to the stack
    boolean isEmpty(); // returns true if stack is empty, false otherwise
    int size(); // returns the number of items in stack right now
    public void addToMinStack(StackInterface<Integer> stack, int newNum);
}

class ArrayStack <Integer> implements StackInterface <Integer>
{
    private int container[];
    private int top;
    private final static int DEFAULT_SIZE = 10;

    public ArrayStack ()
    {
        this(DEFAULT_SIZE);
    }

    public ArrayStack (int initSize)
    {
        container = new int [initSize];
        top = -1;
    }

    public int getTop()
    {
      
        return container[top];
    }

    public boolean isEmpty()
    {
        return (top == -1);
    }

    public int pop()
    {
      
        return container[top--];
    }

    public void push(int itm)
    {
        container[++top] = itm;
      
    }

    public int size()
    {
        return (top + 1);
    }
  
//Method
  
    public void addToMinStack(StackInterface<Integer> stack, int newNum)
    {
     
           if(newNum<=stack.getTop()) //compare new element with top element if less then push
           {
               stack.push(newNum);
              
   }
           else //otherwise pop top element and push new element and then push poped element again
           {
               int temp=stack.getTop();
               stack.pop();
               stack.push(newNum);
               stack.push(temp);
      
           }
      
    }
}

public class testing {
public static void main(String[] args)
{
  
  
   StackInterface <Integer> s = new ArrayStack <Integer>(10);
   s.push(10);
   s.push(11);
   s.push(12);
   s.push(4);
   s.push(17);
   s.push(1);
   Scanner s1=new Scanner(System.in);
   System.out.println(\"Initial top element of stack which is minimum: \");
   System.out.println(s.getTop());

      
   System.out.println(\"Enter new num\");
   int newNum=s1.nextInt();
   s.addToMinStack(s,newNum);
  
  
  
   System.out.println(\"New stack elements: \");
  
  
   while(!s.isEmpty())
   {
      
       System.out.println(s.pop());
   }

}

}