// D. Scott
// CCI - Problem 3.2
// Find minimum value in a stack in constant time

import java.util.Scanner;

class Stack {
    int min;
    int min2;
    Node top;
    
    public Stack() {
        top = null;
        min = 999999;
        min2 = 999999;
    }
    
    void push(int d) {
        if (d < this.min) {
            min2 = min;
            min = d;
        }
        Node n = new Node(d);
        n.next = top;
        top = n;
    }
    
    int pop() {
        if (top == null) {
            System.out.println("Stack is empty.  Nothing to pop.\n");
            return -1;            
        }

        int res = top.data;
        if (top.data == this.min) 
            min = min2;
        top = top.next;
        return res;
    }
    
    int min() {
        if (isEmpty() == true) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return this.min;
    }
    
    boolean isEmpty() {
        if (top == null)
            return true;
        else
            return false;
    }
    
    void printStack() {
        System.out.println("\nCurrent stack (top to bottom):")
        if (top == null) {
            System.out.println("\tStack is empty.");
            return;
        }
        Node n = top;
        while (n != null) {
            System.out.println("\t"+n.data);
            n = n.next;
        }
    }
}
        

public static void main (String[] args)
{
    Stack s1 = new Stack();
    
    s1.printStack();
    
    // Push values, find min, pop values
    s1.push(44);
    s1.printStack();
    System.out.println("Min: " + s1.min());
    s1.push(56);
    s1.printStack();
    System.out.println("Min: " + s1.min());
    s1.push(22);
    s1.printStack();
    System.out.println("Min: " + s1.min());
    s1.push(83);
    s1.printStack();
    System.out.println("Min: " + s1.min());
    System.out.println("\nPopped: " + s1.pop());
    s1.printStack();
    System.out.println("Min: " + s1.min());
    System.out.println("\nPopped: " + s1.pop());
    s1.printStack();
    System.out.println("Min: " + s1.min());
    System.out.println("\nPopped: " + s1.pop());
    s1.printStack();
    System.out.println("Min: " + s1.min());
    System.out.println("\nPopped: " + s1.pop());
    s1.printStack();
    System.out.println("Min: " + s1.min());
}

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}