【算法编程】递归实现栈的逆序
【算法编程】递归实现栈的逆序
  给定⼀个栈，在不使⽤额外数据结构和逆序类库的条件下实现栈内元素的逆序。例如⼊栈的顺序为12345，逆序后对应的出栈的顺序也是12345.
  注意：不能使⽤额外的数据结构，因此传统的借助⼀个新的栈这种⽅法则不可以！
  试题来源：Coding Interviewing Guided (Page 7)
  难度：★★★☆☆
C++源码：
//题⽬：给定⼀个栈，使⽤递归⽅法将其逆序；
#include<iostream>
#include<stack>
using namespace std;
//核⼼算法：递归本质上是⼀个栈，其依次将栈s的栈顶pop后push在计算机内存的栈中，直到s栈空后，再从内存中
//的栈pop并重新push到s中
//该函数⽬标是获取栈s的栈底，并将栈底去除
int get_and_remove_last(stack<int>&s){
int top = s.top();//先从s中pop出栈顶元素
s.pop();
pty()){//如果此时栈为空，则返回此时的top，该元素为s的栈底元素
return top;
}else{
int last =get_and_remove_last(s);//递归，再次获取pop⼀次后的栈顶元素，直到s为空时，此时递归结束，获得栈底元素
s.push(top);//开始回溯，依次⼊栈
return last;
}
}
//算法⼊⼝，递归地对当前的s获取栈底并移除栈底，然后⼊栈
编程递归函数void reverse_stack(stack<int>&s){
if(!s.empty()){
int bottom =get_and_remove_last(s);//获得s的栈底元素，并将s的栈底删除掉
reverse_stack(s);//递归获得最新的s的栈底，并删除，直到获得所有的栈底
s.push(bottom);//依次将最后⼀次得到的栈底元素再次⼊栈，此时⼊栈顺序与s是逆序的
}
}
int main(){
stack<int> s;
cout<<"origin push order:\n";
for(int i=1;i<=3;i++){
s.push(i);
cout<<i<<' ';
}
reverse_stack(s);
cout<<"\nreverse pop order:\n";
while(!s.empty()){
int top = s.top();
s.pop();
cout<<top<<' ';
}
system("pause");
return0;
}
原理讲解：
  我们知道栈数据结构是先进后出的，因此如果实现逆序，传统的⽅法可以对现有的栈，依次将栈顶元素出栈并⼊栈⾄⼀个新的栈，这样可以实现逆序的输出，但其不符合题⽬要求，因此我们选择使⽤递归的⽅法，因为递归的本质就是计算机内存内实现⼀个栈。
  因此，对于⼀个栈 （由栈顶到栈底顺序为321为例），我们对栈的操作只能是对栈顶进⾏pop或push，
⽽如果实现逆序，则必须得获得栈底的元素，并将栈底的元素⼊栈到栈顶。因此整个过程可以分为3个⼦步骤，分别是：
step1：对于当前的栈  ，先将其栈底元素取出，并删除这个栈底元素；如果此时栈为空，则执⾏step3，否则执⾏step2；step2：此时递归执⾏step1，直到栈为空；
step3：此时计算机内存先后保存了s在依次挑选的栈底元素，此时回溯阶段，将这些元素再次⼊栈
程序调⽤的流程图如图所⽰：
  实现这个过程主要由两个函数，如下⾯的代码：
int  get_and_remove_last (stack <int > &s ){
int  top = s .top (); //先从s 中pop 出栈顶元素
s .pop ();
if (s .empty ()){//如果此时栈为空，则返回此时的top ，该元素为s 的栈底元素
return  top ;
}else  {
int  last = get_and_remove_last (s );//递归，再次获取pop ⼀次后的栈顶元素，直到s 为空时，此时递归结束，获得栈底元素
s .push (top );//开始回溯，依次⼊栈
return  last ;
}
}
  这个函数的⽬的是递归的将当前栈  的栈底元素取出并删除。假设当前栈（栈顶到栈底的顺序）为321，执⾏⼀次后返回值为栈底1，此时栈变为32。下⾯这个函数则是将这个栈底元素递归的存⼊计算机内存中的栈，先取出来的栈底元素后⼊栈，因此实现了逆序。s s s
void reverse_stack(stack<int>&s){
if(!s.empty()){
int bottom =get_and_remove_last(s);//获得s的栈底元素，并将s的栈底删除掉
reverse_stack(s);//递归获得最新的s的栈底，并删除，直到获得所有的栈底
s.push(bottom);//依次将最后⼀次得到的栈底元素再次⼊栈，此时⼊栈顺序与s是逆序的}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。