将栈顶放在链接链的末尾而不是开始

Question

我正在解决一个问题:使用链接链创建一个堆栈，该链将新条目(堆栈顶部)放在链的末尾，而不是开始。解决方案的一部分涉及维护对第一个和最后一个节点以及倒数第二个节点的引用。而且，我不能遍历链。我想不出一个解决方案因为我想不出一种方法来更新引用到最后一个节点的下一个节点当顶部条目从堆栈中弹出时?

这是一个教科书式的问题。链的开头包含对下一个节点的引用。链对下一个节点的引用的末尾为null)

Answer 1

开始和结束是抽象的术语。只需初始化一个节点以包含第一个元素。如下所示:

Node tail = null;
..
..

然后添加一个新节点。

public void push(T val) {
Node = new Node(val);
Node.next = tail;
tail = node;
}

你把它加到tail然后新的node变成了tail。然后，当您遍历它时，您只需从尾部开始，并使用next引用向头部移动。

弹出堆栈

public T pop() {
if (tail != null) {
object = tail.object;
tail = tail.next;  
}
return null;
}

您将需要创建一个泛型类Node。你可能想要一个isEmpty()方法。