Problem3-2.java

public class Node {
  public Node next;
  public Node nextMinimum;
  public int data;
  
  public Node(int value) {
    this.data = value;
  }
}

class MinStack {
  public Node top;
  public Node minimum;
  public int minValue;
  
  public int pop() {
    if (top == null) {
      return null;
    }
    
    // popping minimum
    if (top == minimum) {
      minimum = top.nextMinimum;
      if (minimum != null) {
        minValue = minimum.data;
      }
      else {
        minValue = Integer.MAX_VALUE;
      }
    }
    
    int retValue = top.data;
    top = top.next;
    return retValue;
  }
  
  public void push(int value) {
    Node node = new Node(value);
    
    if (top == null) {
      top = node;
      minValue = top.data;
      minimum = top;
    }
    else {
      node.next = top;
      top = node;
      
      if (value < minValue) {
        minValue = value;
        // We have other minimum
        if (minimum != null) {
          node.nextMinimum = minimum;
        }
        minimum = node;
      }
    }
  }
  
  public int getMinValue() {
    return minValue;
  }
  
  public Node getMinNode() {
    return minimum;
  }
  
  
  
  
}