关于来自 CTCI 的 Java 队列实施的问题

Question

我正在看破解代码面试第 5 版中的 Queue 实现。

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) 永远不会消失，只是 last reference 即 moved .

至于为什么是这样的，归结为对象是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

希望对您有所帮助

关于来自 CTCI 的 Java 队列实施的问题

Questions regarding a Java Queue implementation from CTCI

java

queue