Java:使用递归返回自制堆栈大小

Question

所以，当我注意到我交的作业上有一些东西时，我一直在复习类里面的一些作业。其中一部分是编写一个堆栈和一个节点类，它应该有一个方法来返回堆栈的当前值尺寸。我错过了这样一个事实:我实际上需要在 size 方法中使用递归。所以我尝试了一些东西并且得到了正确的结果。代码如下:

public class CharStack {

    private CharStackNode top;

    public CharStack() {
        top=null;
    }

    public void push(char img) {
        CharStackNode node=new CharStackNode(img, top);
        top=node;
    }

    public char pop() {
        char result = top.getImage();
        top = top.getNext();
        return result;
    }

    public char peek() {
        return top.getImage();
    }

    public int size() {
        int counter=0;
        if(this.top!=null) {
        counter=this.top.size();
        }
        return counter;
    }

    public boolean empty() {
        return top == null;
    }
}

正如您所看到的，我正在调用节点的大小方法来实际确定大小。这是节点类:

public class CharStackNode {

    private char image;
    private CharStackNode next;

    public CharStackNode(char image, CharStackNode next) {
        this.image = image;
        this.next = next;
    }

    public char getImage() {
        return image;
    }

    public CharStackNode getNext() {
        return next;
    }

    public int size() {
        int count=0;
        if(this.next!=null) {
            count=this.next.size();
        }
        count+=1;
        return count;
    }
}

如您所见，我正在节点的大小方法中执行递归部分。但是，分配基本上意味着不要在节点类中使用额外的大小方法(尽管可以使用我所做的所有其他方法)。这就是我的问题 - 我不知道如何在仍然使用递归的情况下以任何其他方式实现它。

预先感谢您的帮助。

Answer 1

您可以在堆栈类的私有(private)方法上实现所需的递归，而 size() 方法仅用作前端。这将允许您定义控制递归所需的任何参数。例如，您可以实现如下递归方法:

private int tailSize(CharStackNode from) {
    return (from == null) ? 0 : (1 + tailSize(from.getNext()));
}

并将您的 CharStack.size() 编写为

public int size() {
    return tailSize(top);
}

请注意，递归是解决这个特定问题的一种糟糕方法。迭代解决方案的开销较小，而且也不是特别复杂:

public int size() {
    int rval = 0;

    for (CharStackNode next = top; next != null; next = next.getNext()) {
        rval += 1;
    }

    return rval;
}