链表堆栈实现 - Java

Question

我必须为我的一项作业实现链表形式的堆栈。我们必须实现接口 DStack，它在我们的 LinkedList.java 文件中有方法 push()、pop()、peek() 和 isEmpty()。该列表将以一系列双打作为其内容。

我还在纠结的基本上是链表的push()和pop()方法。我不确定我制作的节点，但这是我目前拥有的代码：

public class ListStack implements DStack{

private Node head;
private int size;


private class Node{
    double d;
    Node next;

    public Node(){
        head = null;
        next = null;
    }

    public Node(double data){
        d = data;
    }
}

public boolean isEmpty() {
    return (head == null);
}

@Override
public void push(double d) {
    if(!isEmpty()){
        Node newHead = new Node(d);
        newHead.next = head;
        head = newHead;
        size++;
    }
    else
        throw new EmptyStackException(); //To change body of generated methods, choose Tools | Templates.
}

@Override
public double pop() {
    if(!isEmpty()){
        double d = head.d;
        head = head.next;
        size--;
        return d;
    }
    else
        throw new EmptyStackException(); //To change body of generated methods, choose Tools | Templates.
}

@Override
public double peek() {
    if(!isEmpty()){
        return head.d;
    }
    else
        throw new EmptyStackException(); //To change body of generated methods, choose Tools | Templates.
}

如果我正确地执行 push() 和 pop() 方法，有人可以告诉我吗？如果不是，我到底需要在哪里修改它？我正在网上寻找解释，但大多数材料对我来说真的没有意义。

此外，我的老师禁止我们使用来自 Java 框架或其他 class 库的任何其他 classes。这是否意味着我不能在我的代码中使用 Iterable？如果是这样，那么就不需要为链表创建其他方法，例如 remove()、next() 等，对吗？

我仍然被这些链接列表的概念绊倒，所以如果有人能解决这个问题，我将不胜感激。谢谢！

Answer 1

pop() 和 peek() 看起来没问题，但是在空堆栈上尝试 push() 时不应该抛出异常。如果是这样的话，你将永远无法使用这个愚蠢的东西。相反，如果它是空的，你可能想做一些不同的事情，但在任何情况下都不应该 push() 抛出 EmptyStackException.

Answer 2

看起来不错，需要初始化 head 否则 push/pop 总是会抛出异常。考虑在不可能时抛出栈满异常，而不是空栈异常。这将是无限的列表容量，也许你可以考虑使用固定容量然后推送会有限制。

Answer 3

除了已经提供的建议之外，它还帮助我为一些基本场景绘制了 stack/list 的状态：开始时，中间有一些元素，最后当你删除最后一个元素时。然后逐步检查您的代码并检查 push() 和 pop() 的变量和指针发生了什么。

当然这也可以用调试器来完成——但笔和纸有时可以解决问题；）祝你作业顺利！

链表堆栈实现 - Java

Linked List Stack Implementation - Java

java

stack

linked-list