c++ - 这个入队功能是如何工作的？

Question

我无法理解这一行:

rear->next = temp;

在这个队列函数中:

 void Queue::enqueue(int data) {

    Node *temp = new Node();    // make a temporary node
    temp->info = data;          // assign passed in data to it
    temp->next = 0;             // make it point to null

    if(front == 0)              // if there is no front node
        front = temp;           // make this a front node

    else                        // else, if there is already a front node
        rear->next = temp;      // make this rear's next pointer???? why?

    rear = temp;                // in any case make this a rear node

}

这样做不是更有意义吗？

    else                    // else, if there is already a front node
        temp->next = rear;  // make temp point to REAR; not other way around

    rear = temp;                // make temp a new rear node

Answer 1

rear 指向最后一个元素。想要的是将 temp 放在当前 rear 之后，然后移动 rear 指向新放置的最后一个元素。因此，如果我们想要将 4 加入队列 (1, 2, 3)，我们需要:

1 -> 2 -> 3 -> 4
|              |
front          rear

您的解决方案让 temp 在当前 rear 前面切入，然后将 rear 移动到切入位置。它甚至没有正确切割，因为 rear 之前的项目仍然指向原始 rear。 rear 不再指向最后一项，因此您的队列将处于不一致状态。

1 -> 2 -> 3
|      4 -^
|      |
front  rear