java - Java中队列链表中的递归toString

Question

我需要为链表队列实现一个 toString() 递归方法。我知道我的 toString 方法在我上周完成的链表实现上运行良好，所以我处理它的队列方面的方式有问题。

我的 QueueList 的 toString 方法:

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 的构造函数:

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递归，事实上这样做是不正确的。您的数据结构不是递归的(即树)而是线性的。

如果您的列表包含 100 万个项目，您很快就会耗尽堆栈空间(StackOverflow，字面意思)。

改用循环。

编辑:如果您需要递归地执行此操作，那么问题是递归方法必须是 QueueNode#toStringRecursive() ，不是Queue#toString() 。方法Queue#toString()分配一个缓冲区并将其提供给特殊的 toStringRecursive()方法QueueNode这是递归的。 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()将设置初始条件，然后调用递归。