up vote 3 down vote favorite

After learning about linked list implementations of a queue I was asked to try a resizing array implementation. I'm looking for constructive criticism.

import java.util.NoSuchElementException;

/**
 * ResizingQueue - Resizing Array Implementation.
 *
 * @author Rocky
 * @version 2016-05-31 
 */
public class ResizingQueue<Item> {

    private Item[] queue;
    private int size;
    private int index;

    public ResizingQueue() {
        queue = (Item[]) new Object[1];
        size = 0;
        index = 0;
    }

    /**
     * Returns the size of the queue
     *
     * @return Integer representing the number of items in the queue
     */
    public int size() {
        return this.size;
    }

    /**
     * Returns whether or not the queue is empty
     *
     * @return True if the queue is empty
     */  
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * Adds an item onto the end of the queue. If the size of the queue reaches
     * the length of the array, the length of the array is doubled.
     *
     * @param item Item to be added. Must not be null
     * @throws NullPointerException if the parameter item is null
     */
    public void enqueue(Item item) {
        if (item == null) {
            throw new NullPointerException("Item must not be null");
        }
        if (size == queue.length) {
            resize(2 * queue.length);
        }
        queue[size + index] = item;
        size++;
    }

    /**
     * Removes and returns the item at the front of the queue. If the size of
     * the queue reaches 25% of the length of the array, the length of the array
     * is halved.
     *
     * @return Item at the front of the queue
     * @throws NoSuchElementException if dequeue() is called while the queue is
     * empty
     */
     public Item dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("There is nothing in the queue");
        }
        if (size < queue.length / 4) {
            resize(queue.length / 2);
            index = 0;
        }
        Item item = queue[index];
        queue[index++] = null;
        size--;
        return item;
    }

    /**
     * Resizes the array when capacity reaches 100% or 25%
     *
     * @param capacity New capacity for the array
     */
    private void resize(int capacity) {
        Item[] copy = (Item[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            copy[i] = queue[i + index];
        }
        queue = copy;
    }

}
share|improve this question
up vote 2 down vote accepted

Your code looks good, but can be improved. 

/**
 * Resizes the array when capacity reaches 100% or 25%
 *
 * @param capacity New capacity for the array
 */
private void resize(int capacity) {
    Item[] copy = (Item[]) new Object[capacity];
    for (int i = 0; i < size; i++) {
        copy[i] = queue[i + index];
    }
    queue = copy;
}

The javadoc states that this method would resize the array when the capacity reaches a specific value which isn't correct. This method resizes the underlaying buffer no matter what capacity it has.

This javadoc is lying. After removing the lying part only Resizes the array is left as description which basically doesn't add any value because it is obvious.

I would remove that javadoc completely and rename the method to resizeInternalBuffer.

enqueue()

/**
 * Adds an item onto the end of the queue. If the size of the queue reaches
 * the length of the array, the length of the array is doubled.
 *
 * @param item Item to be added. Must not be null
 * @throws NullPointerException if the parameter item is null
 */

Without reading the code I see that this method (and the dequeue() method as well) is doing too much. I would extract the checking for the size to separate methods like so 

private void ensureCapacityMax() {
    if (size == queue.length) {
        resize(2 * queue.length);
    }
}

private void ensureCapacityMin() {
    if (size < queue.length / 4) {
        resize(queue.length / 2);
    }
}

which are then called like 

public void enqueue(Item item) {
    if (item == null) {
        throw new NullPointerException("Item must not be null");
    }

    ensureCapacityMax();

    queue[size + index] = item;
    size++;
}

By using lambda expressions you could simplify this to one method.

I don't really like the usage of index for enqueue() and dequeue(). A much cleaner way would be to use head and tail like so 

private int head = 0;
private int tail = 0;  

public void enqueue(Item item) {
    if (item == null) {
        throw new NullPointerException("Item must not be null");
    }

    ensureCapacityMax()

    queue[tail] = item;
    tail = (tail + 1) % queue.length;
    size++;
}


public Item dequeue() {
    if (isEmpty()) {
        throw new NoSuchElementException("There is nothing in the queue");
    }

    ensureCapacityMin()

    Item item = queue[head];
    queue[head] = null;
    head = (head + 1) % queue.length;
    size--;
    return item;
}

now we need to adjust the resize() method like so by the usage of System.arraycopy() 

private void resize(int capacity) {
    Item[] copy = (Item[]) new Object[capacity];

    if (size > 0) {
        if (head < tail) {
            System.arraycopy(queue, head, copy, 0, size);
        } else {
            System.arraycopy(queue, head, copy, 0, queue.length - head);
            System.arraycopy(queue, 0, copy, queue.length - head, tail);
        }
    }

    queue = copy;
    head = 0;
    tail = (size == capacity) ? 0 : size; 
}

I didn't test this implementation but it should work well.

share|improve this answer
    
Regarding the internal buffer, what exactly are you referring to? The empty space in the array perhaps? If so, what would you call the array itself and when you say "This method resizes the underlaying buffer no matter what capacity it has.", I don't see how that statement is true if the method is only called when the array reaches a specified capacity. – Rocky Jun 6 '16 at 4:20
    
A javadoc should express what a method is doing unless it is obvious. The javadoc shouldn't express on what condition it will be called. I would just remove the javadoc in question. – Heslacher Jun 6 '16 at 5:24
up vote 1 down vote

Readibility

In the intrest of making it more readable, I would recommend removing magic numbers which are critical to your implementation.

From enqueue we have:

if (size == queue.length) { resize(2 * queue.length); }

This is effectively the loadfactor for your resizing. If you wish to change this in the future you would have to look deep through the code (if it extends) to change it. A set of private const ints with a meaningful name would help.

Exception Safety

If you look at standard queue implementations they have a front method to get the element from the front of the queue and then have a deque or pop to remove an item. This guarantees strong exception safety if things go wrong. Herb and Sutter explains this very well with a stack implementation.

Consider the code:

1.Item i(q.dequeue());

2.Item j;

3.j = s.dequeue();

Item i gets initialized with dequeue value. Now if the assignment operator fails on the dequeue for some odd reason (memory etc). The queue is now in an inconsistent state. It has removed the element without i being properly initialized.

When the line 3 executes we now have no element for j and that throws an exception

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.