栈和队列——仅用递归函数和栈，逆序一个栈

Posted on | In ,

题目：一个栈依次压入1、2、3、4、5，从栈顶到栈底为5、4、3、2、1，则逆序后从栈顶到栈低为1、2、3、4、5。

实现：需要设计两个递归函数

  1. 第一个递归：递归弹出栈内元素，获得栈底的元素并移除；
  2. 第二个递归：递归弹出栈底元素，然后重新压入元素，逆序栈内元素。

递归：就是在运行的过程中调用自己。
递归的三个要素：
①、边界条件。
②、当边界条件不满足时，递归前进。
③、当边界条件满足时，递归返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Scanner;
import java.util.Stack;
public class ReverseStack {
	// 第一个递归，递归弹出栈顶元素，获得栈底元素并移除
	public static int getBottom(Stack<Integer> stack) {
		/*if (stack.empty()) {
			System.out.println("栈为空");
		}*/
		int result = stack.pop(); 
		if (stack.empty()) {
			return result;
		} else { // 如果不为空，则递归弹出元素
			int bottom = getBottom(stack);
			stack.push(result);
			return bottom;
		}
	}
	// 第二个递归，递归获得栈底元素并移除，再重新压入元素
	public static void reverse(Stack<Integer> stack) {
		if (stack.empty()) {
			return; 
		}
		int bottom = getBottom(stack); //获得栈底元素
		reverse(stack);
		stack.push(bottom);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
	// Test
	public static void main(String[] args) {
		Stack<Integer> sta = new Stack<>();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for(int i = 0; i < n; i++) {
			sta.push(sc.nextInt());
		}
		sc.close();
		//sta.push(2);
		//sta.push(3);
		reverse(sta);
		for (int i : sta) {
			System.out.println(i);
		}
	}
}