forked from destiny1020/algorithm_playground
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathReverseStack.java
More file actions
105 lines (82 loc) · 2.01 KB
/
ReverseStack.java
File metadata and controls
105 lines (82 loc) · 2.01 KB
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package misc;
import org.junit.Test;
import chap1.LinkedStack;
/**
* 颠倒一个栈结构，完全使用递归
* 递归练习
*
* @author jiangr2
*
*/
public class ReverseStack {
/**
* 将传入的栈进行颠倒
*
* @param stack
*/
public static void reverseStack(LinkedStack<Integer> stack) {
if(null != stack && !stack.isEmpty()) {
// 将栈顶元素取出
Integer top = stack.pop();
// 递归地将剩下的元素颠倒
reverseStack(stack);
// 将之前取出的元素放到栈底
insertToStackBottom2(stack, top);
}
}
// public static void reverseStack(LinkedStack<Integer> stack) {
//
// if(null != stack && !stack.isEmpty()) {
//
//
//
// }
// }
public static LinkedStack<Integer> reverseStackDirectly(LinkedStack<Integer> stack) {
if(null != stack && !stack.isEmpty()) {
LinkedStack<Integer> auxiliary = new LinkedStack<Integer>();
while(!stack.isEmpty()) {
auxiliary.push(stack.pop());
}
return auxiliary;
}
return stack;
}
private static void insertToStackBottom(LinkedStack<Integer> stack,
Integer bottom) {
// 当栈为空的时候，将待插入的元素放到栈底
if(stack.isEmpty()) {
stack.push(bottom);
return;
}
// 取出栈顶的元素
Integer top = stack.pop();
// 将传入的栈底元素放到栈底
insertToStackBottom(stack, bottom);
// 还原
stack.push(top);
}
private static void insertToStackBottom2(LinkedStack<Integer> stack, Integer bottom) {
assert (null != stack);
LinkedStack<Integer> auxiliary = new LinkedStack<Integer>();
while(!stack.isEmpty()) {
auxiliary.push(stack.pop());
}
stack.push(bottom);
while(!auxiliary.isEmpty()) {
stack.push(auxiliary.pop());
}
}
@Test
public void testReverseStack() {
LinkedStack<Integer> stack = new LinkedStack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println(stack);
reverseStack(stack);
System.out.println(stack);
}
}