递归toString在Java中的队列链接列表

Question

我需要为链表队列实现toString（）递归方法。我知道我的toString方法在我上周做的链表实现上很好，所以我在处理Queue方面有些问题。对于QueueList

public String toString() 
{ 

    if (front.info == null) 
    { 
     System.out.println("Error, queue is empty"); 
     return ""; 
    } 
    if (front.link == null) //base case: if this is last element in stack 
    { 

     return (" \"" + front.info + "\" , "); 
    } 
    else //normal recursive function 
    { 
     return (" \"" + front.info + "\" , " + front.link.toString()); 

    } 

} 

和我的建设者和这样的：我QueueList

toString方法

public class QueueNode 
{ 
    E info; 
    QueueNode link; 
} 

private QueueNode front;//first element to be placed into queue 
private QueueNode rear;//last element to be placed into queue 
private int NoE;//counter for number of elements in queue 
public QueueList() 
{ 
    front = null; 
    rear = null; 
    NoE = 0; 
} 

我想看看使用这个测试发生了什么事情在里面：

public boolean test() { 
    QueueList<String> q = new QueueList<String>(); 

    q.enqueue("The Godfather"); 
    q.enqueue("Casino"); 
    q.enqueue("Goodfellas"); 
    String r = q.toString(); 
    q.PrettyPrint(); 

与输出

IN -> [ "The Godfather" , QueueList$QueueNode@a3901c6] -> OUT. 

我知道这是因为我告诉在toString方法的递归部分说front.link.toString()，但即使我将其更改为front.link.info.toString()，我的输出是

IN -> [ "The Godfather" , Casino] -> OUT. 

这可能是可能的东西然后用我的入队和出队方法，如下所示：

public void enqueue(E element) 
{ 

     QueueNode newNode = new QueueNode();//creates new Node to hold element 
     newNode.info = element;//set info of new Node to element 
     newNode.link = null;//make link null since it's at back of list 
     if (rear == null)//checks if queue is empty 
     { 
      front = newNode; 
     } 
     else 
     { 
      rear.link = newNode;//sets second to last node's link to newNode 
     } 
     rear = newNode;//makes newNode the new last link 
     NoE++;//increase counter 

} 
public E dequeue() throws InvalidOperationException 
{ 
    if (front == null)//sanitize code 
    { 
     throw new InvalidOperationException("There is nothing in the queue."); 
    } 
    E element = front.info;//creates an element file that takes the info in front of queue 
    front = front.link;//makes second-to-front element new front 
    if (front == null)//if this emptied the queue, make sure rear is also empty 
    { 
     rear = null; 
    } 
    NoE--;//reduce counter 
    return element; 
} 

请帮助我，如果你可以。谢谢。

Answer 1

绝对没有必要使toString递归，而实际上它是不正确这样做。您的数据结构不是递归的（即树），而是线性的。

如果你的列表包含了一百万个项目，你很快就会用完堆栈空间（StackOverflow，字面意思）。

改为使用循环。

编辑：如果你是做这个递归要求，那么问题是递归的方法必须是QueueNode#toStringRecursive()，不Queue#toString()。方法Queue#toString()分配一个缓冲区并将其提供给执行递归的QueueNode上的特殊toStringRecursive()方法。 QueueNode#toString()只能对其自己的节点内容负责。

方法Queue#toString()

public String toString() 
{ 
    StringBuilder buf = new StringBuilder(); 
    if (front == null) 
     // queue is empty 
    else 
     front.toStringRecursive(buf); 
    return buf.toString(); 
} 

方法QueueNode#toStringRecursive()

public void toStringRecursive(StringBuilder buf) 
{ 
    buf.append(this.toString()); 
    if (this.link != null) 
     this.toStringRecursive(buf); 
} 

其中QueueNode.toString()仅用于字符串化一个节点（本身）负责。

请注意，这是一个的方式来做到这一点。也可以在Queue上将其作为递归方法编写，但不能称为toString()。 Queue#toString()会设置初始条件，然后调用递归。