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

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

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

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

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

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

輸出樣例
yes

準(zhǔn)備工作：

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

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

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

圖解:

完整代碼(C語(yǔ)言):

#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++;//彈棧字符串后移
        /*
        //獲取棧頂元素,這里之所以不用判斷棧是否為空，是因?yàn)橹饕紤]ch是否等于target
        而此時(shí)target已經(jīng)后移了，所以并不會(huì)造成死循環(huán)
        */
        getTop(s,ch);
     }
     msg++;//當(dāng)ch不等于彈棧字符串的字符的時(shí)候，那么就將后移
  }
  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("請(qǐng)輸入棧的元素個(gè)數(shù):");
  scanf("%d",&n);
  input(msg,n);//調(diào)用input方法，從而輸入n個(gè)數(shù)字
  input(target,n);
  flag = testIsTrue(msg,target);//判斷出棧順序是否為壓棧順序的一種出?？赡?
  if(flag)
    printf("yes");
  else
    printf("no");
  return 0;
}

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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論