//size, isEmpty, expand, shrink, push, top, pop, toString
class DynamicArrayStackImpl {
    private int capacity;
    
    //default capacity
    private final static int DEFAULT_CAPACITY = 16;
    
    //to maintain minimum stackArray capacity.
    private final int INITIAL_CAPACITY;
    
    //top pointer
    private int top = -1;
    
    //stack holder
    private int[] stackArray;
    
    //Allocate memory with default capacity
    public DynamicArrayStackImpl() {
        //by default array initialize
        this(DynamicArrayStackImpl.DEFAULT_CAPACITY);
    }
    
    //Allocate memory with custom capacity
    public DynamicArrayStackImpl(int capacity) {
        this.capacity = capacity;
        this.INITIAL_CAPACITY = capacity;
        stackArray = new int[this.capacity];
    }
    
    //To get size of the stack
    public int size() {
        return top + 1;
    }
    
    //To check stack isEmpty
    public boolean isEmpty(){
        return top == -1;
    }
    
    //Double the stack size - if stack is full
    public void expand() {
        //double the capacity
        capacity = capacity * 2;
        
        //create new array with double capacity
        int[] newStack = new int[capacity];
        
        //copy old stack into new stack array
        System.arraycopy(stackArray, 0, newStack, 0, size());
        
        //assign new stack to stackArray.
        stackArray = newStack;
    }
    
    //Shrink to 1/2 if more than 3/4 is empty
    public void shrink() {
        //IF 1/2 array size is greater than INITIAL_CAPACITY size.
        //So that not shrink array less than INITIAL_CAPACITY
        if (INITIAL_CAPACITY <= (capacity >> 2)) {
            //Get 3/4 size
            int minSize = capacity >> 2;
            if (top < minSize) {
                //so stack is less than 3/4.
                
                //divide capacity by 2. So new size is 1/2;
                capacity = capacity / 2;
                
                //create new array with new capacity
                int[] newStack = new int[capacity];
                
                //copy old stack into new stack array
                System.arraycopy(stackArray, 0, newStack, 0, size());
                
                //assign new stack to stackArray.
                stackArray = newStack;
            }
        }
    }
    
    //Push ADT
    public void push(int data) throws Exception {
        //If stack is full - expand the size of the stack.
        if (size() == capacity) {
            expand();
        }
        
        //Otherwise add data to the stack.
        stackArray[++top] = data;
    }
    
    //Reading Top value
    public int top() throws Exception {
        //Exception handling - if stack is empty
        if (isEmpty()) {
            throw new Exception("Stack is empty!");
        }
        
        //Otherwise return top value.
        return stackArray[top];
    }
    
    //Pop ADT
    public int pop() throws Exception {
        //Exception handling - if stack is empty
        if (isEmpty()) {
            throw new Exception("Stack is empty!");
        }
        
        //Otherwise pop the top element
        int data = stackArray[top];
        stackArray[top--] = 0;
        
        //shrink if stack size is less than 3/4.
        shrink();
        
        return data;
    }
    
    //toString stackArray
    public String toString() {
        String arrayString = "[";
        
            for (int index = 0; index <= top; index++) {
                if (index == 0) {
                    //adding data if index is 0
                    arrayString += stackArray[index];
                }
                else {
                    //adding data with comma if index is not 0.
                    arrayString += "," + stackArray[index];
                }
            }
        
        arrayString += "]";
        
        return arrayString;
    }
}

/*
 * Dyanmic Array based stack implementation
 * using Java Example program
 */
public class DynamicArrayBasedImplementation {
    public static void main(String[] args) {
        //Using custom stack
        DynamicArrayStackImpl stack = new DynamicArrayStackImpl();
        
        try {
            //check stack is empty
            System.out.println("isEmpty: "+stack.isEmpty());
            
            //adding data to the stack
            stack.push(10);
            stack.push(20);
            stack.push(30);
            stack.push(40);
            stack.push(50);

            
            //will throw stack is full exception
            //stack.push(60);
            
            //print stack
            System.out.println("Stack: "+stack);
            
            //top element
            System.out.println("Top: "+stack.top());
            System.out.println("Stack: "+stack);
            
            //pop element
            System.out.println("Pop data: "+stack.pop());
            System.out.println("Stack: "+stack);
            
            //read size of the stack
            System.out.println("Size is "+stack.size());
            
            //check stack is empty
            System.out.println("isEmpty: "+stack.isEmpty());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}