C语言实现常用数据结构：栈-顺序栈实现（第6篇）

深碍√TFBOYSˉ_ 2022-11-27 12:17 37阅读 0赞

# 栈 #

栈是一种特殊的线性表，其特性是仅能在表尾进行插入或删除的操作，栈中元素的操作是按照后进先出的原则进行，因此栈又称为后进先出线性表（Last In First Out，LIFO数据结构）。

*  栈顶：表尾端称为栈顶
 *  栈底：表头端称为栈底
 *  空栈：不含任何元素的空表称为空栈
 *  出栈：从栈中删除一个元素的操作称为出栈
 *  入栈：从栈中增加一个元素的操作称为入栈

# 顺序栈实现 #

栈有两种存储实现方法，一种是顺序存储实现，一种链式存储实现。考虑简单性和日常使用方便，这里使用顺序存储的方式实现，链式实现可以参照单链表实现。

实现要点：

1.顺序栈使用动态内存分配连续存储空间，当空间不足时，重新申请扩展。

2.使用栈顶和栈底指针指向栈顶和栈底位置。

3.栈顶指针指向栈顶元素下一个空位置上，因此栈顶指针和栈底指针相等时为空栈。

# 代码运行结果 #

输入10个数，后进先出，逆序输出。

请输入数据总个数:10

请依次输入10个整数:0 1 2 3 4 5 6 7 8 9

顺序栈输出结果:9 8 7 6 5 4 3 2 1 0

# 代码实现 #

*/
    #include <stdio.h>
    #include <stdlib.h>
    
    // 栈初始大小
    #define STACK_INIT_SIZE  5
    // 栈空间增量大小
    #define STACK_INCREMENT_SIZE 10
    // 定义栈结构
    typedef struct {
      // 栈底指针
      int *base;
      // 栈顶指针 
      int *top;
      // 栈大小
      int size; 
    }stack; 
     
    // 创建和初始化栈
    stack *create_init_stack()
    {
      // 创建栈结构 
      stack *s = (stack *)malloc(sizeof(stack));
      if(s == NULL)
        return NULL;
      // 分配栈空间
      s->base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));
      if(s->base == NULL)
        return NULL; 
      s->size = STACK_INIT_SIZE;
      // 初始栈为空
      s->top = s->base;
      return s;   
    } 
    // 入栈
    int push(stack *s, int data)
    {
      if(s == NULL)
        return -1;
      // 判断是否栈满
      if(s->top - s->base >= s->size)
      {
        s->base = (int *)realloc(s->base, \
          (s->size + STACK_INCREMENT_SIZE) * sizeof(int));
        if(s->base == NULL)
          return -1;
        s->top = s->base + s->size;
        s->size = s->size + STACK_INCREMENT_SIZE;
      }  
      
      *(s->top) = data;
      s->top++;
      return 0;
    } 
    // 出栈
    int pop(stack *s, int *data)
    {
      if(s == NULL || data == NULL)
        return -1;
      // 判断是否栈空
      if(s->top == s->base)
        return -1;
      *data = *(--s->top);
      return 0;
    } 
    // 查看栈中所有元素
    // 只要调用出栈操作即可 
    void print_stack(stack *s)
    {
      int t;
      while(pop(s, &t) != -1)
        printf("%d ", t);
      printf("\n");
     } 
     
    // 销毁和释放
    void free_stack(stack *s)
    {
      if(s != NULL)
      {
        free(s->base);
        free(s);
      }
    }
    
    int main(void)
    {
      // 创建栈保存数据 
      stack *s = create_init_stack();
      int n,d;
      printf("请输入数据总个数:");
      scanf("%d", &n);
      printf("请依次输入%d个整数:", n);
      int i;
      for(i=0; i<n; i++)
      {
        scanf("%d", &d);
        push(s, d);
      }  
      printf("顺序栈输出结果:");
      print_stack(s); 
      // 释放内存空间 
      free_stack(s);
      return 0;
    }

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[format_png]: /images/20221124/5dcdcb57ebbf467284052656359116f1.png
[format_png 1]: /images/20221124/a1c0934b65a0497ba1b4e943ac454f3e.png