【数据结构】实现栈

大家好，���是苏貝，本篇博客带大家了解栈，如果你觉得我写的还不错的话，可以给我一个赞吗，感谢❤️

目录

• 一 .栈的概念及结构
• 二 .栈的实现
• • 栈的结构体
  • 初始化
  • 销毁
  • 栈顶插入
  • 栈顶删除
  • 显示栈顶元素
  • 是否为空
  • 栈的大小
  • 三. 模块化代码实现
  • • Stack.h
    • Stack.c
    • Test.c
    • 结果演示

      一 .栈的概念及结构

      栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

      压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

      出栈：栈的删除操作叫做出栈，出数据也在栈顶。

      ---

      二 .栈的实现

      栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小（数组的尾插、尾删很方便）。所以下面我们用数组来实现

      1

      栈的结构体

      typedef int STDataType;#define N 10typedef struct Stack{ STDataType _a[N]; int top; // 栈顶}ST;

      上面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈

      typedef int STDataType;typedef struct Stack{STDataType* a;int top;//栈顶int capacity;//容量}ST;

      2

      初始化

      因为我们要对ST类型的变量进行初始化，所以实参要传ST类型变量的地址，用一级指针来接收。因为实参（ST类型变量的地址）不可能为NULL，所以对它断言（下面的接口同理）。

      注意：我们这里的top指的是栈顶元素的下一个，而非栈顶元素，所以将它初始化为0

      void STInit(ST* pst){assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;//指向栈顶元素的下一个}

      3

      销毁

      注意：在这里我们使用的是动态开辟内存，所以要在销毁时释放掉动态开辟的内存，也就是pst->a指向的那个数组

      void STDestroy(ST* pst){assert(pst);if (pst->a != NULL){free(pst->a);pst->a = NULL;pst->capacity = 0;pst->top = 0;}}

      4

      栈顶插入

      再插入元素之前我们要先判断是否要增容，因为在初始化时我们将pst->capacity初始化为0，所以在增容时要特别注意将pst->capacity==0的情况。还要注意对realloc的结果进行判断，防止realloc失败返回NULL，又直接将NULL赋值给pst->a，这样就再找不到开辟的数组了。

      最后不要忘记pst->top++

      void STPush(ST* pst, STDataType x){assert(pst);//判断是否需要增容if (pst->top == pst->capacity){int newcapacity = (pst->capacity == 0) ? 4 : 2 * pst->capacity;ST* tmp = (ST*)realloc(pst->a, newcapacity * sizeof(ST));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}//插入数据pst->a[pst->top] = x;pst->top++;}

      5

      栈顶删除

      删除时我们必须保证栈内有元素，所以要对pst->top>0断言，如果top==0，表示栈内已无元素，返回错误信息，下面的显示栈顶元素同理

      void STPop(ST* pst){assert(pst);assert(pst->top > 0);pst->top--;}

      6

      显示栈顶元素

      STDataType STTop(ST* pst){assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];}

      7

      是否为空

      bool STEmpty(ST* pst){assert(pst);return pst->top == 0;}

      8

      栈的大小

      int STSize(ST* pst){assert(pst);return pst->top;}

      ---

      三. 模块化代码实现

      Stack.h

      #include#include#includetypedef int STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;//初始化void STInit(ST* pst);//销毁void STDestroy(ST* pst);//栈顶插入void STPush(ST* pst, STDataType x);//栈顶删除void STPop(ST* pst);//显示栈顶元素STDataType STTop(ST* pst);//是否为空bool STEmpty(ST* pst);//大小int STSize(ST* pst);

      Stack.c

      #include"Stack.h"//初始化void STInit(ST* pst){assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;//指向栈顶元素的下一个}//销毁void STDestroy(ST* pst){assert(pst);if (pst->a != NULL){free(pst->a);pst->a = NULL;pst->capacity = 0;pst->top = 0;}}//栈顶插入void STPush(ST* pst, STDataType x){assert(pst);//判断是否需要增容if (pst->top == pst->capacity){int newcapacity = (pst->capacity == 0) ? 4 : 2 * pst->capacity;ST* tmp = (ST*)realloc(pst->a, newcapacity * sizeof(ST));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}//插入数据pst->a[pst->top] = x;pst->top++;}//栈顶删除void STPop(ST* pst){assert(pst);assert(pst->top > 0);pst->top--;}//显示栈顶元素STDataType STTop(ST* pst){assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];}//是否为空bool STEmpty(ST* pst){assert(pst);return pst->top == 0;}//大小int STSize(ST* pst){assert(pst);return pst->top;}

      Test.c

      #include"Stack.h"int main(){ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);STPush(&s, 5);while (!STEmpty(&s)){printf("%d  ", STTop(&s));STPop(&s);}printf("\n");return 0;}

      结果演示

      ---

      好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞吗，感谢看到这里，我们下篇博客见❤️