递归解决栈的进出问题

72 阅读 0 评论 48 点赞

我是靠谱客的博主鳗鱼太阳，最近开发中收集的这篇文章主要介绍递归解决栈的进出问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素

一组不同元素进入栈中由于进站和出栈的时间不同可能会出现不同顺序，比如3个元素进入可能会产生5个不同可能，现输入数字n(0-10^4),求出元素可能的出栈后元素的排列顺序总数

/*
出栈顺序
*/
#include <iostream>
using namespace std;
int f(int n);
int f(int n , int m);//n未进栈的元素,m栈内的元素
int main()
{
int n;
cin>>n;
cout<<f(n);
return 0;
}
int f(int n)
{
return f(n,0);
}
int f(int n,int m)
{
if(n==0) return 1;//出口，当未进栈元素为0时只可能有一种出栈顺序
if(m==0) return f(n-1,1);//当m=0时只能进栈
return f(n-1,m+1)+f(n,m-1);//分别表示进栈和出栈的可能性
}