题解 | #栈的压入、弹出序列#

一开始以为是寻找逆序数。

后来才发现入栈顺序不一定是按照从小到大的顺序。

参考了评论区大佬的思想，让我学到许多。

用出栈入栈子函数添加了一些限制条件和功能，使该子函数更加简洁高效，不用再在该功能中控制指针。

主要思想是：

开辟一个新栈进行比较，模拟入栈出栈的过程。

按入栈表中顺序进行入栈操作，每入栈一次，就和出栈表中的首个元素进行比较，

如果相同，则出栈，并指向出栈表的下一个元素，如果不同，则继续入栈。

到全部入栈表中元素访问完毕时，将以新栈栈顶和出栈表的表头元素比较。

如果能全部出栈，则将会一直遇到新栈顶和出栈表表头元素相等的情况。

如果不能，会在还没有全部出完时结束循环。

记录出栈表指针移动的次数可以判断有无清空新栈，做标志位。

该标志位通过和出栈表中元素总个数比较来判断是否可按出栈表中顺序出栈完毕。

#include<stdbool.h>
#define INIT_SIZE 4
#define BUFFER_SIZE 8
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pushV int整型一维数组 
 * @param pushVLen int pushV数组长度
 * @param popV int整型一维数组 
 * @param popVLen int popV数组长度
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

typedef struct stack{//栈结构
    int *top;
    int *bottom;
    int size;
}set;

set *stack_init()//初始化
{
    set * stack=(int*)malloc(sizeof(int));
    if(stack==NULL)
    {
        return -1;
    }
    stack->bottom=(int*)malloc(sizeof(int)*INIT_SIZE);
   if(stack->bottom==NULL)
   {
       return NULL;
   }
    stack->top=stack->bottom;//初始栈为空
    stack->size=INIT_SIZE;//栈空间
    
    return stack;
    }
set *stack_push(set *stack,int p_data)//input
{
    if(stack==NULL)
    {
        return NULL;
    }
    if(stack->top-stack->bottom>=stack->size)
    {
        stack->top=stack->bottom+stack->size;//move the top pointer
        stack->size=stack->size+BUFFER_SIZE;//enlarge the size of buffer
    }
    *(stack->top)=p_data;//GET DATA;
    stack->top++;//TOP POINTER PLUS   
    
    return stack;
}
set *stack_pop(set *stack)//output
{
    if(stack==NULL)
    {
        return NULL;
    }
    stack->top--;//top pointer bonus one to get the forward value
    int data;
    data=*(stack->top);  
    
    return data; 
}



bool IsPopOrder(int* pushV, int pushVLen, int* popV, int popVLen ) {
    // write code here
    //先入栈后比较
    int i=0,j=0;
    set *stack=stack_init();//开辟一个新空栈
    //入新栈，判断当前栈顶是否与出栈表中首个相等。
    //同则将新栈栈顶出栈，出栈表指针后移；异则继续入栈。
    for(j=0;j<pushVLen;j++)
    {
        stack_push(stack,  *(pushV+j));//入新栈
            
        while(*(stack->top-1)==*(popV+i)&&i<popVLen&&(stack->top!=stack->bottom))
        //注意入栈后栈顶内容为空，需与上一个入栈元素比较
        //如果成功，栈空结束
        //不成功，则未到新栈栈空就结束，
        //i是标志位，代表是否所有出栈表中元素都访问到了，全访问到就证明栈空，未全访问到则不空
        
            {
            i++;
            stack_pop(stack);//遇到和栈顶和出栈表首相同，则使新栈出栈。
            }
    }       
       if(i==popVLen)//是否已经访问全部出栈表中元素
        {
            return true;
        }
        else
        {
            return false;
        }  
        
}