CSCI152 L9 P1

//////////////////////////////////////////////////////////////////////////// Generic Stack ADT
/**
 *
 * @author Dastan Iyembergen
 * @param <T>
 */
public interface Stack<T> {

    /**
     * Puts the given element on the top of the stack.
     *
     * @param value element to be added on the top of the stack
     */
    public void push(T value);

    /**
     * Removes and returns the top most element of the stack
     *
     * @return the top most element of the stack
     * @throws Exception if the stack is empty
     */
    public T pop() throws Exception;

    /**
     * @return the size of the stack
     */
    public int getSize();

    /**
     * Removes all elements from the stack
     */
    public void clear();

    /**
     * @return a String representation of the stack
     */
    @Override
    public String toString();
}

//////////////////////////////////////////////////////////////////////////// Generic Stack Impl
/**
 *
 * @author Dastan Iyembergen
 * @param <T>
 */
public class ArrayStack<T> implements Stack<T>{
    private T[] values;
    private int size;

    public ArrayStack(){
        values=(T[]) new Object[10];
        size=0;
    }

    @Override
    public void push(T value) {
        if (size==values.length){
            T[] tmpArr=(T[]) new Object[2*values.length];
            for (int i=0; i<values.length; i++)
                tmpArr[i]=values[i];
            values=tmpArr;
        }
        values[size++]=value;
    }

    @Override
    public T pop() throws Exception {
        if (size<=0){
            throw new Exception("The stack is empty.");
        }
        T res=values[size-1];
        values[size-1]=null;
        size--;
        return res;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public void clear() {
        values=(T[]) new Object[10];
        size=0;
    }

    @Override
    public String toString(){
        String list="bottom[";
        for (int i=0; i<size; i++){
            list+=values[i];
            if (i<size-1)
            list+=", ";
        }
        return list+"]top";
    }
}

//////////////////////////////////////////////////////////////////////////// Generic Queue ADT
/**
 *
 * @author Dastan Iyembergen
 * @param <T>
 */
public interface Queue<T> {

    /**
     * Adds an element to the end of the queue.
     *
     * @param value element to be added to the end of the queue
     */
    public void enqueue(T value);

    /**
     * Removes and returns the front most element of the queue
     *
     * @return the front most element of the queue
     * @throws Exception if the queue is empty
     */
    public T dequeue() throws Exception;

    /**
     * @return the size of the queue
     */
    public int getSize();

    /**
     * Removes all elements from the queue
     */
    public void clear();

    /**
     * @return a String representation of the queue
     */
    @Override
    public String toString();
}

//////////////////////////////////////////////////////////////////////////// Generic Queue Impl
/**
 *
 * @author Dastan Iyembergen
 * @param <T>
 */
public class ArrayQueue<T> implements Queue<T> {

    private T[] values;
    private int size;
    private int front;
    private int back;

    public ArrayQueue(){
        values=(T[]) new Object[10];
        size=0;
        front=0;
        back=9;
    }

    @Override
    public void enqueue(T value) {
        if (size==values.length){
            int i=front, j=0;
            T[] tmp=(T[]) new Object[2*values.length];
            do {
                tmp[j++]=values[i++];
                i%=values.length;
            } while (i!=front);
            values=tmp;
            front=0;
            back=j-1;
        }
        back=(++back)%values.length;
        values[back]=value;
        size++;
    }

    @Override
    public T dequeue() throws Exception {
        if (size==0){
            throw new Exception("The queue is empty.");
        }
        T result=values[front];
        values[front++]=null;
        front%=values.length;
        size--;
        return result;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public void clear() {
        values=(T[]) new Object[10];
        size=0;
        front=0;
        back=9;
    }

    @Override
    public String toString(){
        String res="front[";
        int i=front, j=0, c=0;
        while (c<size) {
            res+=values[i++];
            i%=values.length;
            if (c<size-1){
                res+=", ";
            }
            c++;
        }
        res+="]back";
        return res;
    }
}