バックスタック

質問:
スタックを再帰で逆さまにする.たとえば、スタック{1,2,3,4,5}を入力し、1をスタックの上部に入力します.逆さになったスタックは{5,4,3,2,1}であり,5はスタックの頂上にある.
分析:
問題は簡単で、2つのスタックを直接使用すればいいです.1つのpop、1つのpushで、これは逆になりますが、問題を強化し、別のスタックを使用できない場合は、再帰呼び出しを使用することを考慮することができます(実際には再帰呼び出しもスタックに使用されていますが、プログラム呼び出しで使用されているだけです).プログラム実行は2つの部分に分かれています:1,reverse_stack、スタックの上部から要素をポップアップし、reverseを再帰的に呼び出します.stack、ポップアップ要素を一番下に追加
2,addToBottom,スタックトップをポップアップし,スタックが空になるまでaddToBottomを再帰的に呼び出し,bottom要素をスタックにpushする
アルゴリズムコード:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

void addToBottom(vector<int> &stack, int bottom)
{
	if (stack.empty())
		stack.push_back(bottom);
	else
	{
		int top = stack.back();
		stack.pop_back();
		addToBottom(stack, bottom);
		stack.push_back(top);
	}
	return;
}

void reverse_stack(vector<int> &stack)
{
	if (stack.empty())
		return;

	int top = stack.back();
	stack.pop_back();
	reverse_stack(stack);
	addToBottom(stack, top);

	return;
}

int main()
{
	vector<int> array;

	for (int i = 0; i < 5; i++)
		array.push_back(i);

	reverse_stack(array);

	int num;

	for (int i = 0; i < 5; i++)
	{
		num = array.back();
		array.pop_back();
		cout << num << endl;
	}
	return 0;

まとめ:
このテーマを通じて、再帰の真の意味をもっと深く理解することができて、やはり良いテーマです.