C语言实现出栈序列

110 阅读 0 评论 73 点赞

我是靠谱客的博主顺心煎蛋，最近开发中收集的这篇文章主要介绍C语言实现出栈序列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本文实例为大家分享了C语言实现出栈序列的具体代码，供大家参考，具体内容如下

题目描述:

现在有一个1-n的排列，入栈序列已知，请给出字典序最大的出栈序列。

输入格式

第一行一个整数n。(1<=n<=100)
第二行n个整数，数据确保为1-n的排列。

输出格式

输出n个整数，既字典序最大的出栈序列。

输入样例

5
1 2 4 5 3

输出样例

5 4 3 2 1

解题思路：

1、获取当前数组的最大值，并且需要知道它的下标。所以定义了两个方法，getMax来获取数组的最大值maxNum，getMaxIndex获取最大值的下标max_index。

2、将最大值以及它前面的数字都压入到栈中去

3、这时候将最大值从栈中跳出来。(可要可不要，不要的话可以减少代码的冗余）

4、调用方法getMax,getMaxIndex来获取maxNum后面子数组的最大值r_max，以及下标。

5、将后面数组的最大值r_max和当前栈顶元素进行比较，如果栈顶元素大于等于r_max,那么将栈顶元素tmp从栈中跳出，同时将这个栈顶元素tmp输出。否则，如果r_max大于当前的栈顶元素，那么就将r_max之前的数字压入到栈中，同时需要获取r_max后面数组中的最大值以及下标。

注意这一步，必须是要将后面子数组的最大值r_max和栈顶元素进行比较。而不是拿后面子数组的最大值r_max和maxNum前面数字的最大值进行比较，这样的话，得到的就不是正确的出栈序列了。

6、重复上面的操作，直到将输入的数组已经遍历完了，程序结束。

对应的代码:

#include<stdio.h>
#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
    这里之所以是s.top == 0就为空，是因为下面进行删除操作
    的时候s.top是先减减的，所以在s.top = 1的时候，先进行减1操作，所以
    这时候s.top已经为0，表明我们已经删除了最后一个元素，再来进行这个操作的时候
    s.top为0，所以才用它来判断栈是否为空
    */
     return ERROR;
   }
   c = s.arr[--s.top];//将删除的元素赋值给c
   return OK;
}
//获取栈顶元素
int getTop(Node &s,int &c){
    if(s.top == 0){
    /*
    如果栈为空，那么返回ERROR
    这里之所以是s.top == 0就为空，是因为下面进行删除操作
    的时候s.top是先减减的，所以在s.top = 1的时候，先进行减1操作，所以
    这时候s.top已经为0，表明我们已经删除了最后一个元素，再来进行这个操作的时候
    s.top为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右边最大值下标为:%dn",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;
}

运行结果：