Метод постановки очереди в очередь с использованием массива в Scala

Question

def enqueue(elem: T): Unit = {      
    A(rear) = elem
    rear += 1
    size += 1
    if (size == 0) {
        front = 0 
        rear = 0
        }
    if (size == A.length) {
        grow()
        }   
    }

Я реализую очередь, используя массив, и у меня возникла проблема с методом enqueue, но я не мог понять, где именно ошибка. Так что вы можете дать мне несколько советов, где я допустил ошибку. В приведенном выше коде размер - это число элементов в очереди массива, а функция Grow - функция, которая удваивает массив при его заполнении. Заранее спасибо.

Answer 1

Если вы собираетесь проверить на size == 0, вы должны сначала сделать это.

Это может помочь вам, если вы задокументируете инварианты вашего класса, а также предварительные условия и постусловия ваших методов, чтобы гарантировать, что каждый метод сохраняет ключевые свойства ваших внутренних объектов реализации очереди. Смотри http://en.wikipedia.org/wiki/Design_by_contract.

Инвариант может быть что-то вроде размер всегда меньше или равен длине массива или размер> = 0 .

Answer 2

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

Тест size == 0 кажется бесполезным, размер не будет нулевым сразу после enqueue. Однако то, что вы делаете, говорит о том, что вы делаете, когда происходит удаление, вероятно, верните элемент в front с шагом front и уменьшением size.

Итак, несколько замечаний

1. Удивительно, что звонки растут превентивно, для следующего звонка ставить в очередь, что может никогда не произойти. Вы, вероятно, должны сделать это на самое начало очереди, когда вам не хватает места
2. Ваши данные перемещаются вправо от массива по мере удаления из очереди и повторной постановки в очередь. Таким образом, даже в очереди с очень небольшим количеством элементов (размер маленький), элементы могут располагаться по правому краю массива, и вам может не хватить места. Тест на рост (или, по крайней мере, на то, чтобы что-то сделать) должен быть сзади, а не по размеру.
3. Как следствие, вам, возможно, придется расти или, по крайней мере, что-то делать, даже если в массиве гораздо больше места, чем необходимо. Если массив почти заполнен, вы должны действительно расти (даже если осталось немного места, в противном случае вы рискуете циклами постановки / снятия с очереди, чтобы продолжить копирование всех значений и заставить ваши показатели идти O (N)) Но если есть много свободного места, вы должны просто переместить элементы обратно в начало массива.

Резюме: в начале очереди, если задняя часть имеет длину массива, вы должны

• если размер меньше, чем, скажем, половина пространства, скопируйте элементы в начало массива, front = 0, back = size
• если размер больше, выделить новый массив и скопировать элементы в начале нового массива