栈问题之栈的反转

1. 可以使用O(N)空间

• 可以使用队列
  这个很简单了，就是将栈每个元素依次pop放入队列中，然后从队列中依次push就可以了。
• 只能使用栈
  我们知道两个栈是可以实现队列的功能的(这个不知道的童鞋可以看我后续的文章)，所以这里使用两个栈先实现一个队列，然后依据上面的方法就可以了。

2. 只能使用O(1)空间

这个其实是很有趣的问题。解决方法是使用递归。
这里提供两种方法：

循环插入法

将栈顶元素插入栈中，循环(栈的元素个数-1)次，得到反转的栈。
栗子：

1. 初试栈[1，2，3，4，5]
2. 先把1插入栈底-倒数第一个位置，得到[2，3，4，5，1]
3. 把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);
    }
}

递归插入栈底法

反转方法：

1. 首先我们pop拿到栈顶元素，然后接下来：
2. 反转剩下的栈元素
3. 将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);
    }
}

总结一下

• 其实两种方法有些类似：都使用了递归进行将一个元素插入栈的某个位置。第一种方法是每次插入的位置是不定的，第二种方法每次插入的位置是固定的。
• 像数组、链表、栈、队列这种连续的数据，递归往往会是这类问题的巧妙解决办法。
• 其实递归和循环有一些共通的地方，能用循环的地方都可以使用递归来实现。