遞歸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()會設置初始條件，然後調用遞歸。