Deque implementation with circular array issue

Question

I'm trying to fully implement a Deque without using the one already made in the java library. my code compiles, but the output is not quite as expected. for instance, the capacity is supposed to be given to the class as a parameter, but the result shows that the real capacity ends up being 1 lower than the amount specified.

another issue that Iæm having is that the queue is supposed to work as first-in-first-out. but this is not represented in the results. any ideas?

public class ArrayDeque<E> implements IDeque<E> {


    private int capacity;
    private E[] array;
    private int front;
    private int end;
    private int size;


    public ArrayDeque(int capacity) {

        this.array = (E[]) new Object[capacity];
        this.capacity = capacity - 1;
        front = 1;
        end = 0;
        size = 0;


    }


    private boolean isFull() {
        return (size == capacity);
    }


    private boolean isEmpty() {
        return (size == 0);
    }


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


    @Override
    public void addFirst(E elem) throws DequeFullException {
        if (isFull())
            throw new DequeFullException("samlingen er full!");
        array[front] = elem;
        front = (front + 1) % capacity; // use modulo to make sure the front restarts from initial position once it reaches capacity
        size++;
    }

    @Override
    public E pullFirst() throws DequeEmptyException {
        if (isEmpty())
            throw new DequeEmptyException("Samlingen er tom!");
        front = (front - 1) % capacity;
        size--;
        return array[front];
    }


    @Override
    public E peekFirst() throws DequeEmptyException {
        if (isEmpty())
            throw new DequeEmptyException("samlingen er tom!");

        System.out.println(array[(front - 1) % capacity]);
        return array[(front - 1) % capacity];
    }

    @Override
    public void addLast(E elem) throws DequeFullException {
        if (isFull())
            throw new DequeFullException("samlingen er full!");
        array[end] = elem;
        end = (end - 1) % capacity;
        size++;

    }

    @Override
    public E pullLast() throws DequeEmptyException {
        if (isEmpty())
            throw new DequeEmptyException("samlingen er tom!");
        end = (end + 1) % capacity;
        size--;
        return array[end];


    }


    @Override
    public E peekLast() throws DequeEmptyException {
        if (isEmpty())
            throw new DequeEmptyException("samlingen er tom!");
        System.out.println(array[(end + 1) % capacity]);
        return array[(end + 1) % capacity];
    }

}

public class Main {
    public static void main(String[] args){
    ArrayDeque<String> deque = new ArrayDeque<>(6);

    deque.addFirst("first");
    deque.addFirst("second");
    deque.addFirst("third");
    deque.addFirst("fourth");


    deque.peekFirst();
    deque.peekLast();
    deque.addLast("fourth");
    deque.addLast("last");
    deque.peekLast();
    deque.size();
    }
}

"but the result shows that the real capacity ends up being 1 lower than the amount specified" - Maybe this.capacity = capacity - 1; is the cause? — Jacob G.
– Jacob G., Commented Feb 2, 2018 at 2:51

MrDeal · Accepted Answer · 2018-02-02 07:04:20Z

About the capacity problem you are experiencing: You are setting your array to have the capacity passed by the user. That means that the user inputs 6, for example. Now here you set your internal capacity to capacity -1 , which means it will be 5. Now if you do the modulo using the lower capacity, it will set the position to 0 even though it could technically put something in array[5]. Here is a print of your program run using Arrays.toString, printing your array after every addFront():

[null, 0, null, null, null, null]
0
[null, 0, 1, null, null, null]
0
[null, 0, 1, 2, null, null]
0
[null, 0, 1, 2, 3, null]
0
[4, 0, 1, 2, 3, null]
0
[4, 5, 1, 2, 3, null]
5

The solution to this issue is rather plain. Set your constructor to look like the following:

public ArrayDeque(int capacity) {

    this.array = (E[]) new Object[capacity];
    this.capacity = capacity;
    front = 1;
    end = 0;
    size = 0;
}

Furthermore, considering your FiFo issue: You might want to consider keeping better track of which element you added last and which should be returned. This could introduce two new variable but would make your life considerably easier. For example:

public void addFirst(E elem) throws DequeFullException {
    if (isFull())
        throw new DequeFullException("samlingen er full!");
    array[front] = elem;
    first = front;
    front = (front + 1) % (capacity); // use modulo to make sure the front restarts from initial position once it reaches capacity]
    size++;
    System.out.println(Arrays.toString(array));
}

Assume that first is an integer, which is set equal to 0 in the constructor. You can do this however you like, however this keeps better track of your first element.

Also your methods are a little problematic, considering that you are traversing an array backwards in a few of them, without considering the possibility of an ArrayOutOfBoundsException at -1. To solve that you might want to switch from having the end at [0] and the start at [1] to something that has the start in the middle. You have to find a way to place and return at the proper positions, maybe check if your variable, which you use for traversal is equal to 0 and if it is go to the other side of the array. Like this:

public E pullFirst() throws DequeEmptyException {
    if (isEmpty())
        throw new DequeEmptyException("Samlingen er tom!");
    if(front == 0)
        front = capacity;
    front = (front-1) % (capacity);
    size--;
    return array[front];
}

This produces the following output with this code in main():

public class Main {
    public static void main(String[] args) {
        ArrayDeque<Integer> arrDq = new ArrayDeque<>(6);

        for(int i = 0; i < 6; i ++)
        {
            arrDq.addFirst(i);
        }
        for(int i = 0; i < 6; i ++)
        {
            System.out.println(arrDq.pullFirst());
        }
    }
}

Output:

[null, 0, null, null, null, null]
[null, 0, 1, null, null, null]
[null, 0, 1, 2, null, null]
[null, 0, 1, 2, 3, null]
[null, 0, 1, 2, 3, 4]
[5, 0, 1, 2, 3, 4]
5
4
3
2
1
0

Do the same thing for the rear of your Deque and it should work just fine. I hope this helps.

Collectives™ on Stack Overflow

Deque implementation with circular array issue

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related