递归实现 Stack 元素逆序

假设我们将 10、20、30、40、50 压入栈中，则元素在栈中从栈顶到栈底的顺序为：50、40、30、20、10。我们的目标是使用递归实现一个算法，将 Stack 容器中顺序进行逆序，变为：10、20、30、40、50。

实现该需求，我们要分为两步：

1. 编写递归函数能够依次获得栈底元素。比如：我们栈中元素的从栈顶到栈底的顺序为：50、40、30、20、10，则我们的函数能够依次返回 10、20、30、40、50；
2. 编写递归函数按照第一步获得的元素次序的逆序依次入栈。此时，我们依次可以获得 10、20、30、40、50，我们此时就按照逆序 50、40、30、20、10 的顺序依次压栈。此时，输出就变成了 10、20、30、40、50，达到了我们的目标。

我们先完成第一步，编写一个 get_stack_bottom_value 函数用于获得最后一个元素。注意：我们只获得栈底元素，其他元素并不会从栈中删除。

// 获得栈容器当前栈底元素，其他元素删除
template<class T>
T& get_stack_bottom_value(stack<T>& my_stack)
{
	// 获得并弹出栈顶元素
	T top_value = my_stack.top();
	my_stack.pop();

	// 如果栈空，说明 top_value 为栈底元素
	if (my_stack.empty())
	{
		return top_value;
	}

	T bottom_value = get_stack_bottom_value(my_stack);
	
	// 如果不是栈底元素则放回栈中
	my_stack.push(top_value);

	return bottom_value;

}

接下来，编写 reverse_stack 函数实现栈中元素的逆序：

template<class T>
void reverse_stack(stack<T> &my_stack)
{
	if (my_stack.empty())
	{
		return;
	}

	// 获得栈底元素
	T bottom_value = get_stack_bottom_value(my_stack);
	reverse_stack(my_stack);
	my_stack.push(bottom_value);
}

我们接下调用下 reverse_stack 函数，看看能否达到我们的要求：

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> my_stack;
	my_stack.push(10);
	my_stack.push(20);
	my_stack.push(30);
	my_stack.push(40);
	my_stack.push(50);

	reverse_stack(my_stack);

	while (!my_stack.empty())
	{
		cout << my_stack.top() << " ";
		my_stack.pop();
	}

	return 0;
}

程序输出结果：

10 20 30 40 50

至此，搞定我们的需求。