使用链表排队——这应该如何工作?

Question

我很难理解这个数据结构。在我的课程中，我们使用以下代码来使用链表实现Queue:

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|指针指向尾部]，尾部[x|null]

如果我们现在调用.dequeue(), sentinel.next就是null。

我问我的讲师关于这一点，我得到了以下回复，这并没有真正使它更清楚我:"当我们通过Queue q = new Queue();调用构造函数时，我们将创建虚拟项目sentinel，其值为零，其下一个指针为空。同时我们让尾巴指向哨兵。因此，向队列中添加元素显然不是问题。"

我不知道我们在哪里让let尾巴指向哨兵:/

Answer 1

事实上，你的直觉是正确的。这个类不能正常工作。

当你排队的东西，它工作得很好-在尾部添加东西，一切都工作。

当你把所有的东西都拿出来排队时，麻烦就开始了。当您这样做时，sentinel.next将变成null -您已经从队列中删除了所有内容-但tail仍将指向您进入队列的最后一个项目。所以基本上你有一个与sentinel断开的尾巴。

你可以排队的东西，它将被附加在旧尾巴之后，但它将不再从sentinel访问。如果您尝试进一步取消队列，您将获得NullPointerException .

为了演示这一点，我将以下方法添加到您的Queue类中(并且添加了Item类，因为您没有将其放在您的帖子中):

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

你

:

<>以前队列:[5][10]队列:[10]队列:队列:线程"main"中的异常在testing.Queue.dequeue (SimpleTest.java: 48)在testing.SimpleTest.main (SimpleTest.java: 27)之前

你应该得到的是:

<>以前队列:[5][10]队列:[10]队列:队列:[15][20]队列:[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; 
}

如果我们没有null检查，那么sentinel将在我们尝试脱队列时变成null，然后我们将永远无法再次脱队列。通过null检查，我们确保有一个项目需要退出队列，它成为哨兵。如果它恰好是队列中的最后一项，那么tail和sentinel就像开始时一样指向同一项，所以我们知道我们可以继续添加项，并且可以通过sentinel访问它们。

请注意，在尝试退出队列之前检查队列是否为空的方法也会派上用场。

Answer 2

如果我们现在调用.dequeue()，哨兵。Next仍然指向null。这是不对的。Senitel只在构造函数中初始化，不会再改变。

所以，在构造函数之后，你得到- (Senitel) -> null，这里tail指向Senitel。你调用enqueue，它就变成。(element) -> (Element1) -> null。这里，tail指向Element1，而Senitel仍然指向(Senitel)。你调用dequeue，它变成(Senitel) -> null