java - 在用户定义的 LinkedList 中创建 push 和 pop 方法

Question

最近我类在学习ArrayLists和LinkedLists。上周我们收到了一项任务，要求我们在 LinkedList 堆栈类中创建 push 和 pop 方法。我了解堆栈背后的逻辑，因此它是后进先出的，但我在实际代码中遇到了麻烦。我对计算机科学还很陌生(这是我有史以来的第二门类(class))，这项特殊的作业确实让我抓狂。我已经交了这个作业，但我们下周有期中考试，我想好好完成。我一直在网上和我的教科书上寻找帮助，但一无所获。我的教授只将我推荐给助教，而助教只关心帮助我处理逻辑，而不是实际的代码。我将在下面发布我的教授给我的说明，以及我目前的代码。提前致谢。

来自教授:

使用下面Java给出的模板实现栈文件:

CS401StackInterface.java CS401StackLinkedListImpl.java

public interface CS401StackInterface<E>
{
   /**
    * Get the top element on the stack.
    * 
    * @return the first element on the stack.
    */
   public E pop();

   /**
    * Adds an element on the top of the stack.
    * 
    * @param e - The element to be added to the stack.
    */
   public void push(E e);

   /**
    * Determines the number of elements in this data structure.
    * 
    * @return the number of elements currently resident in this
    *         data structure.
    */
   public int size();
}

这是我尝试定义方法的实际类:

public class CS401StackLinkedListImpl<E> implements CS401StackInterface<E> 
{
    private LinkEntry<E> head;
    private int num_elements;

    public CS401StackLinkedListImpl()
    {
        head = null;
        num_elements = 0;
    }

    public void setElement(LinkEntry<E> anElement){
        head = anElement;
    }

    /*Append the new element to the end of the list*/
    public void push(E e)
    {
        LinkEntry<E> temp = new LinkEntry<E>();
        temp.element = e;
        temp.next = head;
        head = temp;
    }

    /*Remove the most recently pushed element at the end of the list*/
    public E pop()
    {
        head.next = head;
        num_elements--;
        return (E) head;
    }

    public int size()
    {
        LinkEntry<E> temp = new LinkEntry<E>();
        for (temp = head; head != null; head = head.next)
            num_elements++;
        return num_elements;
    }

    public String toString()
    {
        String string = "";
        LinkEntry<E> temp = new LinkEntry<E>();
        for (temp = head; temp != null; temp = temp.next)
        {
            string += temp.element.toString() + "";
        }
        return string;
    }

/* ------------------------------------------------------------------- */
/* Inner classes                                                      */
    protected class LinkEntry<E>
    {
        protected E element;
        protected LinkEntry<E> next;

        protected LinkEntry() { element = null; next = null; }
    }
}

最后，这是我测试方法的主类:

import java.util.*;

public class App {

    public static <E> void main(String[] args) {

        CS401StackLinkedListImpl<String> my_stack = new CS401StackLinkedListImpl<String>();
        my_stack.push("Brian");
        my_stack.push("Chris");
        my_stack.push("Joe");
        System.out.println("Stack size: " + my_stack.size());
        my_stack.pop();
        System.out.println("Stack size: " + my_stack.size());
        my_stack.toString();
    }

}

当我运行我的主类时，这是它返回的内容:

Stack size: 3
Exception in thread "main" java.lang.NullPointerException
    at week6.CS401StackLinkedListImpl.pop(CS401StackLinkedListImpl.java:30)
    at week6.App.main(App.java:66)

我遇到的一切都告诉我创建一个新的堆栈，这很容易，因为这样我就不必担心代码的“内部结构”，但这不是我需要的。谢谢。

Answer 1

问题出在您的size 方法上。它破坏了 head 的值，使其为 null。然后你对 pop 的调用得到一个 NPE。

变量初始化也有问题 - num_elements 只会在每次调用 size 时增加。您可以通过增加对 push 的调用的变量来简化这一过程。

如果使用的话，您的 setElement 也会破坏您的堆栈，因为它只是设置 head，而没有修补下一个指针。

对不起，我看到这是作业中交的......所以这里有一些更正代码的具体方法:

public CS401StackLinkedListImpl()
{
    head = null;
    num_elements = 0;
}

public void setElement(LinkEntry<E> anElement)
{
    if (head != null)
        anElement.next = head.next; //New top-of-stack needs to point to next element, if any
    else
        anElement.next = null;
    head = anElement;
}

/*Append the new element to the end of the list*/
public void push(E e)
{
    LinkEntry<E> temp = new LinkEntry<E>();
    temp.element = e;
    temp.next = head;
    head = temp;

    num_elements++; // Increase number of elements count here
}

/*Remove the most recently pushed element at the end of the list*/
public E pop()
{
    E result = head.element; // Save return value of TOS
    head = head.next; // Corrected POP action
    num_elements--;
    return result;
}

public int size()
{
    //Remove below since count is kept accurate with push/pop methods
    //LinkEntry<E> temp = new LinkEntry<E>();
    //for (temp = head; head != null; head = head.next)
    //    num_elements++;
    return num_elements;
}

如果没有元素，你可能想在 pop 中添加一个附加检查以抛出比 NPE 更好的异常，例如:

if (head == null)
    throw new StackUnderflowException(); // and define a StackUnderflowException; or use a standard exception with a message