栈的逆置

发表于 | 分类于 |

       背景：栈中的元素是Integer类型, 从栈顶到栈底依次是 : 4,3,2,1 ,调用该方法后， 元素次序从栈顶到栈底变为:1,2,3,4。注意：只能使用Stack的基本操作，即push,pop,peek,isEmpty，可以使用辅助栈。

       首先明确思路：先写测试用例，再写逆置方法，预先写的测试用例通过则逆置方法完成。

       一、根据需求先写测试用例（TDD设计模式）

       根据需求背景写出测试用例，核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

@Test
public void testReverse() {
	Stack<Integer> s = new Stack<Integer>();
	
	for(int i=1;i<=4;i++){
		s.push(i);
	}
	
	StackUtil.reverse(s);
	
	for(int i=1;i<=4;i++){
		Assert.assertEquals((int)i,(int)s.pop());
	}
	
}

       根据测试用例我们新建StackUtil类，在该类中新建reverse()方法，接下来我们只要补全reverse()方法使其通过测试用例就完成了我们的预期需求。

       二、实现reverse()方法

       本文实现reverse()方法模块写了一个容易犯错误的版本以及多种可以实现reverse()方法的正确版本，方法名会因为版本问题加以一些标识符予以区分（比如版本一方法名为reverse_V1()），测试时测试用例中的方法名和实际方法名一定要改成一致。

       1.第一种容易犯的错误：值传递

       代码如下：

1
2
3
4
5
6
7
8
9
10
11
public static void error_reverse(Stack<Integer> s) {
		if (s == null || s.isEmpty()) {
			return;
		}

		Stack<Integer> tmpStack = new Stack<Integer>();
		while (!s.isEmpty()) {
			tmpStack.push(s.pop());
		}
		s = tmpStack;
	}

       方法的最后tmpStack传给了栈s，但是并没有逆置原始栈s，这里是一个值传递，改变的是原始栈s的拷贝栈s，并没有改变原始栈s。也就是说，tmpStack的值传给了传入栈s的拷贝栈s，拷贝栈s的栈逆置了，但传入栈s并没有受到影响。

       可以在方法的最后加一个直接打印拷贝栈s的遍历，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void error_reverse(Stack<Integer> s) {
		if (s == null || s.isEmpty()) {
			return;
		}

		Stack<Integer> tmpStack = new Stack<Integer>();
		while (!s.isEmpty()) {
			tmpStack.push(s.pop());
		}
		s = tmpStack;
		while (!s.isEmpty()) {
			System.out.print(s.pop() + " ");
		}
	}

       控制台输出如下：

1
2
3
4
1
2
3
4

       由上输出可知：传入栈s的拷贝栈s确实实现了栈的逆置。

       运行测试用例结果如下：

       image

       报错提示java.util.EmptyStackException,因为原始栈s全都pop()了，但是s = tmpStack赋值语句却没有将tmpStack赋值给原始栈s，所以原始栈s是一个空栈。如上述分析以及控制台的输出均可以验证tmpStack赋值给了原始栈s的拷贝栈s，所以这里是一个值传递，需谨慎！

       2.第一种实现：借用两个辅助栈

       核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void reverse_V1(Stack<Integer> s) {
		if (s == null || s.isEmpty()) {
			return;
		}

		Stack<Integer> tmpStack1 = new Stack<Integer>();
		int size = s.size();
		for (int i = 0; i < size; i++) {
			tmpStack1.push(s.pop());
		}

		Stack<Integer> tmpStack2 = new Stack<Integer>();
		for (int i = 0; i < size; i++) {
			tmpStack2.push(tmpStack1.pop());
		}

		for (int i = 0; i < size; i++) {
			s.push(tmpStack2.pop());
		}
	}

       其实就是把原始栈全部导入辅助栈一，然后辅助栈一全部导入辅助栈二，此时辅助栈二和原始栈（未进行导入操作之前）是一模一样的，此时我们再把辅助栈二全部导入空的原始栈，则原始栈就完成了栈的逆置，这也是最简单的思路。

       运行测试用例，结果如下：

       image

       3.第二种实现：借用一个辅助栈

       核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void reverse_V2(Stack<Integer> s) {
		if (s == null || s.isEmpty()) {
			return;
		}

		int size = s.size();
		Stack<Integer> tmpStack = new Stack<Integer>();

		for (int i = 0; i < size; i++) {
			Integer top = s.pop();
			while (s.size() > i) {
				tmpStack.push(s.pop());
			}
			s.push(top);
			while (!tmpStack.isEmpty()) {
				s.push(tmpStack.pop());
			}

		}
	}

       实现思想如下图解：

       image

       image

       运行测试用例，结果如下：

       image

       3.第三种实现：借用一个辅助栈（递归思想）

       核心代码如下：

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
public static void reverse_V3(Stack<Integer> s) {
		if (s == null || s.isEmpty()) {
			return;
		}

		Stack<Integer> tmpStack = new Stack<Integer>();

		while (!s.isEmpty()) {
			tmpStack.push(s.pop());
		}

		while (!tmpStack.isEmpty()) {
			Integer top = tmpStack.pop();
			addToBottom(s, top);
		}

	}

private static void addToBottom(Stack<Integer> s, Integer value) {
		if (s.isEmpty()) {
			s.push(value);
		} else {
			Integer top = s.pop();
			addToBottom(s, value);
			s.push(top);
		}

	}

       实现思想如下图解：

       image

       image

       image

       image

       运行测试用例，结果如下：

       image