ResizableArray на основе реализации очереди


Я реализовать базовые структуры данных в Java. Я написал этот простой изменение размера очереди массива внедрения и ищет способы для упрощения реализации, как это выглядит я использую слишком много переменных, которые могут быть сокращены. Я бы признателен за любые идеи, чтобы сделать его проще, рекомендации и конструктивную критику.

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


120
1
задан 4 марта 2018 в 03:03 Источник Поделиться
Комментарии
1 ответ


    private T[] mQueue;
private int mHead, mTail, mCurrentSize, mSize;

Значение, которое вы храните в mSize доступно mQueue.length.

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

Но если вам избавиться от mSizeтогда нет причин для проведения различия mCurrentSize. Так что просто назвать это mSize.

Вы также не нужно mTailкак mHead, mSizeи mQueue.length определить mTail однозначно.

Вам не нужен конструктор, как вы можете инициализировать эти значения без дальнейших вычислений.


        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;


Есть встроенные для этого.

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

Теперь вам не newQueue или mCurrent.

Как ранее сказал, вам не нужно mSize или 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;
}


Для реализации, вы можете сделать это, как

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

С помощью <= или >= а не строгое равенство, мы можем поймать ситуациях, когда размер перепрыгнули стробирования. Например, если вы реализовали QueueIterator.remove без вызова deQueueвы можете обнаружить, что у вас пропустили resize проверить.

Посмотрим, как нам определить значение, которое будет проведено в mTail по мере необходимости, а не поддержание его.

Обратите внимание, как легче, если мы сохраним mHead как индекс, а не позволяя ему увеличиваться в размере. Обратите внимание, что это также позволяет избежать целочисленного переполнения в пограничном случае (если вы никогда не изменить, mHead всегда растет).

0
ответ дан 4 марта 2018 в 11:03 Источник Поделиться