了解链表队列的入队方法

Question

我很难理解linkedlist队列的enqueue方法的代码。我理解dequeue()、isEmpty()、First()和size（）。首先，这里有一个LinearNode类来创建新的节点对象：

public class LinearNode<T> {
    private T element;
    private LinearNode<T> next;

    /**
     * Constructor: Creates an empty node.
     */
    public LinearNode() {
        next = null;
        element = null;
    }

    /**
     * Constructor: Creates a node storing the specified element.
     * @param elem  The specified element that is to be kept by this LinearNode.
     */
    public LinearNode(T elem) {
        next = null;
        element = elem;
    }

    /**
     *  Returns the node that follows this one.
     * @return  The node that follows this one.
     */
    public LinearNode<T> getNext() {
        return next;
    }

    /**
     *  Sets the node that follows this one.
     * @param node  The node which is to follow this one.
     */
    public void setNext(LinearNode<T> node) {
        next = node;
    }

    /**
     *  Returns the element stored in this node.
     * @return  The element that is kept within this node.
     */
    public T getElement() {
        return element;
    }

    /**
     *  Sets the element stored in this node.
     * @param elem  The element that is to be kept within this node.
     */
    public void setElement(T elem) {
        element = elem;
    }
}

下面是Enqueue方法

public void enqueue(T element) {
    LinearNode<T> tmp = new LinearNode<T>(element);
    if (isEmpty()) {
        // set-up front to point to the new node
        front = tmp;
    } else {
        // add the node after the old tail node
        rear.setNext(tmp);
    }
    // update rear to point to the new node
    rear = tmp;
    count++; // increment size
}

在此编辑包含Enqueue方法的LinkQueue类：

public class LinkedQueue<T> implements QueueADT<T> {
private LinearNode<T> front; // front node of the queue
private LinearNode<T> rear;  // rear node of the queue
private int count;           // the current size of the queue

/**
 * Constructor: Creates an empty Queue.
 */
public LinkedQueue() { 
    count = 0;
    /* the following assignments are not actually necessary as references
     *  are initialised automatically to null, 
     *  but they are included for clarity.
     */
    front = null;
    rear = null;
}

Answer 1

根据我从代码中所能理解的，前面和后面只是指针。它们用于指向队列的第一个和最后一个节点。所以当你说：

rear.setNext(tmp);

您正在将新节点标记在队列的最后一个节点之后。

考虑以下队列：1,2,3,4

enqueue(5)

rear=tmp导致rear=5将后指针重置到最后一个节点