首页 > 代码库 > 用递归翻转一个栈 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。