SpecialStack

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package special_stack;

import java.util.Iterator;
import java.util.Stack;

/**
 *
 * @author 141021
 */

/*
 Question: Design a Data Structure SpecialStack that supports all the stack
operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin()
which should return minimum element from the SpecialStack. All these operations
of SpecialStack must be O(1).
To implement SpecialStack, you should only use standard Stack data structure and no
other data structure like arrays, list, .. etc.

Example:

Consider the following SpecialStack
16  --> TOP
15
29
19
18

When getMin() is called it should return 15, which is the minimum
element in the current stack.

If we do pop two times on stack, the stack becomes
29  --> TOP
19
18

When getMin() is called, it should return 18 which is the minimum
in the current stack.
 */
class SpecialStack {

    Stack min;
    Stack stack;

    public SpecialStack() {
        min = new Stack();
        stack = new Stack();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(x);
            min.push(x);
        } else {
            stack.push(x);
            int y = (int) min.pop();
            if (x < y) {
                min.push(x);
            } else {
                min.push(y);
            }
        }
    }

    public int peek() {
        return (int) stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public int pop() {
        return (int) stack.pop();
    }

    public int getMin() {
        int x = (int) min.pop();
        min.push(x);
        return x;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Iterator it = stack.iterator();
        while (it.hasNext()) {
            sb.append(it.next());
            sb.append("\n");
        }

        return sb.toString();
    }
}

public class SpecialStackTest {

    public static void main(String[] args) {
        SpecialStack stack = new SpecialStack();

        for (int i = 0; i < 10; i += 2) {
            stack.push(i);
        }

        System.out.println(stack.toString());

        System.out.println(stack.isEmpty());
        System.out.println(stack.peek());
        System.out.println(stack.getMin());
        stack.push(-2);
        System.out.println(stack.getMin());

    }
}