堆栈如何在链接结构中工作

Question

我了解以下大多数代码，但是我不清楚POP方法的工作原理。我不明白为什么当称为top.getnext((时，它会返回上一个节点。推送方法同样的东西。为什么要调用temp.setnext(top(，然后将顶部分配给temp？

public class Stack {
private Node top;
public Stack()
{
    top = null;
}
public void push(int v)
{
    Node temp = new Node();
    temp.setValue(v);
    temp.setNext(top);
    top = temp;
}
public int peek()
{
    return top.getValue();
}
public int pop()
{
    int temp = top.getValue();
    top = top.getNext();
    return temp;
}
public boolean isEmpty()
{
    return(top == null);
}
public void makeEmpty()
{
    top = null;
}
}
public class Node {
private int value;
private Node next;
public void setValue(int v)
{
    value = v;
}
public int getValue()
{
    return value;
}
public void setNext(Node n)
{
    next = n;
}
public Node getNext()
{
    return next;
}
}

设置下一个代码真正使我感到困惑。

Answer 1

堆栈数据结构以 lifo (首先出现(。

。

牢记这一点，上面的代码以每个添加的节点将节点指向堆栈顶部的方式进行构造。TOP将分配给该新添加的节点。这是使用setNext ()方法提供的。使用相同的逻辑，当节点弹出时；它的下一个节点是在它之前添加的一个节点，将是新的顶级节点。

例如，考虑堆栈是空的。添加第一个节点时，顶部将引用此节点。当添加第二个节点时，根据LIFO应该是新顶部。因此，当将其添加到堆栈中时，其下一个节点将指向当前顶部节点，第一个节点。之后，顶部将引用此新节点。这里将下一个节点设置为先前添加的节点可以帮助我们找到新的顶级节点，如果我们弹出此新添加的节点。

Answer 2

说您想将值1,2,3,4推到堆栈上：

push(1(：stack = {1} |顶是1

push(2(：stack = {2 =＆gt;1} |顶是2

push(3(：stack = {3 =＆gt;2 =＆gt;1} |顶是3

push(4(：stack = {4 =＆gt;3 =＆gt;2 =＆gt;1} |顶部是4

为了在添加节点时获得其行为，您必须构造一个新节点，在这种情况下，将值设置为添加值的值。现在，由于该节点将是新顶部，因此指出的节点应该是堆栈的当前顶部。因此， setNext(top(; 。现在，要使新节点成为堆栈的顶部，您必须通过 top = temp; 。

相应地设置它。

现在，如果我们从上面的堆栈中弹出一个值：

pop((：返回值= 4 |stack = {3 =＆gt;2 =＆gt;1} |顶是3

为了获得此行为，我们获得了堆栈当前顶部的值，因此 int temp = top.getValue((; 。现在，我们不希望此节点成为顶部，我们希望新顶部是当前顶部指向的节点，因此 top = top.top.getnext((; 。剩下的就是返回我们存储在温度中的值，并且我们已经正确弹出了堆栈。

Answer 3

要回答您的问题，让我们回顾一下堆栈在概念上的工作方式。让我举个例子。

假设您正在洗碗。在此示例中，我们一次只能洗1盘。第一次清洁菜时，您将其放在柜台上。您清洁的下一个菜最重要的是。每次清洁菜时，它是现有菜肴的顶部。您清洁的最后一道菜总是在堆栈的顶部，而较旧的菜肴依次在堆栈上延伸。底菜是先清洗的菜。

现在，如果有人来并需要一道干净的菜，他们将不会尝试从烟囱中拉出底菜。他们只会拿出堆栈的顶菜。换句话说，他们将进行流行操作。

让我们以另一个例子为例。说我们按照那个顺序将鸟，鱼，狗和猫推入一堆。看起来像这样

Stack after bird, fish, dog pushed
----------------------------------
top:    dog
        fish
bottom: bird
Stack after cat pushed
----------------------
top:    cat
        dog
        fish
bottom: bird        
Stack after a pop operation
---------------------------
top:    dog
        fish
bottom: bird

当我们从堆栈顶部弹出猫时，狗将成为新的顶部。我们知道这一点，因为我们可以看到整个堆栈。但是，代码无法看到整个堆栈。因此，代码做一些聪明的事情。

当将新动物推到烟囱上时，旧的顶部将与刚刚添加的动物一起存放。换句话说，猫记得狗曾经是顶部。为什么？这样，如果我们弹出猫，顶部将恢复到过去的猫。

这就是top.getnext((返回的 - pop之后的旧顶部是pop的分配。过去的顶部已成为当前顶部。我们现在知道狗是堆栈的顶部。

这是什么记忆，以便top.getnext((会返回旧顶？这是由执行推动时发生的temp.setnext(顶部(完成的。当添加猫时，在更新猫之前，旧的顶部是用猫保存的。