java - 为什么我的递归函数不能递归遍历堆栈中的所有数据？

Question

我正在尝试使用递归反转 int 类型的堆栈。我能够反转第一个条目，但当我尝试在递归发生后打印假定的反转堆栈时，它仅显示零。这是我的代码:

//Class to reverse a stack using recursion
class ReverseStack
{
    //Global Variables
    static int[] stack = new int[5];
    static  int[] tempStack = new int[5];
    private static int size;

    //Constructor
    public ReverseStack()
    {

    }

    //Functions to for the stack
   public static boolean isEmpty()
    {
        return size == 0;
    }

    //Function to determine if stack is full
    public static boolean isFull()
    {
        return size == stack.length;
    }
    //Function to determine size of array
    int size()
    {
        return size;
    }

    //Function to push entries into stack
    public static boolean push(int[] stack, int data)
    {
        if(isFull())
        {
            return false;
        }
        else
        {
            stack[size] = data;
            size++;
            return true;
        }
    }

    //Function to remove entries from stack
    public static int pop()
    {
        if(isEmpty())
        {
            return 0;
        }
        else
        {
            size--;
            return(stack[size + 1]);
        }
    }

    //Function to print the stack
    public static void print(int[] stack)
    {
        //This prints top to bottom
        //Top is the last entry

        System.out.println("Top to Bottom");
        if(isEmpty())
        {
            System.out.println("The stack is empty ");
        }
        else
        {
            for(int cntr = 0; cntr < size; cntr++)
            {
                System.out.println(stack[cntr] + " ");
            }
        }
    }

    //Function to reverse data recursively
    public static void reverseData(int data)
    {
        //Variables
        int tempNum;
        int cntr = 4;
        int cntr2 = 0;


        //Note: 
        /*
        To reverse a stack we need to
        1. pass in a number 
        2. Remove the number
        3. Repeat until no numbers are left
        4  copy stack
        5. print

        */

        if(data > stack[cntr - 1])
        {
            tempStack[cntr2] = data;
            cntr--;
            cntr2++;
            data = stack[cntr - 1];
            reverseData(data);
        }

    }
}

我在程序的菜单系统中调用这个reverseStack函数:

//Function to create a menu system
    public static void menu()
    {
        //Variables
        int response;

        //Message user
        System.out.println("Would you like to: "
                + "\n(1) Reverse a stack using recursion "
                + "\n(2) Draw the Sierpinski Triangle "
                + "\n(3) Draw the Dragon Curve "
                + "\n(4) Recurse through a file/directory system"
                + "\n(5) Recurse through my own recursive function"
                + "\n(6) Quit the program ");

        //Save user's response
        response = Integer.parseInt(myScanner.nextLine());

        //Switch statement for menu options
        switch (response)
        {
            case 1:
            {
                //Create a new instance of ReverseStack class
                ReverseStack rs = new ReverseStack();

                //Add data into stack before reversing the stack
                rs.push(stack, 10);
                rs.push(stack, 20);
                rs.push(stack, 30);
                rs.push(stack, 40);
                rs.push(stack, 50);

                //Print stack
                rs.print(stack);

                //Call function to reverse data set
                rs.reverseData(stack[4]);

                //Print data set
                rs.print(rs.tempStack);

                //Return to menu
                menu();
                break;
            }
}
}

你知道我做错了什么吗？

Answer 1

Size 似乎总是比堆栈中最后一个元素的索引高 1，因此您的 pop 方法可能应该是

size--;
return stack[size]; // not stack[size+1]

此外，您的reverseData函数不起作用，因为您每次调用该函数时都会重置cntr和cntr2。这些必须是全局变量。

也许尝试类似的事情

int counter = 0;
public void reverseData (int index) {
    if (index > counter) {
        int temp = data[index];
        data[index] = data[counter];
        data[counter] = temp;
        counter++;
        reverseData(--index);

}