java-如何在使用链表实现的堆栈中实现弹出操作？

Question

我目前正在使用 Java 来完成一个测试模块，该模块涉及使用链表实现堆栈。

我已经实现了push()操作，但是对于pop()操作我没有得到正确的结果。我尝试如下:

public class LLStack implements LLStackQInterface{
SintNode head = new SintNode(0);
@Override
public void push(int num) {

head.nextNode = new SintNode(num);
head = head.nextNode;
}

@Override
public int pop() {

    SintNode t = head;
    while(t.nextNode!=null)
    {
        t=t.nextNode;

    }
    t = null;
    return 0;

}

我必须推出最新的元素，因此我使用指针导航到列表中的最后一个元素，但我没有得到结果!

我确实得到了这个结果:

Failed for the input: PUSH 1 PUSH 3 POP PUSH 4 PUSH 6
POP PUSH 8 PUSH 9 POP
Expected output is: 8->4->1->NULL

Actual output generated by your code: 9->8->6->4->3->1->NULL

我设法反转列表，但显然我的 pop() 不起作用。我该怎么办？

Answer 1

您的 pop 和 push 方法都存在错误。

您在 push 中对下一个指针的管理不正确。首先将当前head的next指针设置为新节点，然后将新节点分配给head。因此，head.next == null。正确的做法是:

public void push(int num) {
        SintNode n = new SintNode(num);
        n.next = head;
        head = n;
}

这样，您可以将新节点插入到列表的前面，并维护一个指向下一个元素的指针，即列表的前一个头。

在 pop 方法中，您将遍历到列表的末尾。这是不正确的，因为您将元素添加到列表的前面。堆栈是一种 LIFO(后进先出)数据结构，这意味着您应该删除最后插入的元素。在本例中，它是列表的头部。

public int pop() {
        if (head == null)
           return 0;

        SintNode t = head;
        head = t.next;
        t = null;
        return 0;

}

这里，我们首先将新的head设置为head.next，然后删除当前的head。

我运行了更正后的版本，实际输出与预期输出相符。