首页 > 代码库 > 用递归翻转一个栈 Reverse a stack using recursion

用递归翻转一个栈 Reverse a stack using recursion

明白递归语句之前的语句都是顺序运行,而递归语句之后的语句都是逆序运行


package recursion;

import java.util.Stack;

public class Reverse_a_stack_using_recursion {

	/*
	 Input stack:
	 3
	 2
	 1
	 Output stack:
	 1
	 2
	 3
	 */
	public static void main(String[] args) {
		Stack<Integer> s = new Stack<Integer>();
		s.push(1);
		s.push(2);
		s.push(3);
		insertAtBottom(s, 4);
		System.out.println(s);
		reverseStack(s);
		System.out.println(s);
	}
	
	// 把item插入到栈s的底部
	public static void insertAtBottom(Stack<Integer> s, int item) {
		if(s.isEmpty()) {		// 假设是空栈则能够直接增加
			s.add(item);
			return;
		}
		
		int tmp = s.pop();		// 把栈顶元素保存在tmp,这样就转化为少一个元素的子栈问题
		insertAtBottom(s, item);// 递归地把item插入到栈底
		s.push(tmp);			// 把tmp又一次插入到栈顶 
	}
	
	// 把栈s翻转
	public static void reverseStack(Stack<Integer> s) {
		if(s.isEmpty()) {
			return;
		}
		
		int tmp = s.pop();		// 把栈顶元素保存在tmp,这样就转化为少一个元素的子栈问题
		reverseStack(s);		// 翻转剩下的子栈
		insertAtBottom(s, tmp);	// 把tmp插入到栈底
	}

}




http://www.geeksforgeeks.org/reverse-a-stack-using-recursion/



用递归翻转一个栈 Reverse a stack using recursion