Как работает Enqueue и Dequeue в Связанной реализации очереди

Question

Как Enqueue обрабатывает специальный случай, когда цепочка начинается пустым и процесс Dequeue, когда цепочка начинается с одного узла.

Answer 1

OpenJDK implementation использует две хитрости:

1. Очереди содержит слепой элемент, который всегда присутствует, даже в пустой очереди. Слепой элемент всегда является первым элементом в очереди, но не видимым вне класса.

2. Очередь на самом деле является кольцом. Мы знаем, что мы достигли последнего элемента, когда currentElement.next == blind.

На следующем рисунке показана такая очередь длины 0 (слева) и длина qeue 1 (справа).

Преимущества использования этих уловок не являются:

• нет нулевых указателей
• нет, если-то еще для добавления/enqueuing элементы

Для демонтажа/Deque мы еще нужно проверить, пуста ли очередь.

Добавление

newElement.next = head.next; 
newElement.prev = head; 
newElement.prev.next = newElement; 
newElement.next.prev = newElement; 

Удаление

if (head.next == head) { 
    // ERROR, queue is empty 
} else { 
    removedElement.next.prev = removedElement.prev; 
    removedElement.prev.next = removedElement.next; 
} 

Обратите внимание, что это абсолютно возможно реализовать очередь без этих уловок, используя только один дополнительный оператор, если-иначе. Следующее изображение представляет собой наивную реализованную очередь длины 0 (слева) и длину 1 (справа).

Добавление

if (head == null) { 
    // queue is empty 
    head = newElement; 
} else { 
    // add to head 
} 

Удаление

if (head == null) { 
    // ERROR, queue is empty 
} else { 
    // remove from tail 
}