数据结构-Pop Sequence

Pop Sequence

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

该题是一种模拟出入栈的过程，比如说 5 6 4 3 7 2 1这个序列，首先我们自然由第一个出栈元素为5，推测出5出栈前栈里面应该为5 4 3 2 1（5为栈顶元素）。然后5出栈，这时第二个元素为6，而栈顶元素为4，应该继续入栈，即6入栈。此时栈顶元素等于6，将6出栈。依此类推，只要比较栈顶元素和将要出栈的元素的大小，就可以知道该进栈还是出栈。若是出现栈顶元素大于将要出栈的元素，或者虽然栈顶元素小于将要出栈的栈顶元素但此时栈已满都说明这个将要出栈的元素是不可能出现的。因此可以判断该出栈序列不合法。

在这里插入代码片

#include<stdio.h>
#include<stdlib.h>
typedef struct STACK *stack;

struct STACK{
 int *data;          //存堆栈数据的空间的指针 
 int top;
 int MAXSIZE;
}; 

stack CreatStack(int maxsize){
 stack s = (stack)malloc(sizeof(struct STACK));
 s->data = (int*)malloc(maxsize * sizeof(int));
 s->MAXSIZE = maxsize;
 s->top = -1;
 return s;
}

void PushStack(stack s,int elem){   //入栈 
 if(s->top == s->MAXSIZE-1){
  printf("STACK IS FULL!");
 }
 else{
  s->data[++(s->top)] = elem;
 }
}

int PopStack(stack s){           //出栈 
 if(s->top == -1){
  printf("STACK IS EMPTY!");
  return;
 }
 else{
  return s->data[(s->top)--];
 }
}

int Top(stack s){                  //栈顶元素 
 return s->data[s->top]; 
}

void StackCheak(int *v,stack s,int n,int k);

int main(){
 int m,n,k;
 scanf("%d %d %d",&m,&n,&k);
 stack s = CreatStack(m);
 int a[n*k];
 for(int i = 0;i<n*k;i++){
  scanf("%d",&a[i]);
 }
 StackCheak(a,s,n,k);
 return 0;
}

void StackCheak(int *v,stack s,int n,int k){
 for(int i = 0;i<k;i++){
  int index = 0;   //数组V的下标，指向下一个将要出栈的元素 
  int num =1;      //顺序入栈1，2...... 
  while(index != n){
   //若栈非空且栈顶元素小于将要比较的出栈元素且栈未满或者栈为空且idx未滑至N(即出栈序列未比较完成
   while(s->top!=-1&&Top(s)<v[index+i*n]&&s->top<s->MAXSIZE-1||s->top==-1&&index!=n){
    PushStack(s,num++);    //num入栈，然后num+1 
   }
   if(s->top!=-1&&Top(s)==v[index+i*n]){  //栈非空且栈顶元素等于将要出栈的元素 
    PopStack(s);
    index++;
   }
   //栈非空且栈顶元素大于将要出栈的元素，或者栈满且栈顶元素不等于将要出栈的元素 
   if(s->top!=-1&&Top(s)>v[index+i*n]||s->top==s->MAXSIZE-1&&Top(s)!=v[index+i*n]){
    printf("NO\n");
    break;
   }
  }
  s->top = -1;   //继续比较下一条序列 
  if(index==n){
   printf("YES\n");
  }
 }
}