1
\$\begingroup\$

I am implementing basic data structures in Java. I have written this simple resizing array queue implementation and looking for ways to simplify the implementation as it looks like I am using too many variables which can be reduced. I would appreciate any ideas to make it simpler, implementation advice and constructive criticisms.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ResizingArrayQueue<T> implements Iterable<T>{
    private T[] mQueue;
    private int mHead, mTail, mCurrentSize, mSize;

    public Iterator<T> iterator() {
        return new QueueIterator();
    }

    public ResizingArrayQueue() { 
        mQueue = (T[]) new Object[1];
        mHead = 0;
        mSize = 1;
        mTail = mSize - 1;
        mCurrentSize = 0;
    }

    public void enQueue(T valueToEnque){
        if (mCurrentSize == mSize) {
            resize(2 * mSize);
        }
        mTail = ++mTail % mSize;
        mQueue[mTail] = valueToEnque;
        mCurrentSize++;
    }

    public T deQueue(){
        if(mCurrentSize == mSize / 4) {
            resize(mSize / 2);
        }
        T value = mQueue[mHead % mSize];
        mQueue[mHead % mSize] = null;
        mHead++;
        mCurrentSize--;
        return value;
    }

    public boolean isEmpty() {
        return mCurrentSize == 0;
    }

    public void resize(int size){
        T[] newQueue = (T[]) new Object[size];
        int mCurrent = 0;
        while(mCurrent < mCurrentSize){
            newQueue[mCurrent] = mQueue[(mCurrent + mHead) % mSize];
            mCurrent++;
        }

        mQueue = newQueue;
        mSize = size;
        mHead = 0;
        mTail = mCurrentSize - 1; 
    }

    private class QueueIterator implements Iterator<T> {
        private int mCurrent = 0;

        public boolean hasNext() {
            return mCurrent < mCurrentSize;
        }

        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            T valueToReturn = mQueue[(mCurrent + mHead) % mSize];
            mCurrent++;
            return valueToReturn;
        }

        public void remove(){
            throw new UnsupportedOperationException();
        }
    }
}
\$\endgroup\$
0
\$\begingroup\$
    private T[] mQueue;
    private int mHead, mTail, mCurrentSize, mSize;

The value that you are storing in mSize is available as mQueue.length.

    private T[] mQueue = (T[]) new Object[1];
    private int mHead = 0;
    private int mSize = 0;

But if you get rid of mSize, then there is no reason to differentiate mCurrentSize. So just call that mSize.

You also don't need mTail, as mHead, mSize, and mQueue.length determine mTail uniquely.

You don't need a constructor, as you can initialize these values without further calculation.

        T[] newQueue = (T[]) new Object[size];
        int mCurrent = 0;
        while(mCurrent < mCurrentSize){
            newQueue[mCurrent] = mQueue[(mCurrent + mHead) % mSize];
            mCurrent++;
        }

        mQueue = newQueue;
        mSize = size;
        mHead = 0;
        mTail = mCurrentSize - 1; 

There's a built-in for this.

        mQueue = Arrays.copyOfRange(mQueue, mHead, mHead + size);
        mHead = 0;

Now you don't newQueue or mCurrent.

As previously said, you don't need mSize or mTail.

    public void enQueue(T valueToEnque){
        if (mCurrentSize == mSize) {
            resize(2 * mSize);
        }
        mTail = ++mTail % mSize;
        mQueue[mTail] = valueToEnque;
        mCurrentSize++;
    }

    public T deQueue(){
        if(mCurrentSize == mSize / 4) {
            resize(mSize / 2);
        }
        T value = mQueue[mHead % mSize];
        mQueue[mHead % mSize] = null;
        mHead++;
        mCurrentSize--;
        return value;
    }

To implement, you could do it like

    public void enQueue(T valueToEnque) {
        if (mSize >= mQueue.length) {
            resize(2 * mQueue.length);
        }

        mQueue[(mHead + mSize) % mQueue.length] = valueToEnque;
        mSize++;
    }

    public T deQueue() {
        if (mSize <= mQueue.length / 4) {
            resize(mQueue.length / 2);
        }

        T value = mQueue[mHead];
        mQueue[mHead] = null;
        mHead = ++mHead % mQueue.length;
        mSize--;

        return value;
    }

By using <= or >= rather than strict equality, we can catch situations where the size jumped over the gating. For example, if you implemented QueueIterator.remove without calling deQueue, you might find that you had skipped over the resize check.

See how we determine the value that would have been held in mTail as needed rather than maintaining it.

Notice how things are easier if we maintain mHead as the actual index rather than allowing it to grow unbounded. Note that this also avoids integer overflow in an edge case (if you never resize, mHead always grows).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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