出栈序列（C语言)
#include<>
#define ERROR 0
#define OK 1
#define MAX_SIZE 100
#define N 100
typedef struct NODE{
int arr[MAX_SIZE];
int top;
}Node;
void init(Node &s){
s.top = 0;
}
//压栈
int pushElem(Node &s,int c){
if(s.top == MAX_SIZE){
return ERROR;//如果栈满了，那么返回ERROR
}
s.arr[s.top++] = c;
return OK;
}
//跳出栈顶元素
int popElem(Node &s,int &c){
if(s.top == 0){
/*
如果栈为空，那么返回ERROR
这里之所以是 == 0就为空，是因为下面进行删除操作
的时候是先减减的，所以在 = 1的时候，先进行减1操作，所以
这时候已经为0，表明我们已经删除了最后一个元素，再来进行这个操作的时候
为0，所以才用它来判断栈是否为空
*/
return ERROR;
}
c = s.arr[--s.top];//将删除的元素赋值给c
return OK;
}
//获取栈顶元素
int getTop(Node &s,int &c){
if(s.top == 0){
/*
如果栈为空，那么返回ERROR
这里之所以是 == 0就为空，是因为下面进行删除操作
的时候是先减减的，所以在 = 1的时候，先进行减1操作，所以
这时候已经为0，表明我们已经删除了最后一个元素，再来进行这个操作的时候
为0，所以才用它来判断栈是否为空
*/
return ERROR;
}
c = s.arr[s.top - 1];//将栈顶元素赋值给c
return OK;
}
int isEmpty(Node &s){
return s.top == 0;
}
/*
将maxNum及其之前的数字压入栈中，同时返回maxNum的下标
*/
int getMax_index(int *arr,Node &s,int left,int right,int maxNum){
int i;
for(i = left; i < right; i++){
pushElem(s,arr[i]);//将当前的数字压入栈中
if(arr[i] == maxNum){
//如果栈顶元素是最大值，那么就将退出循环遍历
break;
}
}
return i;
}
/*
获取left - right区间的最大值
*/
int arrayMax(int *arr,int left,int right){
int i,maxNum = 0;
for(i = left; i < right; i++){
if(maxNum == 0 || arr[i] > maxNum)
maxNum = arr[i];
}
return maxNum;
}
//获取最大的出栈序列
void getMax(int *arr,Node &s,int left,int right,int maxNum){
if(left >= right){
//如果区间的范围不正确的时候，那么结束递归
return;
}
//tmp表示栈顶元素，r_max表示maxNum后面子数组的最大值,i表示maxNum的下标
int i,tmp,r_max;
/*
将maxNum及它前面的数字压入栈中，同时将maxNum的下标返回
*/
i = getMax_index(arr,s,left,right,maxNum);
r_max = arrayMax(arr,i + 1,right);//获取maxNum后面子数组的最大值
/*
这段代码也可以不写，因为下面会拿栈顶元素和r_max进行比较，所以
maxNum是最大值，必然会先输出manNum的
popElem(s,tmp);//将最大值maxNum赋值给tmp，并从栈中跳出
printf("%d ",tmp);
*/
while(!isEmpty(s)){
getTop(s,tmp);//获取栈顶元素
if(r_max > tmp){
//判断r_max是否大于栈顶元素，如果是，将它及其之前的数字压入栈中，同时获取r_max的下标
i = getMax_index(arr,s,i + 1,right,r_max);
r_max = arrayMax(arr,i + 1,right);//获取 i + 1 到right区间的最大值
// printf("\n右边最大值下标为:%d\n",i);
}else{
//如果r_max小于等于栈顶元素，那么就将栈顶元素从栈中跳出，并将其输出
popElem(s,tmp);
printf("%d ",tmp);
}
}
getMax(arr,s,i + 1,right,r_max);
}
int main(){
int arr[N];
int n,i,maxNum;
Node s;
init(s);//初始栈
printf("请输入栈的元素个数:");
scanf("%d",&n);//输入栈元素个数
for(i = 0; i < n; i++)
scanf("%d",&arr[i]);
maxNum = arrayMax(arr,0,n);//获取left-right区间的最大值
getMax(arr,s,0,n,maxNum);
return 0;
}