Очередь с использованием связанных списков - как это должно работать?

Question

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

class Queue 
{ 
    private Item sentinel , tail; 

    public Queue() { 
     sentinel = new Item(0,null); 
     tail = sentinel; 
    } 

    public void enqueue(int value) { 
     tail.next = new Item(value , null); 
     tail = tail.next; 
    } 

    public int dequeue() 
    { 
     int value = sentinel.next.value;​ 
     sentinel.next = sentinel.next.next; 
     return value; 
    } 
} 

Я не вижу, как это должно работать, когда мы вызываем метод конструктора мы sentinel[0|null], а затем мы позволяем tail=sentinel, так tail[0|null] , Позвонив .enqueue(x), мы получим следующее:

[0|pointer to tail],  tail[x|null]

Если мы теперь называем .dequeue(), sentinel.next является null.

Я спросил у своего преподавателя об этом, и я получил следующий ответ, который на самом деле не дает мне ясности: «Когда мы вызываем конструктора через Queue q = new Queue();, мы создадим фиктивный элемент, чье значение равно нулю и чья следующий указатель равен нулю. В то же время мы позволяем хвосту указывать на дозорный сигнал. Поэтому четкое добавление элементов в очередь не является проблемой ».

Я не вижу, где мы позволяем пусть хвостовую точку к часовому:/

Answer 1

Если мы теперь называем .dequeue(), sentinel.next все еще указывает на нулевое значение. Это неправильно. senitel только инициализируется в конструкторе и больше не изменяется.

Итак, после connstructor вы получаете - (Senitel) -> null, а вот хвост указывает на Сенителя. Вы звоните enqueue и становится. (Senitel) -> (Element1) -> null. Здесь хвост указывает на Элемент 1, и Сенитель все еще указывает на (Сенитель). Вы вызываете dequeue, и он становится (Senitel) -> null.

Answer 2

Ваша интуиция, по сути, правильная. Этот класс работает неправильно.

Когда вы вставляете вещи, это хорошо работает - добавляет вещи в хвост, и все работает.

Проблема начинается, когда вы деактивируете все предметы. Когда вы это сделаете, sentinel.next станет null - вы удалили все из очереди - но tail все равно укажет на последний элемент, который вы указали. Таким образом, в основном у вас есть хвост, который отключен от вашего sentinel.

Затем вы можете вставить в очередь, и он будет добавлен после старого хвоста, но он больше не будет доступен от sentinel. Если вы попытаетесь удалить что-либо еще, вы получите NullPointerException.

Чтобы продемонстрировать это, я добавил следующий метод для вашего Queue класса (и добавил предмет класса, так как вы не поставить его в должности):

@Override 
public String toString() { 
    StringBuilder sb = new StringBuilder("Queue: "); 
    for (Item item = sentinel.next; item != null; item = item.next) { 
     sb.append('[').append(item.value).append(']'); 
    } 
    return sb.toString(); 
} 

Теперь, с этой основной программой:

public static void main(String[] args) { 

    Queue queue = new Queue(); 
    queue.enqueue(5); 
    queue.enqueue(10); 
    System.out.println(queue); 
    queue.dequeue(); 
    System.out.println(queue); 
    queue.dequeue(); 
    System.out.println(queue); 
    queue.enqueue(15); 
    queue.enqueue(20); 
    System.out.println(queue); 
    queue.dequeue(); 
    System.out.println(queue); 
} 

вы получаете:

Queue: [5][10] 
Queue: [10] 
Queue: 
Queue: 
Exception in thread "main" java.lang.NullPointerException 
     at testing.Queue.dequeue(SimpleTest.java:48) 
     at testing.SimpleTest.main(SimpleTest.java:27) 

Что вы должен получили был:

Queue: [5][10] 
Queue: [10] 
Queue: 
Queue: [15][20] 
Queue: [20] 

Для достижения этой цели, вы должны исправить хвост, когда вы достигнете его, когда извлечение из.

public int dequeue() 
{ 
    int value = sentinel.next.value; 
    if (sentinel.next == tail) { 
     tail = sentinel; 
    } 
    sentinel.next = sentinel.next.next; 
    return value; 
} 

На самом деле, нужно также защитить метод dequeue() против вызывается, когда очередь пуста. Бросать NullPointerException не приятно, более разумное исключение было бы приятнее. И на самом деле это помогает создать более элегантный dequeue(), где вместо того, чтобы исправлять хвост, мы просто изменить часовой - выбросить старые дозорный и использовать этот пункт мы только из очереди как наш новый страж:

public int dequeue() 
{ 
    int value = sentinel.next.value; 
    if (sentinel.next == null) { 
     throw new IllegalStateException("No items to dequeue"); 
    } 
    sentinel = sentinel.next; 
    return value; 
} 

если мы не проверял нуль, тогда sentinel стал бы null, когда мы попытаемся удалить из очереди, а затем мы больше не сможем снова выполнить деактивацию. Путем проверки нулевого кода мы убеждаемся, что у нас есть элемент для удаления из очереди, и он становится часовым. Если это также последний элемент в очереди, то у нас есть tail и sentinel, указывающие на тот же элемент, что и в начале, поэтому мы знаем, что мы можем продолжать добавлять элементы, и они будут доступны через sentinel.

Обратите внимание, что метод проверки того, была ли очередь пуста, до, пытающаяся выполнить деинструмент, также пригодится.