java - 如何在 Java 中的 Stack/Queue 类中实现通用 LinkedList

Question

我有一个项目，我必须在堆栈和队列类中实现 LinkedList 数据结构。包括我的 LinkedList 在内的所有类都是通用类型 <E> 。问题是我收到了一堆溢出和空指针异常错误。这是我的物流:

我的 Stack 和 Queue 类应该实现我之前编写的 LinkedList 类，该类运行完美(我彻底测试了它)。我的 LinkedList 同时实现 LinkedListImplementation，它只包含我应该使用的方法的“蓝图”。另外，我想说所有这些文件 -> LinkedListImplementation.java、LinkedList.java 和 Stack.java 都在一个名为 package1 的包内。 .

以下是方法(没有代码，因为我 110% 确定它运行完美):

//LinkedListImplementation.java:
package package1;
import java.util.Iterator;
public class LinkedListImplementation<E> extends Iterable<E>{
    //...
    //All the methods to be used go here. See the methods in LinkedList.java
}//End LinkedListImplementation Implementation Class




//LinkedList.java:
package package1;
import java.util.Iterator;
import java.lang.Comparable;
import java.util.NoSuchElementException;

public class LinkedList<E> implements LinkedListImplementation<E>{
    int size;
    Node<E> head, tail;

    public LinkedList(){
        head = null;
        tail = null;
    }

    class Node<E>{
        E data;
        Node<E> next;

        //Default Node constructor
        Node(E obj){
            this.data = obj;
            next = null;
        }
    }
    //Logic for all the LinkedList methods below.

    //This method contains its code, as an example...
    public void addLast(E obj){
        Node<E> newNode = new Node<E>(obj);
        if( isEmpty() ){
            head = newNode;
            tail = newNode;
            size++;
        }else{
            tail.next = newNode;
            tail = newNode;
            size++;
        }
    }

    public void addFirst(E obj){
        ...
    }

    public void insert(E obj, int location){
        ...
    }

    //... Other methods, such as removeFirst(), removeLast(), remove(int location)
    //... size(), get(int location), contains(E obj), locate(int location)
    //... clear(), isEmpty().
}//End LinkedList Class

正如你所看到的，我可以在java中使用LinkedList类，但我不允许使用java.util中任何已构建并具有默认行为的库，即LinkedList、Stack和Queue。我应该自己编写逻辑和实现来模拟他们的行为。

现在，我想实现一个由节点组成的堆栈，实现我的 LinkedList。这是我的尝试:

//Stack.java:
package package1;
import java.util.Iterator;
public class Stack<E> extends LinkedList<E> implements Iterable<E>{
    LinkedList<E> list;

    Stack(){
        list = new LinkedList<E>();
        testStack();
    }

    //START declaration of Stack methods
    public void push(E obj){ list.addFirst(); }

    public E pop(){ return list.removeFirst() }

    public int size(){ return list.size(); }

    public boolean isEmpty(){ return list.isEmpty(); }

    public E peek(){ return list.get(size()); }

    public boolean contains(E obj){ return list.contains(obj); }

    public void makeEmpty(){ list.clear(); }

    public Iterator<E> iterator(){ return list.iterator(); } 
    //END declaration of Stack methods

    //My tests to see if the Stack works
    public void testStack{

        Stack<Integer> testStack = new Stack<Integer>();
        //Test push method
        for(int i = 1; i < 100; i++){
            stack.push(new Integer(i));
        }
    }//End testStack

    public static void main(String [] args) {
        try {
            new Stack();
        } catch(Exception e) {
            System.out.println("ERROR: " + e);
            e.printStackTrace();
        }
    }//End Main method

}//End Stack Class

这是我的代码。我什至没有尝试接近 Queue 类，因为一旦我启动并运行 Stack 类，实现 Queue 类就会非常容易。

每当我运行代码时，都会收到以下错误:

Exception in thread "main" java.lang.StackOverflowError
    at data_structures.LinearList.<init>(LinkedList.java:24)
    at data_structures.Stack.<init>(Stack.java:9)
    at data_structures.Stack.testStack(Stack.java:25)
    at data_structures.Stack.<init>(Stack.java:11)
    at data_structures.Stack.testStack(Stack.java:25)
    at data_structures.Stack.<init>(Stack.java:11)
    at data_structures.Stack.testStack(Stack.java:25)
    ...//A lot more of the same line 11 and 25 errors...

我认为错误的发生是由于 testStack 内的 for 循环造成的。我的代码中存在方法和某种类实例化错误。第一个错误(第 24 行)指的是 LinkedList类构造函数。第二个错误(第 9 行)指的是 Stack类构造函数。第三个错误(第25行)是指runTests()内堆栈的实例化。方法，如下行:Stack<Integer> testStack = new Stack<Integer>(); 。第四个错误(第 11 行)指的是 testStack调用Stack()内类默认构造函数。

有人可以帮助我找到实现目标的正确方法吗？这又是为了建立一个 Stack 结构并使用我的 LinkedList 数据结构运行。

非常感谢您提前提供的帮助和时间!

干杯!

<小时/>

编辑1:

push方法错误(是pop方法)。还添加了 pop 方法。这些是正确的(上面也已更正)

public void push(){ list.addFirst(obj); } 
public E pop(){ return list.removeFirst(); }

Answer 1

您已经定义了您的Stack构造函数如下:

Stack(){
    list = new LinkedList<E>();
    testStack();
}

还有你的testStack()方法如下，缺少()

//My tests to see if the Stack works
public void testStack(){

    Stack<Integer> testStack = new Stack<Integer>();
    //Test push method
    for(int i = 1; i < 100; i++){
        stack.push(new Integer(i));
    }
}//End 

您的Stack()构造函数正在调用testStack()方法，它本身在语句中初始化一个 Stack: Stack<Integer> testStack = new Stack<Integer>();这会变成递归，你会遇到 StackOverflowError