linkedlistnode.java

linkedlistnode.java

import java.util.EmptyStackException;
import java.util.Scanner;

public class IntStack {

    private static final String STRING_BEGIN = "[";
    private static final String STRING_END   = "]";
    private static final String SEPARATOR    = ", ";

    private static final class IntStackNode {

        private final int datum;
        private final IntStackNode previous;
        private IntStackNode previousMinimum;

        IntStackNode(final int datum, final IntStackNode previous) {
            this.datum = datum;
            this.previous = previous;
        }

        int getDatum() {
            return datum;
        }

        IntStackNode getPreviousNode() {
            return previous;
        }

        IntStackNode getPreviousMinimum() {
            return previousMinimum;
        }

        void setPreviousMinimum(final IntStackNode previousMinimum) {
            this.previousMinimum = previousMinimum;
        }
    }

    private IntStackNode top;
    private IntStackNode minimum;
    private int size;

    public void push(final int datum) {
        IntStackNode newnode = new IntStackNode(datum, top);

        if (isEmpty()) {
            minimum = newnode;
        } else if (minimum.getDatum() > datum) {
            newnode.setPreviousMinimum(minimum);
            minimum = newnode;
        }

        top = newnode;
        ++size;
    }

    public int pop() {
        if (top == null) {
            throw new EmptyStackException();
        }

        final IntStackNode ret = top;

        if (minimum == ret) {
            minimum = ret.getPreviousMinimum();
        }

        top = top.getPreviousNode();
        --size;
        return ret.datum;
    }

    public int min() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        return minimum.getDatum();
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0; 
    }

    @Override
    public String toString() {
        IntStackNode node = top;

        if (top == null) {
            return STRING_BEGIN + STRING_END;
        }

        final StringBuilder sb = new StringBuilder(STRING_BEGIN);
        sb.append(top.getDatum());
        node = top.getPreviousNode();

        for (int i = 1; i < size; ++i) {
            sb.append(SEPARATOR).append(node.getDatum());
            node = node.getPreviousNode();
        }

        return sb.append(STRING_END).toString();
    }

    public static void main(final String[] args) {
        final IntStack stack = new IntStack();
        final Scanner scanner = new Scanner(System.in);

        loop:
        while (true) {
            System.out.print("> ");

            final String command = scanner.next().trim().toLowerCase();

            switch (command) {
                case "push":
                    doPush(stack, scanner);
                    break;

                case "pop":
                    doPop(stack);
                    break;

                case "print":
                    System.out.println(stack);
                    break;

                case "min":
                    doMin(stack);
                    break;

                case "quit":
                case "exit":
                    break loop;

                default:
                    System.out.println("Unknown command: \"" + command + "\"");
            }
        }
    }

    private static void doPush(IntStack stack, Scanner scanner) {
        int datum;

        try {
            datum = scanner.nextInt();
        } catch (NumberFormatException ex) {
            System.out.println("ERROR: An integer is required.");
            return;
        }

        stack.push(datum);
    }

    private static void doPop(IntStack stack) {
        try {
            stack.pop();
        } catch (EmptyStackException ex) {
            System.out.println("ERROR: Popping from an empty stack.");
        }
    }

    private static void doMin(IntStack stack) {
        try {
            System.out.println(stack.min());
        } catch (EmptyStackException ex) {
            System.out.println(
                    "ERROR: Asking for minimum element from an empty stack.");
        }
    }
}