Question

Write a ADT called in minStack that provides the following methods:

• push() // inserts an element to the “top” of the minStack

• pop() // removes the last element that was pushed on the stack

• top () // returns the last element that was pushed on the stack

• min() // returns the minimum value of the elements stored so far

Answer 1

class MinStack {

    static class Node {
        private int value;
        private Node next;

        public Node(int number) {
            this.value = number;
            next = null;
        }

        public Node(int number, Node next) {
            this.value = number;
            this.next = next;
        }
    }

    private Node head;

    public MinStack() {
        head = null;
    }

    public void push(int num) {
        head = new Node(num, head);
    }

    public int pop() {
        int result = head.value;
        head = head.next;
        return result;
    }

    public int top() {
        return head.value;
    }

    public int min() {
        int minValue = head.value;
        Node temp =head;
        while (temp != null) {
            if (temp.value < minValue)
                minValue = temp.value;
            temp = temp.next;
        }
        return minValue;
    }

    public boolean isEmpty() {
        return head == null;
    }
}

class MinStackTest {

    public static void main(String[] args) {
        MinStack stack = new MinStack();
        stack.push(4);
        stack.push(2);
        stack.push(9);
        System.out.println("Min: " + stack.min());
        stack.push(1);
        System.out.println("Min: " + stack.min());
        System.out.print("Stack: ");
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
    }
}