Turn a stack recursively into a linked list

Question

therefore, I worked on a programming assignment that involved executing a ~ 13,000 stack and turning it into a linked list. The guide is basically that the stack has been populated by sequentially scanning the linked list (IE tail was the top of the stack) and you want to create the linked list using the stack. The trick is that you need to do this using a recursive method. The only methods in this stack class are pop (returns and deletes the top element), and isEmpty (indicates whether empty is empty). I have code that does this work, but it requires increasing the size of the java stack (otherwise I get a StackOverflowError), which I think is not resolved.

As the saying goes, does anyone know a way I could get this to work without increasing the size of the java package.

The stack is the static field that I designated S. Head is what should be the first node in the linked list, and steper is just the node that will be used to create every other step.

Here is the code I have:

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;
        }

}

Thank you for your help.

Answer 1

This is because you are storing a complete list of function calls on the memory stack. You start creating your linked list only after you reach the bottom of the stack, thereby keeping all previous calls on stackList, waiting for completion.

You need to start creating a linked list with the first pop of stack.

( 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)

EDIT: , , , , , Java .

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);
}

, java.util.LinkedList, . , , add(int index, E element) java.util.LinkedList, . , , .

EDIT:

, Harsh Gupta , , StackOverflowError, , , , . - , , .