Reverse a stack with recursive functions and stack operations only

【 subject 】

A stack is pushed in turn 1、2、3、4、5, So from the top to the bottom of the stack are 5、4、3、2、1. After transposing this stack , From the top to the bottom of the stack is 1、2、3、4、5, That is to realize the reverse order of the elements in the stack , But it can only be implemented with recursive functions , You can't use other data structures .

【 Ideas 】

Only recursive functions are required , You need to design two functions , Function returns the bottom of the stack element and removes ; Function 2 implements the reverse stack , Function one is required .

explain ： The picture comes from Zuoshen's program code interview guide , For learning purposes only .

Function one ：

// Return to the bottom of the stack and remove public static int getAndRemoveLastElement(Stack<Integer> stack){    int res = stack.pop();    if(stack.isEmpty()){        return res;    }else{        int last = getAndRemoveLastElement(stack);        stack.push(res);        return last;    }}

Function two ：

// Reverse order stack public static void reverse(Stack<Integer> stack){	if(stack.isEmpty()){		return ;	}	int i = getAndRemoveLastElement(stack);	reverse(stack);	stack.push(i);}

【 Code 】

package keafmd.accumulate.codeinterviewguide.reversestack;import java.util.Stack;/** * Keafmd * * @ClassName: ReverseStack * @Description:  Use function reverse stack  * @author:  Cowherd Conan  * @date: 2022-06-22 11:01 */public class ReverseStack {    // Return to the bottom of the stack and remove     public static int getAndRemoveLastElement(Stack<Integer> stack){        int res = stack.pop();        if(stack.isEmpty()){            return res;        }else{            int last = getAndRemoveLastElement(stack);            stack.push(res);            return last;        }    }    // Reverse order stack     public static void reverse(Stack<Integer> stack){        if(stack.isEmpty()){            return ;        }        int i = getAndRemoveLastElement(stack);        reverse(stack);        stack.push(i);    }    public static void main(String[] args) {        Stack<Integer> stack = new Stack<>();        for(int i=1;i<=5;i++){            stack.push(i);        }        System.out.print(" Before reverse order ：");        while (!stack.isEmpty()){            System.out.print(stack.pop()+" ");        }        System.out.println();        for(int i=1;i<=5;i++){            stack.push(i);        }        reverse(stack);        System.out.print(" After reverse order ：");        while (!stack.isEmpty()){            System.out.print(stack.pop()+" ");        }        System.out.println();    }}

effect ：

 Before reverse order ：5 4 3 2 1  After reverse order ：1 2 3 4 5 Process finished with exit code 0