#java #data-structures #queue
#java #структуры данных #очередь
Вопрос:
Как Enqueue обрабатывает особый случай, когда цепочка начинается с пустого, и процесс удаления из очереди, когда цепочка начинается с одного узла.
Комментарии:
1. О какой реализации вы говорите? Вы просмотрели исходный код? Что вас смущает в этом случае?
2. Я хочу понять, каков процесс постановки в очередь и удаления из очереди при связанной реализации..
Ответ №1:
Реализация OpenJDK использует два приема:
-
Очередь содержит слепой элемент, который всегда присутствует, даже в пустой очереди. Слепой элемент всегда является первым элементом в очереди, но не виден извне класса.
-
Очередь на самом деле является кольцом. Мы знаем, что мы достигли последнего элемента, когда
currentElement.next == blind.
На следующем рисунке показана такая очередь длиной 0 (слева) и qeue длиной 1 (справа).
Преимущества использования этих приемов:
- нет нулевых указателей
- нет if-else для добавления / постановки в очередь элементов
Для удаления / удаления нам все равно нужно проверить, пуста ли очередь.
Добавление
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;
}
Обратите внимание, что абсолютно возможно реализовать очередь без этих трюков, используя только один дополнительный оператор if-else .
На следующем рисунке представлена наивно реализованная очередь длиной 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
}