Double Ended Queue implementation in Java, and Operations run in O(1) time

public class Main {



    /**

     * @param args

     */

    public static void main(String[] args) {

    Deque<Integer> Q = new Deque<Integer>(6);

    try {

        Q.addFirst(3);

        System.out.println(Q);

        Q.addFirst(5);

        System.out.println(Q);

        Q.removeFirst();

        System.out.println(Q);

        Q.addLast(7);

        System.out.println(Q);

        Q.removeFirst();

        System.out.println(Q);

        Q.removeLast();

        System.out.println(Q);

        System.out.println(Q.isEmpty());

        Q.removeFirst();

        

    } catch (FullStackException e) {

        // TODO Auto-generated catch block

        System.out.println(e.getMessage());

    }catch (EmptyStackException e) {

        // TODO Auto-generated catch block

        System.out.println(e.getMessage());

    }

    

    }



}

/**

* Double queue class

*/

class Deque<E>

{

//f is front index

//r is rear index

//N is the size of the queue

//A is the queue

//E is a generic type 

    private int f,r,N;

    private E[] A;

    

    public Deque(int s)

    {

        A = (E[]) new Object[s];

        f = 0;

        r = 0;

        N = s;

    }

    

    public void addFirst(E e) throws FullStackException

    {

        if (size() == N - 1) throw new FullStackException();

        /**

         * Would work in Python

         * f = (f - 1 ) % N;

         */

        f = (f == 0) ? N - 1 : (f - 1 ) % N;

        A[f] = e;

    }

    

    public void addLast(E e) throws FullStackException

    {

        if (size() == N - 1) throw new FullStackException();

        A[r] = e;

        r = (r + 1 ) % N;

    }

    

    public E removeFirst() throws EmptyStackException

    {

        if (isEmpty()) throw new EmptyStackException();

        E temp = A[f];

        A[f] = null;

        f = (f + 1 ) % N;

        return temp;

    }

    

    public E removeLast() throws EmptyStackException

    {

        if (isEmpty()) throw new EmptyStackException();

        /**

         * Would work in Python

         * r = (r - 1 ) % N;

         */

        r = (r == 0) ? N - 1 : (r - 1 ) % N;

        E temp = A[r];

        A[r] = null;

        return temp;

    }

    

    public E getFirst() throws EmptyStackException

    {

        if (isEmpty()) throw new EmptyStackException();

        return A[f];

    }

    

    public E getLast() throws EmptyStackException

    {

        if (isEmpty()) throw new EmptyStackException();

        int temp = (r - 1 ) % N;

        return A[temp];

    }

    

    public int size()

    {

        return (N - f + r) % N;

    }

    

    public boolean isEmpty()

    {

        return f == r;

    }

    

    public String toString()

    {

        String str = "(";

        for(E e:A) str += e + ",";

        str += ")";

        return str;

    }

}



class FullStackException extends Exception

{

    public FullStackException()

    {

        super("Stack is full!");

    }

}



class EmptyStackException extends Exception

{

    public EmptyStackException()

    {

        super("Stack is empty!");

    }

}
This entry was posted in Code samples and tagged . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *