C語言實現出棧序列合法性判定

Posted on by

本文實例為大傢分享瞭C語言實現出棧序列合法性判定的具體代碼，供大傢參考，具體內容如下

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

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

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

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

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

輸出樣例
yes

準備工作：

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

解題思路：（主要是通過循環嵌套）

1、通過遍歷msg，將遍歷得到的數字壓入到棧中。
2、每次壓入數字之後，要獲取棧頂元素ch，然後判斷ch是否和當前target下標對應的數字相同，如果相同，那麼就從棧中跳出一個元素，同時target的下標後移。這時候，我們依舊需要從棧中獲取棧頂元素，那這個棧頂元素和當前target下標的數字進行比較，如果相等，那麼繼續重復上述的操作。
這裡之所以需要這麼做，是因為考慮到類似於壓入一個元素之後，就跳出一個元素的可能，所以我們需要在target中找到相同的數字之後，不僅需要將target後移，同時需要將從棧中跳出原來的棧頂元素，然後拿新的棧頂元素和target當前下標的值進行比較，直到新的棧頂元素和target當前下標的值不相等。
3、如果不相等，那麼這時候就將msg後移。重復1、2步驟。直到msg已經遍歷完瞭。
4、這時候如果target已經遍歷完瞭，那麼就說明瞭target就是msg的一種出棧可能，否則，如果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){
        //如果當前棧頂的字符和彈棧字符相同，那麼就從棧中跳出
        popElem(s,ch);
        target++;//彈棧字符串後移
        /*
        //獲取棧頂元素,這裡之所以不用判斷棧是否為空，是因為主要考慮ch是否等於target
        而此時target已經後移瞭，所以並不會造成死循環
        */
        getTop(s,ch);
     }
     msg++;//當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("請輸入棧的元素個數:");
  scanf("%d",&n);
  input(msg,n);//調用input方法，從而輸入n個數字
  input(target,n);
  flag = testIsTrue(msg,target);//判斷出棧順序是否為壓棧順序的一種出棧可能
  if(flag)
    printf("yes");
  else
    printf("no");
  return 0;
}

運行結果:

以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。

推薦閱讀：