所以,当我注意到我交的作业上有一些东西时,我一直在复习类里面的一些作业。其中一部分是编写一个堆栈和一个节点类,它应该有一个方法来返回堆栈的当前值尺寸。我错过了这样一个事实:我实际上需要在 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;
}
}
如您所见,我正在节点的大小方法中执行递归部分。但是,分配基本上意味着不要在节点类中使用额外的大小方法(尽管可以使用我所做的所有其他方法)。这就是我的问题 - 我不知道如何在仍然使用递归的情况下以任何其他方式实现它。
预先感谢您的帮助。
最佳答案
您可以在堆栈类的私有(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;
}
关于Java:使用递归返回自制堆栈大小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28283362/