Когда я пытаюсь использовать концепцию стека вызовов. Это входит в бесконечное l oop. Я не могу выйти из этого - PullRequest
Новая
       55

Когда я пытаюсь использовать концепцию стека вызовов. Это входит в бесконечное l oop. Я не могу выйти из этого

1 голос
/ 30 января 2020

Когда я запускаю этот код, он становится бесконечным l oop. 

import java.util.Scanner;

public class StackAsLinkedList {
    Node head ;

    static class Node{
        int data ;
        Node next ;

        Node(int d){
            data  = d;
            next = null ;
        }
    }

    boolean isEmpty(){
        return (head == null);
    }


    void push(int new_data){
        Node n = head ;
        if(n == null){
            head = new Node(new_data);
            System.out.println(new_data + " pushed out successfully !! ");
            return ;
        }

        Node new_node = new Node(new_data);
        new_node.next = n ;
        head =  new_node ;
        System.out.println(new_data + " pushed out successfully !! ");
    }

    void pop(){
        Node n = head ;
        if(n == null){
            System.out.println("Stack underflow !!");
            return;
        }
        Node temp = n;
        head = n.next ;
        System.out.println(temp.data + " popped out successfully !");
    }

    int peek(){
        Node n = head ;
        if(head == null){
            System.out.println("Stack is Empty !!");
            return -1 ;
        }

        int x = n.data ;
        return x ;
    }

    void printStack(){
        Node n = head;
        if(n == null){
            System.out.println("The stack is Empty !");
            return ;
        }

        System.out.println("The Stack is :");
        while(n != null){
            System.out.println(n.data);
            n = n.next ;
        }

    }

    void insertAtBottom(int data){
        Node n = head ;
        if(head == null){
            head = new Node(data);
            return ;
        }
        while(n.next != null){
            n = n.next ;
        }

        Node new_node = new Node(data);
         n.next = new_node ;
    }

    void reverse(){
        while(isEmpty() == false){
            System.out.println(" ! isEmpty() : " + (isEmpty()) );
            System.out.println("Entered reverse Function !");

            int x  = peek();
            System.out.println(x);
            pop();
            reverse();

            insertAtBottom(x);
        }
    }



    public static void main(String ... s){
        StackAsLinkedList stack =  new StackAsLinkedList() ;

        stack.head = new Node(4);
        Node second = new Node(3);
        Node third = new Node(2);
        Node fourth = new Node(1);

        stack.head.next = second ;
        second.next = third ;
        third.next = fourth ;

        stack.printStack();
        stack.reverse();
        stack.printStack();

    }
}

Вывод: 

The Stack is :
4
3
2
1
 ! isEmpty() : false
Entered reverse Function !
4
4 popped out successfully !
 ! isEmpty() : false
Entered reverse Function !
3
3 popped out successfully !
 ! isEmpty() : false
Entered reverse Function !
2
2 popped out successfully !
 ! isEmpty() : false
Entered reverse Function !
1
1 popped out successfully !
 ! isEmpty() : false
Entered reverse Function !
1
1 popped out successfully !
 ! isEmpty() : false
Entered reverse Function !
1
1 popped out successfully !
 ! isEmpty() : false
Entered reverse Function !
1
1 popped out successfully !
 ! isEmpty() : false
Entered reverse Function !
1
1 popped out successfully !
 ! isEmpty() : false

1 Ответ

0 голосов
/ 31 января 2020

Вы получили инфинитив l oop в reverse() методе:

  • сначала ваш метод - проверить, что он не пустой, и начать работу;
  • вы удаляете один за другим элементы 1,2,3 в вашем стеке, пока он не останется последним один раз 4;
  • перед удалением этого, вы сохраните его значение в int x (кстати, вы должны вернуть data поле в методе pop() вместо вывода его значения на консоли - и вам не нужно делать одну вещь в двух действиях)
  • следующий reverse() метод возвращается без дальнейшей глубокой рекурсии уровень ...
  • и на том же глубоком уровне рекурсии вы снова вставляете x данные в insertAtBottom(x) и возвращаетесь с этого уровня в родительский элемент;
  • родительский элемент Проверяет уровень рекурсии, стек пуст, и уверен, что он не пуст - пока l oop будет работать;
  • и все будет снова.
...