基于C语言实现顺序栈

提到栈，首先想到的是栈中元素移动的方式为先进后出，下面基于顺序表来实现栈的一些操作。

下图为入栈和出栈的操作操作，可以从图中看出，最先入栈的在最下面，而出栈的时候却正好相反，最后入栈的要先出来

为了使栈的大小可以一直容纳栈中的元素，在这里在结构体中设定了一个最大长度的变量，当栈中元素充满栈时，栈能够自己扩展容量

  3 typedef char SeqStactType;
  4 typedef struct SeqStact
  5 {                                                                                                           
  6     SeqStactType* data;
  7     size_t size;
  8     size_t capacity;//data指向内存中能最大容纳的元素的个数MAX_SIZE的替代品
  9 }SeqStact;

栈的初始化

说白了，将栈初始化，其实就是开辟一块新的空间来准备存放顺序表的内容，详细见程序

  5 //栈初始化
  6 void SeqStactInit(SeqStact* stack)
  7 {                                                                                                           
  8     if(stack == NULL)
  9     {
 10         //非法操作
 11         return ;
 12     }
 13     stack->size =0;
 14     stack->capacity=1000;
 15     stack->data=(SeqStactType*)malloc(stack->capacity* sizeof(SeqStactType));
 16 }

扩容

若在入栈的时候，栈中元素已经满了，那么再入栈的元素，就超出了栈的容量，这时就需要扩容，而扩容之后的大小设定是根据自己喜好来*设定的，我设定的规则是将原来的大小capacity乘以2再加1，之所以加一是防止原先的capacity是0，若只是单纯的乘以一个数，那么扩容之后的结果将依旧是0，没有改变，详细见程序

 27 //扩容
 28 void SeqStactReSize(SeqStact* stack)
 29 {
 30     if(stack == NULL)
 31     {
 32         //非法操作
 33         return ;
 34     }
 35     if(stack->size<stack->capacity)
 36     {
 37         return ;
 38     }
 39     //扩容策略可按照自己的喜好来定
 40     stack->capacity=stack->capacity*2+1;
 41     SeqStactType* new_ptr=(SeqStactType*)malloc(stack->capacity*sizeof(SeqStactType));
 42     size_t i=0;
 43     for(;i<stack->size;++i)
 44     {
 45         new_ptr[i]=stack->data[i];
 46     }
 47     free(stack->data);                                                                                      
 48     stack->data=new_ptr;
 49 }

入栈

其实在基于顺序表来进行入栈操作，就相当于是将顺序表进行头插一个元素，或者尾插一个元素（这两种方法的栈的头部相反），下面将用尾插法来进行操作

 51 //入栈
 52 void SeqStactPush(SeqStact* stack,SeqStactType value)
 53 {
 54     if(stack == NULL)
 55     {
 56         //非法操作
 57         return ;
 58     }
 59     if(stack->size>=stack->capacity)
 60     {
 61         //扩容
 62         SeqStactReSize(stack);
 63     }
 64     stack->data[stack->size++]=value;
 65     return ;
 66 }

出栈

出栈其实同入栈一样，在基于顺序表来实现出栈操作，其实就是相当于头删或者是尾删（两种方法的头部是相反的），下面将采用尾删的方法来进行操作

 68 //出栈
 69 void SeqStactPop(SeqStact* stack)
 70 {
 71     if(stack == NULL)
 72     {
 73         //非法操作
 74         return ;
 75     }
 76     if(stack->size == 0)
 77     {
 78         //空栈
 79         return ;
 80     }
 81     --stack->size;
 82     return;
 83 }                                                                                                           
 84 

取栈顶元素

其实就是相当于取顺序表的最后一个元素

 85 //取栈顶元素
 86 int SeqStactTop(SeqStact* stack,SeqStactType* value)
 87 {                                                                                                           
 88     if(stack == NULL || value == NULL)
 89     {
 90         //非法操作
 91         return 0;
 92     }
 93     if(stack->size==0)
 94     {
 95         //空栈
 96         return 0;
 97     }
 98     *value=stack->data[stack->size-1];
 99 }

销毁栈

 19 //销毁栈
 20 void SeqStactDestroy(SeqStact* stack)
 21 {
 22     free(stack->data);
 23     stack->size=0;
 24     stack->capacity=0;
 25 }