无额外空间逆序栈

//2021/05/27H:\无额外空间的栈逆序-使用递归\无额外空间的栈逆序-使用递归.vcxproj
#include <iostream>
#include <stack>
using namespace std;

int getDownItem(stack<int>& s);
void rStack(stack<int>& s);

void printStack(stack<int> s)
{
	if (s.empty()){
		return;
	}
	cout << s.top() << endl;
	s.pop();
	printStack(s);
}

void test()
{
	stack<int> mys;
	mys.push(4);
	mys.push(3);
	mys.push(2);
	mys.push(1);
	printStack(mys);

	//cout << getDownItem(mys) << endl;
	cout << "逆序之后" << endl;
	rStack(mys);
	printStack(mys);
}

//主要功能函数，实现栈的逆序，并且不使用额外内存空间
//函数1 实现取到栈底元素，并且弹出栈底元素
int getDownItem(stack<int>& s)
{
	int result = s.top();
	s.pop();
	//base case
	if (s.empty()) {
		return result;	//只有一个元素，栈底就是栈头
	}
	int last = getDownItem(s);		//取到剩余部分栈底元素，并且弹出栈底元素
	s.push(result);
	return last;
}

//函数2  实现栈的逆序
void rStack(stack<int>& s)
{
	if (s.empty()) {
		return;
	}
	int ret = getDownItem(s);	//得到栈底元素，并且原栈中该元素已弹出
	rStack(s);					//对剩下的部分逆序
	s.push(ret);				//把元素压回去
}



int main()
{
	test();
	
	cout << "hello world!" << endl;
	system("pause");
	return 0;
}