By

文章目录
  1. 1. 题目
  2. 2. 解题
  3. 3. 代码
  4. 4. 参考

题目

使用递归的方法将栈颠倒

解题

假设当前的入栈顺序为1,2,3,4,5 那么我们的目标是将栈内的顺序改为5,4,3,2,1
先来看如果将数据搞成了1 和5,4,3,2 那么只需要将1放在栈的尾部即可，就可以变成了5,4,3,2,1
那么如何将2，3，4，5变为5,4,3,2呢，其实同理，也是分为2和5,4,3 一致递归

关于如何将元素放入栈的尾部？

将e放到底部
先递归逐个将元素取出来  取至空的时候将e给push进去
然后再依次将取出来的元素也给push进去

代码

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
27
28
29
30
31
32
33
34
35
36
37
/**
 * 1,2,3,4,5看成1和2,3,4,5
 * 假如已经将2,3,4,5倒转置5,4,3,2  那么只需要将1放到末尾即可
 * 同时关于2,3,4,5的倒置也可以看做3,4,5和2的分离
 * 逐步递归即可
 * @param stack
 */
public static <E> void putUpsideDownStack(Stack<E> stack)
{
	if(stack.size()<=0)
		return ;
	
	E t=stack.pop();
	putUpsideDownStack(stack);
	addToBottom(stack,t);//将当前元素放到底部
}

/**
 * 将e放到底部
 * 先递归逐个将元素取出来  取至空的时候将e给push进去
 * 然后再依次将取出来的元素也给push进去
 * @param stack
 * @param e
 */
public static <E> void addToBottom(Stack<E> stack,E e)
{
	if(stack.size()==0)
	{
		stack.push(e);//放到底部
		return ;
	}
	
	E t=stack.pop();
	addToBottom(stack,e);
	stack.push(t);
	
}

验证结果可以看到

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
	// TODO Auto-generated method stub
	Stack<Integer> stack=new Stack<Integer>();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	stack.push(5);
	putUpsideDownStack(stack);
	
	while(stack.size()>0)
		System.out.println(stack.pop());
}

1
2
3
4
5

参考

http://blog.csdn.net/cxllyg/article/details/7655935

其实我只是将参考里面的意思给复述了一下，我好自己理解-_-

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 题目
  2. 2. 解题
  3. 3. 代码
  4. 4. 参考