#include <iostream>
#include <stack>
#include <vector>
using namespace std;
static int count=0;
/**
mystack:代表堆栈
input:代表要压入堆栈的数字序列
output:代表弹出堆栈的数字序列
*/
void countSequeue(stack<int> mystack,vector<int> input,vector<int> output){
/**
当input为空时，说明等待进栈的队列为空，展示结果：将前面出栈数字和栈中的数字打印出来
*/
if(input.empty()){
for(vector<int>::iterator b=output.begin();b<output.end();b++){
cout<<*b<<" ";
}
while(!mystack.empty()){
int value=mystack.top();
cout<<value<<" ";
mystack.pop();
}
cout<<endl<<"执行次数"<<++count<<endl;
return;
}
/**
将原来的栈复制到两个栈中，给下面两个递归函数使用
*/
stack<int> tmp,newstack,newstack2;
while(!mystack.empty()){
tmp.push(mystack.top());
mystack.pop();
}
while(!tmp.empty()){
newstack.push(tmp.top());
newstack2.push(tmp.top());
tmp.pop();
}
/**
将input复制一份留给下一个递归函数使用
*/
vector<int> tmpinput=input;
//首先将下一个数压入堆栈中，进行迭代
newstack.push(input.front());
input.erase(input.begin());
countSequeue(newstack,input,output);
//进行下一种情况，就是先将堆栈中的数弹出，进行迭代
if(!newstack2.empty()){
output.push_back(newstack2.top());
newstack2.pop();
countSequeue(newstack2,tmpinput,output);
}
}
int main(){
stack<int> mystack;
vector<int> output;
vector<int> input;
for(int i=0;i<3;i++)
input.push_back(i+1);
countSequeue(mystack,input,output);
return 0;
}
解释：采用递归的方式模拟数字序列压栈出栈操作，能够输出搜索的出栈序列，对一个{1,2,3}的序列，出栈结果如下
3 2 1 执行次数1 2 3 1 执行次数2 2 1 3 执行次数3 1 3 2 执行次数4 1 2 3 执行次数5 Press any key to continue