java - 关于 CTCI 的 Java 队列实现的问题

Question

我正在研究《破解代码面试第五版》中的队列实现。

enqueue的解释如下:

class Queue {
    Node first, last;

    void enqueue(Object item) {
        // This indicates the Queue is empty
        // so we set both first and last as 
        // the same item
        if(first == null) {
            last = new Node(item);
            first = last;
        } else {
            last.next = new Node(item);
            last = last.next;
        }
    }
}

我明白 if 语句中发生了什么。该条件处理空队列。因此，如果队列为空，并且我们尝试将项目添加到队列中，则添加的项目既是第一个项目也是最后一个项目。

但是，我不明白 else 语句中发生了什么。本书首先将该项指定为 last.next，然后将 last 指定为 last.next。这不会使最后一个元素和最后一个元素的下一个元素变得相同吗？另外，我还说明了队列。这是对 last 和 last.next 位置的准确说明吗？

[      |      |      |      ]

    ^     ^
  last  last.next

Answer 1

else部分的代码:

1: last.next = new Node(item);
2: last = last.next;

这是我们开始的 LL:

(a) -> (b) -> (c)
 ^first        ^last

我们调用enqueue(d)

第 1 行运行后:

(a) -> (b) -> (c) -> (d)
 ^first        ^last

因此我们看到第 1 行在列表末尾创建了一个新元素，但 last 仍然指向 (c)。

第 2 行运行后:

(a) -> (b) -> (c) -> (d)
 ^first               ^last

现在，last 指向 (d)，它相应地没有 next 节点。

你看，(c) 永远不会消失，它只是最后引用被移动 .

至于为什么它是这样工作的，这一切都归结于Java中对象是引用的事实。

考虑这段代码:

Object x = 300;
Object y = 500;
Object z = x;

//here, x = 300, y = 500, z = 300

x = y;
//now, x = 500, y = 500, z = 300
//because the actual object that x initially pointed to was not changed, only x as a reference was changed.

如果列表的大小分别为 n=0 和 n=1:

NULL
^first,last

NULL    (a)
^first   ^last

(a)
 ^first,last

然后另一个电话

(a)
 ^first,last
(a)     ->     (b)
 ^first,last

(a)     ->     (b)
 ^first         ^last

希望有帮助