java - 实现linkedStack时出现NullPointerException

Question

我得到了

Exception in thread "main" java.lang.NullPointerException
    at datastructuresPart2.LinkedStack.pop(LinkedStack.java:20)
    at tests.StackTest.main(StackTest.java:66)

当尝试实现链接堆栈时。几乎相同的代码在不同的项目中工作，所以我不确定发生了什么。我将发布所有相关代码。 (我已经成功地将它作为数组运行。但我需要使用链表...)

package datastructuresPart2;

import datastructuresPart2.Node;

public class LinkedStack<E> extends AbstractCollection<E> implements Stack<E> {


    private Node<E> top = null;

    @Override
    public void push(E element) {
        top = new Node<E>(element, top);
        size++;     
    }

    @Override
    public E pop() {
        if (isEmpty())
            throw new EmptyCollectionException("empty stack");
        E element = top.data;
        top = top.next;
        size--;
        return element;
        }

    @Override
    public E top() {
        if (isEmpty())
            throw new EmptyCollectionException("empty stack");
        return top.data;
    }

    @Override 
    public void clear() {
        super.clear();
        top = null;
    }

    public boolean contains(E element) {
        for (Node<E> current = top; current != null; current = current.next) 
            if (element.equals(current.data))
                return true;
        return false;
    }

    // Returns a string representation for this collection.
        @Override
        public String toString() {
            String buffer = "[";
            if (! isEmpty()) {
                buffer += top.data;
                for (Node<E> current = top.next; current != null; current = current.next)
                    buffer += ", " + current.data;
            }
            return buffer + "]";
        }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;

        if (getClass() != obj.getClass())
            return false;

        @SuppressWarnings("unchecked")
        LinkedStack<E> other = (LinkedStack<E>) obj;



        int count = 0;
        for (Node<E> trav = other.top; trav != null; trav = trav.next){

            if (top.getData().equals(trav.getData())) {
                count++;    
            }

            top = top.getNext();
        }

        if (count == size)
            return true;
        else
            return false;
    }
}

我还使用:

/*
 * StackTest.java
 * This source file contains a class that tests the Stack interface and
 * implementation.
 */

package tests;

import datastructuresPart2.*;

public class StackTest {

    // Serves as the entry point for this application.
    public static void main(String[] args) {
        Stack<String> stk = new LinkedStack<>();
        Stack<String> stk2 = new LinkedStack<>();


        System.out.println("After creating a new stack...");
        CollectionTest.print(stk);
        System.out.println();

        stk.push("cat");
        stk.push("dog");
        stk.push("tree");
        stk.push("house");
        stk.push("boat");
        stk.push("woman");
        stk.push("man");
        stk.push("car");
        stk.push("pool");
        stk.push("motorcycle");
        stk.push("mailbox");

        System.out.println("After adding some elements...");
        CollectionTest.print(stk);
        System.out.println();

        System.out.println("After creating a new stack2...");
        CollectionTest.print(stk2);
        System.out.println();

        stk2.push("cat");
        stk2.push("dog");
        stk2.push("tree");
        stk2.push("house");
        stk2.push("boat");
        stk2.push("woman");
        stk2.push("man");
        stk2.push("car");
        stk2.push("pool");
        stk2.push("motorcycle");
        stk2.push("mailbox");

        System.out.println("The top element is " + stk.top());
        System.out.println("Does it contains a man? " + stk.contains("man"));
        System.out.println();

        System.out.println("Are the stacks equal? " + stk.equals(stk2));

//      System.out.println("Traversing the stack...");
//      for (String element : stk)
//          System.out.println(element);
//      System.out.println();

        System.out.println("Removing: " + stk.pop());
        System.out.println("Removing: " + stk.pop());

        System.out.println("After removing the top two elements...");
        CollectionTest.print(stk);
        System.out.println();

        System.out.println("Are the stacks equal? " + stk.equals(stk2));
        System.out.println();

        System.out.println("The top element is " + stk.top());
        System.out.println("Does it contains a man? " + stk.contains("man"));
        System.out.println();

        stk.clear();
        System.out.println("After clearing the stack...");
        CollectionTest.print(stk);
        System.out.println();

        System.out.println("Trying to get the top element...");
        try {
            System.out.println("The top element is " + stk.top());
        }
        catch (EmptyCollectionException e) {
            System.out.println("Error: " + e.getMessage());
        }
    }

}

非常感谢任何帮助!

编辑:

Node.java

package datastructuresPart2;

public class Node<T> {

    T data;
    Node<T> next;

    public Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }

    public T getData() { return data; }
    public void setData(T data) { this.data = data; }
    public Node<T> getNext() { return next; }
    public void setNext(Node<T> next) { this.next = next; }

    @Override
    public String toString() {
        return data + "--->" + next; //recursion implicita
    }



}

AbstractCollection.java

package datastructuresPart2;

public abstract class AbstractCollection<E> implements Collection<E> {

    protected int size = 0;

    @Override
    public int size() { return size; }

    @Override 
    public void clear() { size = 0; }

    @Override
    public boolean isEmpty() { return (size == 0); }

    @Override public abstract boolean contains(E element);
    @Override public abstract String toString();
    @Override public abstract boolean equals(Object obj);



}

编辑:Collection.java ...不妨把整个事情放出来哈哈。

package datastructuresPart2;

public interface Collection<E> {

    int size();

    boolean isEmpty();

    boolean contains(E element);

    void clear();



}

Answer 1

我很确定这种情况正在发生，因为您的 equals() 实现正在修改堆栈的状态，这可能不是您想要的。您在失败的 pop() 行之前调用 equals()。

这里:

for (Node<E> trav = other.top; trav != null; trav = trav.next){

    if (top.getData().equals(trav.getData())) {
        count++;    
    }

    top = top.getNext();
}

您正在更改 top 的值，如果您遍历整个堆栈，top 在此函数调用结束时将为 null。重写equals()，这样它就不会修改对象的状态。

您还应该在 clear() 实现中设置 size = 0 和/或重写 isEmpty() 来检查 top==null 是否为空，这将是一个更强大的空性检查(例如，我认为您会在这里得到一个“堆栈为空”而不是空指针)。