1. 可以使用O(N)空间
- 可以使用队列
这个很简单了，就是将栈每个元素依次pop放入队列中，然后从队列中依次push就可以了。 - 只能使用栈
我们知道两个栈是可以实现队列的功能的(这个不知道的童鞋可以看我后续的文章)，所以这里使用两个栈先实现一个队列，然后依据上面的方法就可以了。
2. 只能使用O(1)空间
这个其实是很有趣的问题。解决方法是使用递归。
这里提供两种方法：
循环插入法
将栈顶元素插入栈中，循环(栈的元素个数-1)次，得到反转的栈。
栗子：
- 初试栈[1，2，3，4，5]
- 先把1插入栈底-倒数第一个位置，得到[2，3，4，5，1]
- 把2插入倒数第二个位置，得到[3，4，5，2，1]
......
最终得到[5，4，3，2，1]
注意：将一个元素插入栈的倒数第N个位置可以使用递归实现。
实现代码如下
public class ReverseStack1 {
static int insertStackBottomNPosition(String element, Stack<String> stack, int index) {
if (stack.size() == 0) {
return 0;
}
String tmp = stack.pop();
int i = insertStackBottomNPosition(element, stack, index);
if (i == index) {
stack.push(element);
}
stack.push(tmp);
return i+1;
}
static void reverseStack(Stack<String> stack) {
for (int index = 0; index < stack.size()-1; index++) {
String tmp = stack.pop();
insertStackBottomNPosition(tmp, stack, index);
}
}
public static void main(String[] arg) {
Stack<String> stack = new Stack<>();
stack.push("1");
stack.push("2");
stack.push("3");
reverseStack(stack);
System.out.println(stack);
}
}
递归插入栈底法
反转方法：
- 首先我们pop拿到栈顶元素，然后接下来：
- 反转剩下的栈元素
- 将pop出来的栈顶元素插入栈底即可。
- 说的有点抽象，我们举个例子：
假设栈元素为[1，2，3，4，5]
方法体：
第1步：我们拿到1元素，剩下的栈为[2，3，4，5]
第2步：递归调用本方法得到[5，4，3，2]
第3步：将1插入栈[5，4，3，2]底，成为[5，4，3，2，1]
注意：第3步也是可以使用另一个递归来实现。
实现代码如下：
public class ReverseStack {
static void insertStackBottom(String element, Stack<String> stack) {
if (stack.size() == 0) {
stack.push(element);
return;
}
String top = stack.pop();
insertStackBottom(element, stack);
stack.push(top);
}
static void reverseStack(Stack<String> stringStack){
if (stringStack.size() == 1) {
return;
}
String tmp = stringStack.pop();
reverseStack(stringStack);
insertStackBottom(tmp, stringStack);
}
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
stack.push("1");
stack.push("2");
stack.push("3");
reverseStack(stack);
System.out.println(stack);
}
}
总结一下
- 其实两种方法有些类似：都使用了递归进行将一个元素插入栈的某个位置。第一种方法是每次插入的位置是不定的，第二种方法每次插入的位置是固定的。
- 像数组、链表、栈、队列这种连续的数据，递归往往会是这类问题的巧妙解决办法。
- 其实递归和循环有一些共通的地方，能用循环的地方都可以使用递归来实现。
