递归实现栈中元素的逆置

浅浅的花香味﹌ 2022-07-21 02:14 163阅读 0赞

题目：

一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现了栈中元素的逆序，请设计一个算法实现逆序栈的操作，但是只能用递归函数来实现，而不能用另外的数据结构。

给定一个栈Stack以及栈的大小top，请返回逆序后的栈。

测试样例：

[1,2,3,4,5],5

返回：[5,4,3,2,1]

![Center][]

//一个栈依次压入1, 2, 3, 4, 5   那么从栈顶到栈底分别为
    //5, 4, 3, 2, 1。将这个栈转置后，从栈顶到栈底为1, 2, 3, 4, 5，
    //也就是实现了栈中元素的逆序，请设计一个算法实现逆序栈的操作，
    //但是只能用递归函数来实现，而不能用另外的数据结构。
    //给定一个栈Stack以及栈的大小top，请返回逆序后的栈。
    //测试样例：
    //[1, 2, 3, 4, 5], 5
    //返回：[5, 4, 3, 2, 1]
    #include<iostream>
    using namespace std;
    #include<stack>
    #include<vector>
    class ReverseStack 
    {//类似于层次遍历
    public:
    	int level = 0;//全局变量
    	vector<int> reverseStackRecursively(vector<int>& stack, int top)
    	{//1.在递归中，由于每次递归都会改变数据，所以& 是一个很神奇的东西在递归中
    //2.或者每次递归中，原容器进行接收，这两样东西的效果都是一样的，防止改变
    		if (top > 0)
    		{
    			int val = stack[top - 1];//每次递归时从尾到头保存元素 5->4->3->2->1
    			++level;//层+1
    			stack = reverseStackRecursively(stack, top - 1);//top-1;向深层次进行递归
    			//不断递归，一直递归到个数top为0，在返回到这里
    			--level;//递归到最深层后，level变为5，先--level，让level变为4
    			stack[level] = val;//方便作为下标进行数据交换
    			//最深层中数据为1，然后进行交换数据
    		}
    
    		return stack;//可以用作递归返回，返回到上一层
    		//返回到stack = reverseStackRecursively(stack, top - 1);然后继续进行数据交换
    	}
    
    };
    int main()
    {
    	vector<int> s;
    	s.push_back(1);
    	s.push_back(2);
    	s.push_back(3);
    	s.push_back(4);
    	s.push_back(5);
    	ReverseStack  r;
    	vector<int> ret=r.reverseStackRecursively(s, s.size());
    	for (int i = 0; i < 5; i++)
    		cout << ret[i] << " ";
    	cout << endl;
    	system("pause");
    	return 0;
    }

[Center]: /images/20220720/05127ed422194431afe280cd8b17384f.png