top push div emp return 递归实现 开始 stack
2017-06-23 20:36:02
刚开始思考这个问题的时候陷入了一个误区,就是以为只能用一个递归完成。
然而事实上,可以使用两个递归来完成这个功能。
具体思考是这样的,首先递归其实是将问题规模缩小了,每次处理更小的问题。针对这题来说,更小的问题应该是去除底部那个数后的逆序再加上最后的数。
当然,你可能会问,什么不是去掉最上面的数,然后将它再放到最前面,理由很简单,栈是一种后进先出的数据结构,这种类型的数据结构适合的是在尾部添加数据,而非在首部添加数据,所以更清晰的或者说更适合栈的操作是先把底部数据 remove, 再对栈进行逆序操作,最后将它再 push 进末尾。
因此,核心操作就两个,一个是 remove 底部数据,二是 reverse。
- intgetlast(stack<int>& s)
- {
- if(s.empty()) {cout<<"当前栈为空"<0);}
- else
- {
- inttemp=s.top();
- s.pop();
- if(s.empty())return temp;
- else
- {
- intt=getlast(s);
- s.push(temp);
- return t;
- }
- }
- }
- voidreverse(stack<int>& s)
- {
- if(s.empty())return ;
- else
- {
- inttemp=getlast(s);
- reverse(s);
- s.push(temp);
- }
- }
只使用递归实现栈的逆序操作
来源: http://www.bubuko.com/infodetail-2135007.html