[Daily]仅用递归函数和栈操作逆序一个栈

【题目】

• 一个栈依次压入1，2，3，4，5；那么从栈顶到栈底分别为5，4，3，2，1.。将栈转置

【要求】

• 只能用递归函数来实现。

【分析】
该算法需要两个递归函数。分别是getAndRemoveLastElement()和Reverse()

• 关于getAndRemoveLastElement函数
  • 伪代码如下：

function getAndRemoveLastElement
result=stack.pop();
if stack为空返回结果result
elselast=getAndRemoveLastElement();stack.push(result)  //重新将取出的非栈底元素放回return last

• 上面的伪代码可以理解为：不停地出栈，我们要找的是栈底元素，栈底元素的标志就是：当栈底元素出栈时，栈即变为空栈。
• 利用该标志的代码为：

if stack为空返回结果result

• 当到了栈底，则开始将非栈底的元素重新按顺序压入栈中。而原来的栈底元素一直随着 return result 或 return last 返回到last

last=getAndRemoveLastElement();
stack.push(result)  //重新将取出的非栈底元素放回
return last

• 因此我们无论是仅为1个元素的栈（这种情况返回的是result）还是1个元素以上的栈（这是返回值是last）都返回的是栈底元素。而非栈底元素将会重新压入栈中。

• 关于Reverse函数
  • 整个算法的入口，它利用前一个getAndRemoveLastElement()并自身递归实现了逆序。
  • 利用getAndRemoveLastElement()我们可以获取到栈底元素，而Reverse递归主要是将最后一次获取的栈底元素（即栈顶元素）先入栈。
  • 伪代码如下

function Reverse
if stack为空return;    //禁止实现后面的操作
int i=getAndRemoveLastElement()
Reverse()
i入栈

• Reverse函数会将push操作卡到最后一次获取到的栈底元素（即栈顶元素），当整个栈的元素均获取完后，开始将元素一个个push入栈中。即可达到逆序效果。

【实现】

• 实现语言：C++
• 源代码如下：

/*仅用递归函数和栈操作逆序一个栈*/ 
#include<iostream>
#include<stack>
using namespace std;//第一个递归函数
int getAndRemoveLastElement(stack<int> *_stack)
{int result=_stack->top();  //首先出栈 _stack->pop();if(_stack->empty())        //当出栈后为空时，证明result就是栈底元素return result;        //返回栈底元素 else{//递归调用该函数，last一直被赋值为栈底元素int last=getAndRemoveLastElement(_stack);  _stack->push(result);  //将非栈底元素重新压回栈中   return last;          //一直返回栈底元素	} 	
} //第二个递归函数
void Reverse(stack<int> *_stack)
{if(_stack->empty())    //如果已经操作到最后一个取出的栈底元素（即为栈顶元素），就无任何操作的返回 return;int i=getAndRemoveLastElement(_stack);//未到栈顶元素，继续递归 Reverse(_stack);_stack->push(i); 
} int main()
{stack<int> test;stack<int> *p=&test;int temp;for(temp=1;temp<6;temp++)test.push(temp);Reverse(p);cout<<"逆置之后"<<endl; while(!test.empty()){cout<<test.top()<<" "; test.pop();	}
}

• 控制台截图