首页 > 试题广场 >

用递归函数和栈逆序一个栈

[编程题]用递归函数和栈逆序一个栈

热度指数：8598 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个栈依次压入1,2,3,4,5，那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

输入描述:

输入数据第一行一个整数N为栈中元素的个数。

接下来一行N个整数表示一个栈依次压入的每个元素。

输出描述:

输出一行表示栈中元素逆序后的栈顶到栈底的每个元素

示例1

输入

5
1 2 3 4 5

输出

1 2 3 4 5

算法知识视频讲解

Java

pein531

左老师课堂上的经典例题，这两个递归函数还是得画个图好好理解一下。基本思路是：每次获得栈底元素，当一层层调用递归函数，就能够得到栈中只有一个元素的base case。栈顶弹出后直接压栈，然后一层层返回去，将之前的栈底压栈，这样之前的栈底就变成了现在的栈顶。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++) stack.push(Integer.parseInt(strArr[i]));
        reverse(stack);
        while(!stack.isEmpty()) System.out.print(stack.pop() + " ");
    }
    
    private static int getLast(Stack<Integer> stack) {
        int result = stack.pop();
        if(!stack.isEmpty()){
            int last = getLast(stack);
            stack.push(result);
            return last;
        }else
            return result;        // 只有一个元素，返回去
    }
    
    private static void reverse(Stack<Integer> stack) {
        if(stack.isEmpty()) return;
        int elem = getLast(stack);     // 获得栈底
        reverse(stack);
        stack.push(elem);
    }
}

发表于 2021-11-14 18:00:24 回复(0)

Java

Forrest0721

这题的测试明显有bug。只判断输出适合符合“栈的逆序”，完全不检测方法是否合理。

那么，完全可以用栈接收输入，出栈即为所求。。。

Stack<Integer> stack = new Stack<>();
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
scanner.nextLine();
for(int i = 1; i <= N; i++) {
    stack.push(scanner.nextInt());
}
int count = 0;
while(!stack.empty()) {
    System.out.print(stack.pop());
    count++;
    if(count != N)
        System.out.print(" ");
}

发表于 2021-08-25 20:02:47 回复(1)

Java

无可救药的菜鸡

public static void main(String[] s) {
        Scanner sc = new Scanner(System.in);
        int x = Integer.parseInt(sc.nextLine());
        int[] arr = new int[x];
        for(int i = 0; i < x; i++) {
            arr[i] = sc.nextInt();
        }
        outputStack(arr, 0);
    }
    
    public static void outputStack(int[] arr, int index) {
        if (index ==  arr.length - 1) {
            System.out.print(arr[index]);
            return;
        }
        int x = index;
        outputStack(arr, ++x);
        System.out.print(" " + arr[index]);
    }

发表于 2020-09-12 22:40:52 回复(0)

Java

deh

import java.util.Scanner;
import java.util.Stack;

public class Main{

    // 将stack的栈底元素移除并返回
    public static int getAndRemoveLastElement(Stack<Integer> stack){
        int result = stack.pop();
        if (stack.isEmpty()){
            return result;
        } else {
            int last = getAndRemoveLastElement(stack);
            stack.push(result);
            return last;
        }
    }

    // 逆序一个栈
    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) {
        Scanner sc = new Scanner(System.in);
        // 迷惑行为：本题的输入是入栈的反顺序，因此借助stackPlus将输入逆序
        Stack<Integer> stackInt = new Stack<>();
        Stack<Integer> stackPlus = new Stack<>();
        while (sc.hasNextInt()){
            int N = sc.nextInt();
            for (int i = 0; i < N; i++){
                stackPlus.push(sc.nextInt());
            }
            while (!stackPlus.isEmpty()){
                stackInt.push(stackPlus.pop());
            }
            reverse(stackInt);
            while (!stackInt.isEmpty()){
                System.out.print(stackInt.pop() + " ");
            }
        }
    }
}

发表于 2020-04-04 16:04:37 回复(1)

Java

把我想成一颗树

import java.util.Scanner;
import java.util.Stack;


public class Main {

	/**
	 * @param args
	 */
	public int srt(Stack<Integer> stack){
		if(stack.empty()){
			return 1;
		}
		else{
		 System.out.print(stack.pop()+" ");
		 srt(stack);
		 }
		return 1;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Stack<Integer> s =new Stack<Integer>();
          Scanner n =new Scanner(System.in);
          int N=n.nextInt();
          for (int i = 0; i < N; i++) {
			s.push(n.nextInt());
		}
         Main t =new Main();
          t.srt(s);
          
	}

}

发表于 2020-03-22 17:46:15 回复(0)

Java

闪电利剑

谁出的测试用例，有毒吧。这测试用例，直接入栈再出栈就完事了啊，输入和输出一样才把栈反转了。

import java.util.Stack;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();

        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        for (int i = 0; i < count; i ++) {
            stack.push(sc.nextInt());
        }
        reverseStack(stack);
        while (!stack.isEmpty()) {
            System.out.print(getAndRemoveLastElement(stack) + " ");
        }
    }
    public static void reverseStack(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        int i = getAndRemoveLastElement(stack);
        reverseStack(stack);
        stack.push(i);
    }
    public static int getAndRemoveLastElement(Stack<Integer> stack) {
        int result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        } else {
            int last = getAndRemoveLastElement(stack);
            stack.push(result);
            return last;
        }
    }
}

发表于 2020-02-29 16:42:46 回复(0)

Java

小星教授

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		Stack<Integer> stack = new Stack<>();
		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i] = scanner.nextInt();
		}
		for(int i=n-1;i>=0;i--) {
			stack.push(arr[i]);
		}
		
		reverse(stack);
		
		for(int i=0;i<n;i++) {
			System.out.print(stack.pop() + " ");
		}
	}
	
	
	private static int getAndRemoveLastEle(Stack<Integer> stack) {
		int val = stack.pop();
		if(stack.isEmpty()) {
			return val;
		}else {
			int res = getAndRemoveLastEle(stack);
			stack.push(val);
			return res;
		}
	}
	
	private static void reverse(Stack<Integer> stack) {
		if(stack.isEmpty()) {
			return;
		}
		
		int lastEle = getAndRemoveLastEle(stack);
		reverse(stack);
		stack.push(lastEle);
	}
}

发表于 2019-10-21 15:17:48 回复(0)

Java

牛客654210号

真的奇葩输出

import java.util.Scanner;
import java.util.*;
public class  Main{
private Stack<Integer> stack;

    public Main(Stack stack){
        this.stack = stack;
    }

    //弹出栈底的元素
    public  int popLast(){
        //递归回退条件,当前的栈顶值
        int result = stack.pop();
        if(stack.empty()){
            return result;
        }
        int last = popLast();
        stack.push(result);
        return last;
    }

    public  void reveseStack(){
        if(stack.empty()){
            return;
        }
        int val  = popLast();
        reveseStack();
        stack.push(val);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Stack<Integer> stack = new Stack();
        int count = sc.nextInt();
        while(count-->0){
            stack.push(sc.nextInt());
        }
        sc.close();
        Main r = new Main(stack);
        r.reveseStack();
        
        Stack<Integer> stack2 = new Stack<>();
        
         while(!stack.empty()){
            stack2.push(stack.pop());
        }
        
        while(!stack2.empty()){
            System.out.print(stack2.pop()+" ");
        }
    }
}

发表于 2019-08-13 23:29:22 回复(0)