Reverse a Stack Only with Recursion and That Stack

只用递归和自身反转栈，这题机试没法考，面试考纯属刁难，当作回溯练习食用最佳。

步骤如下：

1. 获取并删除栈底
2. 反转剩余栈
3. 将原栈底入栈

举个例子，要把 [1, 2, 3, 4, 5 变为 [5, 4, 3, 2, 1

1. 获取并删除栈底 1，变为 [2, 3, 4, 5
2. 反转剩余栈，变为 [5, 4, 3, 2
3. 原栈底 1 入栈，变为 [5, 4, 3, 2, 1

第 1 步也可递归，出口是只有一个元素，此时弹栈顶返回。否则原问题等价于去掉栈顶，递归子栈，恢复栈顶。这样完美符合它的定义，即删除栈底并返回，剩余元素顺序不变。

int del_bottom(stack<int>& s) {
    int top = s.top(); s.pop();
    if (s.empty()) return top;

    int bottom = del_bottom(s);
    s.push(top); // 回溯恢复现场

    return bottom;
}

void reverse(stack<int>& s) {
    if (s.size() <= 1) return;
    int bottom = del_bottom(s);
    reverse(s);
    s.push(bottom);
}

其实，你还是用了其它栈，即函数调用栈，进入下层递归时，弹出的栈顶被自动压入系统栈，返回时又被你压回原栈，只是原栈底没有被压回。