快捷導(dǎo)航

C語言實現(xiàn)出棧序列合法性判定

更新時間：2021年05月03日 11:12:18 作者：奮斗的龍貓

這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)出棧序列合法性判定，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了C語言實現(xiàn)出棧序列合法性判定的具體代碼，供大家參考，具體內(nèi)容如下

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。

假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

輸入格式
第一行一個整數(shù)n，表示輸入序列的長度。(1<=n<=10000)
第二行n個整數(shù)，表示棧的壓入順序。
第三行n個整數(shù)，表示棧的出棧順序。

輸出格式
如果是彈出序列，輸出yes，否則輸出no。

輸入樣例
5
1 2 3 8 6
8 6 3 2 1

輸出樣例
yes

準(zhǔn)備工作：

①定義一個棧，并且實現(xiàn)它的基本操作（出棧popStack()/壓棧pushStack()/訪問棧頂元素getTop()/判斷棧是否為空isEmpty()等）
②定義兩個長度為10000的整形數(shù)組的，分別表示要壓入順序的數(shù)字msg以及出棧順序的數(shù)字target.。為了避免要書寫兩個for循環(huán)來輸入，這里可以通過調(diào)用方法input(int *arr,int len)，每次輸入msg/target的時候，只要調(diào)用這個方法即可，從而減少代碼量。

解題思路：（主要是通過循環(huán)嵌套）

1、通過遍歷msg，將遍歷得到的數(shù)字壓入到棧中。
2、每次壓入數(shù)字之后，要獲取棧頂元素ch，然后判斷ch是否和當(dāng)前target下標(biāo)對應(yīng)的數(shù)字相同，如果相同，那么就從棧中跳出一個元素，同時target的下標(biāo)后移。這時候，我們依舊需要從棧中獲取棧頂元素，那這個棧頂元素和當(dāng)前target下標(biāo)的數(shù)字進(jìn)行比較，如果相等，那么繼續(xù)重復(fù)上述的操作。
這里之所以需要這么做，是因為考慮到類似于壓入一個元素之后，就跳出一個元素的可能，所以我們需要在target中找到相同的數(shù)字之后，不僅需要將target后移，同時需要將從棧中跳出原來的棧頂元素，然后拿新的棧頂元素和target當(dāng)前下標(biāo)的值進(jìn)行比較，直到新的棧頂元素和target當(dāng)前下標(biāo)的值不相等。
3、如果不相等，那么這時候就將msg后移。重復(fù)1、2步驟。直到msg已經(jīng)遍歷完了。
4、這時候如果target已經(jīng)遍歷完了，那么就說明了target就是msg的一種出?？赡埽駝t，如果target沒有遍歷完，說明target不是msg的一種出?？赡?。

圖解:

完整代碼(C語言):

#include<stdio.h>
#define ERROR 0
#define OK 1
#define MAX_SIZE 10000
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;
   s.arr[s.top++] = c;
   return OK;
}
int popElem(Node &s,int &e){
   if(s.top == 0)
     return ERROR;
   e = s.arr[--s.top];
   return OK;
}
int getTop(Node &s,int &e){
   if(s.top == 0)
     return ERROR;
   e = s.arr[s.top - 1];
   return OK;
}
int isEmpty(Node &s){
   return s.top == 0;
}
int testIsTrue(int *msg,int *target){
  Node s;
  int ch;
  init(s);
  while(*msg != '\0'){
     pushElem(s,*msg);//將壓棧字符串中的字符壓入棧中
     //獲取棧頂元素
     getTop(s,ch);
     while(ch == *target){
        //如果當(dāng)前棧頂?shù)淖址蛷棗Ｗ址嗤?，那么就從棧中跳?
        popElem(s,ch);
        target++;//彈棧字符串后移
        /*
        //獲取棧頂元素,這里之所以不用判斷棧是否為空，是因為主要考慮ch是否等于target
        而此時target已經(jīng)后移了，所以并不會造成死循環(huán)
        */
        getTop(s,ch);
     }
     msg++;//當(dāng)ch不等于彈棧字符串的字符的時候，那么就將后移
  }
  if(*target != '\0')
    return 0;
  return 1;
}
void input(int *arr,int n){
  int i;
  for(i = 0; i < n; i++)
    scanf("%d",&arr[i]);
}
int main(){
  int msg[10000],target[10000];
  int n,flag;
  printf("請輸入棧的元素個數(shù):");
  scanf("%d",&n);
  input(msg,n);//調(diào)用input方法，從而輸入n個數(shù)字
  input(target,n);
  flag = testIsTrue(msg,target);//判斷出棧順序是否為壓棧順序的一種出?？赡?
  if(flag)
    printf("yes");
  else
    printf("no");
  return 0;
}

運(yùn)行結(jié)果: