栈的反转

实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。
听上去完全是玩弄伎俩的东西。自己思考的话确实不容易想到，所以它的意义更多在于理解递归。

CODE1

    int delLast(stack<int>&s){
        int t=s.top();
        s.pop();
        if(s.empty()){
            return t;
        }
        int u=delLast(s);
        s.push(t);
        return u;
    }

上述函数的功能在于将栈底元素删除，并返回。整个递归过程是这样的：

• 弹出栈顶元素记为t
• 若空，返回t（因为t就是栈底元素），函数退出
• 若不为空：处理栈，返回为u
• 压入t，返回u

说了半天没头没脑的，等于没说。我们举个例子：
国王告诉我：有一座地下塔，去塔底解救公主。
我走到塔前面，打开第一层的大门，发现里面好黑好害怕，于是找了个小弟告诉他说：
从这里下去，到塔底解救公主。
然后我等小弟回来，从他手里接过公主，把第一层的大门关上，带公主回去。
任务完成。
但是那请问这个小弟会怎么做呢？

• 打开所在层的大门
• 交给下一个小弟
• 等下一个小弟完成任务，从他手里接过公主
• 关闭大门
• 抱公主给上一层

唯一不同的是，最后一层的小弟，发现那里没有大门可以开，只有公主。那就直接把公主抱上去就可以了。
这就叫做“层层外包”。
也就是说：

• 弹出栈顶元素记为t（打开某一层的大门）
• 若空，返回t（因为t就是栈底元素），函数退出（抱公主上去）
• 若不为空：处理栈，返回为u（外包给下一层的小弟，等待他抱公主上来）
• 压入t，返回u（关闭大门，抱公主上去）

弹出了一个元素，然后再处理这个栈，感觉上就是处理了栈的下一层。
记得处理完以后把弹出的元素压回去。

CODE2

void rever(stack<int>&s){
        if(s.empty())
            return;
        int t=delLast(s);
        rever(s);
        s.push(t);
        return;
    }

上述函数的作用就是反转整个栈。
如果我有一摞书，希望把它们反转，我只能做的事情是：

• 从一摞书的表面拿起来一本
• 把一本书放在一摞书的表面

因为我们有了之前“釜底抽薪”的函数，所以还可以做一件事：

• 从一摞书中抽取最底层的一本书（此时其他书就会下沉一格）

我需要做的是：

1. 抽出最下面一本
2. 剩下的书交给我的小弟来处理
3. 把抽出的书放回表面

每个小弟所做的工作跟上面是一样的，处理最后的一个小弟：

• 如果发现当前待处理的书没有了，就什么也不做，返回。

栈是一种特别的数据结构，特别在它只能访问栈顶元素。所以它和递归的结合，不仅有趣，而且很讨人烦。