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:

insertAtFront()
insertAtLast()
size()
isEmpty()
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

It might seem minor, but I would also recommend removing the comments in your code. They're not providing any useful information and are, therefore, just noise. — bedwyr
– bedwyr, Commented Mar 4, 2014 at 4:24
Did not understand what you are trying to do, when the size() >= arr.length. Are you increasing the array capacity by another 5 and then adding to front or last? — ray
– ray, Commented Mar 4, 2014 at 5:40
Yes @ray. I cannot get the code to either inserAtFront() or insertAtLast() working. thank you. — Combustion007
– Combustion007, Commented Mar 4, 2014 at 5:55

ray · Accepted Answer · 2014-03-04 06:35:51Z

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;
    }   
}

I cannot thank you enough for all your help, It is working as it should. Now I know how to code this.

Collectives™ on Stack Overflow

Array based Deque implementation

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related