学步园

题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。

分析：就是把栈顶元素依次压入到n, n-1，n-2, ..., 2处。

// 递归法颠倒栈<br /> #include <stack><br /> template<typename T><br /> void ReverseStack(std::stack<T>& s)<br /> {<br /> int count = s.size();<br /> while(count >= 0)<br /> {<br /> T data = s.top();<br /> s.pop();<br /> // 此处不用s.size作为第三个参数<br /> ReverseStack_Sub(s, data, count-1);<br /> --count;<br /> }<br /> }<br /> // 栈顶为第0层，栈底为n-1层，把一个元素写入第floor个<br /> template<typename T><br /> void ReverseStack_Sub(std::stack<T>& s, T data, int floor)<br /> {<br /> // 如果要把一个元素写入floor层，就相当于栈pop处一个元素，<br /> // 然后把当前元素写入到floor-1层，然后再把pop的元素push进来<br /> if(floor > 0)<br /> {<br /> T temp = s.top();<br /> s.pop();<br /> ReverseStack_Sub(s, data, floor-1);<br /> s.push(temp);<br /> }<br /> else<br /> s.push(data);<br /> }