3

最近，我班一直在学习ArrayLists和LinkedLists。上周我们收到了一个任务，要求我们在 LinkedList 堆栈类中创建 push 和 pop 方法。我了解堆栈背后的逻辑，因此它是后进先出的，但我在实际代码中遇到了麻烦。我对计算机科学相当陌生（这是我的第二门课程），这个特殊的任务确实让我把头发拔了出来。我已经上交了这个作业，但我们下周有期中考试，我想好好完成它。我一直在网上和我的教科书上寻求帮助，但没有。我的教授只把我介绍给助教，助教只关心帮助我处理逻辑，而不是实际的代码。我将在下面发布教授给我的说明以及到目前为止的代码。

来自教授：

使用以下 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)

我遇到的所有事情都只是告诉我创建一个新堆栈，这很容易，因为我不必担心代码的“内部”，但这不是我需要的。谢谢。

4

4 回答 4

2

问题出在你的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
于 2012-10-05T19:56:07.660 回答
0 
/*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;
    num_elements++;//Increment count<--- Correction
    head = temp;
}

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

public int size()
{
   return num_elements;<--- Correction
}
于 2012-10-05T20:01:53.330 回答
0 
public void push(E e)

好像没问题。

public E pop()

看起来不太好：您分配给head.next元素本身，这会创建一个循环。然后你返回实际的head. 您应该首先将当前头保存在某处，然后更新head对下一个元素的引用并返回前一个头。

public int size()

方法是错误的：首先你实例化一个无用的元素，temp但你不需要它（因为你将在循环中使用 temp 并且你应该将它初始化为 current head。然后检查你的 for 循环：你正在head使用循环迭代结束时的停止条件。你不应该使用head，因为你只是在列表上迭代而不是修改它，而只是temp（检查你的toString代码是否正确）。

于 2012-10-05T19:49:50.033 回答
0

查看代码，您的 Pop 方法似乎是倒退的。

在您的 push 方法中，您将当前的head元素分配给新 LinkEntry 的 'next' 属性，然后将其设为新的 head。因此，当您将项目从列表中弹出时，您需要将“下一个”元素分配回列表的头部。所以你的代码，即：

head.next = head;

应该：

LinkEntry<E> toReturn = head;
head = head.next;
return toReturn.element;

实际上，您将头引用克隆到堆栈顶部的当前项（以便您可以返回它），然后移动头引用以指向堆栈中的下一项

于 2012-10-05T19:53:42.150 回答