スタックを再帰的にリンクリストに変換する

Question

私は、13,000のサイズのスタック実装を取得してリンクリストにするというプログラミング割り当てに取り組んでいます。ガイドは基本的に、リンクされたリスト（IEテールがスタックの先頭になる）を順番にスキャンすることによってスタックが満たされ、スタックを使用してリンクリストを再作成したいと考えています。トリックは、再帰的なメソッドを使用して行う必要があります。このスタッククラスの唯一のメソッドは、pop（先頭の要素を戻して削除する）とisEmpty（スタックが空であるかどうかを指示する）です。私は仕事を終わらせるコードを持っていますが、Javaスタックのサイズを増やす必要があります（それ以外の場合はStackOverflowErrorを取得します）。これは許されないようです。

誰もが、私はおそらくこれをJavaスタックのサイズを増やさずに動作させる方法を知っていると言われている。

スタックは静的フィールドで、ラベルはSです。ヘッドはリンクリストの最初のノードでなければなりません。steperは他のすべてのステップを作成するためのノードです。ここで

は、私が現在持っているコードです：

public static void stackToList() 
{ 
    int x = 0; 
     if(S.isEmpty()) 
     { 
      return; 
     } 
     x = S.pop(); 
     stackToList(); 
     if (head == null) 
     { 
      head = new ListNode(x, null); 
      steper = head; 
     } 
     else 
     { 
      steper.next = new ListNode(x, null); 
      steper = steper.next; 
     } 

} 

先に任意の助けのための時間のありがとう。

Answer 1

メモリスタック内の関数呼び出しのリスト全体を保持しているために起こっています。スタックされたリストの作成を開始するのは、スタックの一番下まで来てから、以前のすべての呼び出しをstackListが終了するのを待つことです。

スタックの最初のポップでリンクリストの作成を開始する必要があります。

シンプル& が非機能がどのように見えることがあり（現在、非常に長い時間の中で、Javaで働いていない）をテストした：

public static ListNode stackToList(ListNode head) { 
    if(S.isEmpty()) 
     return head; 

    int stackValue = S.pop(); 
    ListNode node = ListNode(stackValue, null); 
    node.next(head); 
    return stackToList(node); 
} 

そして、あなたが好きそれを呼び出す：

ListNode head = stackToList(null) 

HTH

編集：これを投稿したので、私のコードはあなたと同じ問題を潜在的に持っていることに気付きました。私はJava doesn't support tail-call optimization。

Answer 2

あなたは、私は以下の私の例ソリューションのものを使用することになり、これらのオブジェクトのためのコードを提供しなかったので、それはあなたがjava.util.LinkedListとjava.util.Stackを使用している場合は、あなたの質問から完全には明らかではないですが。

public static void main(String[] args) { 
    //Create a stack 
    Stack<Integer> stack = new Stack<Integer>(); 
    stack.push(0); 
    stack.push(1); 
    stack.push(2); 
    stack.push(3); 
    stack.push(4); 
    stack.push(5); 
    stack.push(6); 
    stack.push(7); 
    stack.push(8); 
    stack.push(9); 

    //Create a list to hold your stack elements 
    LinkedList<Integer> linkedList = new LinkedList<Integer>(); 

    //Call the conversion method, which modifies both the stack and the list 
    convertStackToLinkedList(stack, linkedList); 

    //print the results 
    System.out.println("linkedList: "+linkedList); 
} 

public static void convertStackToLinkedList(Stack<Integer> stack, LinkedList<Integer> linkedList){ 
    int topStackElement = stack.pop(); 
    linkedList.add(0,topStackElement); 
    if(!stack.isEmpty()) 
     convertStackToLinkedList(stack, linkedList); 
} 

Iコードがリストの内部を修正しようとしているので、java.util.LinkedListを使用していない可能性があります。だから、java.util.LinkedListクラスのadd(int index, E element)メソッドと同様のメソッドを実装し、それを再帰で使用するだけで済みます。リストの内部にアクセスできる場合は、これを行うことができます。

EDIT：

私はあなたがStackOverflowErrorを見ている理由は、あなたが変更するあなたの再帰の最後に到達するまで、あなたが待っているということであるという点で、私は過酷グプタによって答えに同意することを言及するのを忘れてしまいましたあなたのリスト。いくつかの再帰では、最後まで待たなければならないが、待たなければならない場合は、それをしないでください。