栈与队列03：如何仅用递归函数和栈操作逆序一个栈

【题目】

        一个栈一次压入1、2、3、4、5，那么从栈顶到栈底分别是5、4、3、2、1。将这个栈转置后，从栈顶到栈底为1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

 

【解答】

 

       递归函数一：将栈stack的栈底元素返回并移除。具体过程见代码：

 

【代码实现1】

#include <stack>

static int getAndRemoveLastElement(std::stack<int> &stack){
	int result = stack.top();
	stack.pop();
	if (stack.empty()){
		return result;
	}
	else{
		int last = getAndRemoveLastElement(stack);
		stack.push(result);
		return last;
	}
}

 

        递归函数二：逆序一个栈，用到上面提到的getAndRemoveLastElement方法。

 

【代码实现2】

static void reverse(std::stack<int> &stack){
	if (stack.empty()){
		return;
	}
	int i = getAndRemoveLastElement(stack);
	reverse(stack);
	stack.push(i);
}