Array based Deque implementation

Question

I am following an online example and learning "Circular Deque implementation in Java using array". Here is the online resource that I am following:

Circular Queue Implementation

I have an array based deque class which has final capacity of 5. Now if the array is full then I can have the methods create a temporary array of all the objects and then copy all the objects of temporary array back to "object[] arr". I have been at it for some time now but have not been able to get it going. I would appreciate if someone can help me understand the process here please. I have following class methods:

1. insertAtFront()
2. insertAtLast()
3. size()
4. isEmpty()
5. toString()

Here is my code:

public class ArrayDeque {

    private static final int INIT_CAPACITY = 5;             
    private int front;                              
    private int rear;                                       
    private Object[] arr;                           


    public ArrayDeque(){

        arr = new Object[ INIT_CAPACITY ];
        front = 0;
        rear = 0;       
    }   


    public void insertAtFirst(Object item){

        if(size() >= arr.length){

            Object[] tmp = new Object[arr.length + INIT_CAPACITY];

            for(int i = 0; i < size(); ++i)
                tmp[i] = arr[i];

            arr = tmp;
        }
        arr[front] = item;
        ++front;
    }


    public void insertAtLast(Object item){

        if(size() >= arr.length){

            Object[] tmp = new Object[arr.length + INIT_CAPACITY];

            for(int i = 0; i < size(); ++i)
                tmp[i] = arr[i];

            arr = tmp;
        }
        arr[rear] = item;
        ++rear;
    }


    public int size(){

        return (rear - front);      
    }   


    public boolean isEmpty(){

        return (front == rear);

    }   


    public String toString(){

        String s = "";
        for(int i = 0; i < size(); ++i)
            s += arr[i] + "\n";
        return s;
    }   
}//CLASS    

Answer 1

Try the below code, i changed the logic a bit by keeping track of how much the array is filled up. Your main problem is with the size() function, which is giving wrong indications. Some optimization is pending for i see some nulls in the results.

public class ArrayDeque {
    public static void main(String[] args) {
        ArrayDeque t = new ArrayDeque ();
        t.insertAtFirst("1");
        t.insertAtFirst("2");
        t.insertAtFirst("3");
        t.insertAtFirst("4");
        t.insertAtFirst("5");
        t.insertAtFirst("6");
        t.insertAtFirst("7");
        t.insertAtFirst("8");
        t.insertAtFirst("9");
        t.insertAtFirst("10");
        t.insertAtFirst("11");
        t.insertAtFirst("12");
        t.insertAtFirst("13");
        t.insertAtFirst("14");

        System.out.println("After first--"+t.toString());
        t.insertAtLast("1");
        t.insertAtLast("2");
        t.insertAtLast("3");
        t.insertAtLast("4");
        t.insertAtLast("5");
        t.insertAtLast("6");
        t.insertAtLast("7");
        t.insertAtLast("8");
        t.insertAtLast("9");
        t.insertAtLast("10");
        t.insertAtLast("11");
        t.insertAtLast("12");
        t.insertAtLast("13");
        t.insertAtLast("14");
        System.out.println("After last--"+t.toString());
    }
    private static final int INIT_CAPACITY = 5;             

    private int NEW_CAPACITY;
    private int ARRAY_SIZE;
    private Object[] arr;                           


    public TestClass(){

        arr = new Object[ INIT_CAPACITY ];

        NEW_CAPACITY = INIT_CAPACITY;
        ARRAY_SIZE = 0;
    }   


    public void insertAtFirst(Object item){

        if(ARRAY_SIZE == 0)
        {
            arr[0] = item;
            ARRAY_SIZE++;
        }
        else if(ARRAY_SIZE+1 < arr.length)
        {
            Object[] tmp = new Object[NEW_CAPACITY];
             for(int i = 1; i < arr.length; ++i)
                tmp[i] = (String)arr[i-1];

            arr = tmp;
            arr[0] = item;
            ARRAY_SIZE++;
        }
        else if(ARRAY_SIZE+1 >= arr.length)
        {
            NEW_CAPACITY = NEW_CAPACITY+INIT_CAPACITY;
            Object[] tmp = new Object[NEW_CAPACITY];
             for(int i = 1; i < arr.length; ++i)
                tmp[i] = (String)arr[i-1];

            arr = tmp;
            arr[0] = item;
            ARRAY_SIZE++;
        }
    }


    public void insertAtLast(Object item){

        if(ARRAY_SIZE == 0)
        {
            arr[0] = item;
            ARRAY_SIZE++;
        }
        else if(ARRAY_SIZE+1 < arr.length)
        {

            arr[ARRAY_SIZE] = item;
            ARRAY_SIZE++;
        }
        else if(ARRAY_SIZE+1 >= arr.length)
        {
            NEW_CAPACITY = NEW_CAPACITY+INIT_CAPACITY;
            Object[] tmp = new Object[NEW_CAPACITY];
             for(int i = 0; i < arr.length; ++i)
                tmp[i] = (String)arr[i];

            arr = tmp;

            arr[ARRAY_SIZE] = item;
            ARRAY_SIZE++;
        }
    }


    public int size(){

        return ARRAY_SIZE;      
    }   


    public boolean isEmpty(){

        return (ARRAY_SIZE == 0);

    }   


    public String toString(){

        String s = "";
        for(int i = 0; i < arr.length; ++i)
            s += arr[i] + "\t";
        return s;
    }   
}