数据结构之栈详解（C语言手撕）

个人名���：

作者简介：一名乐于分享在学习道路上收获的大二在校生

个人主页：GOTXX

个人WeChat：ILXOXVJE

本文由GOTXX原创，首发CSDN

系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路

每日一句：如果没有特别幸运，那就请特别努力！ ————————————————————————————

文章简介：

本篇文章对 用C语言实现栈等相关知识 学习的相关知识进行分享！

如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加油，一起奔跑，让我们顶峰相见！！！

————————————————

一.栈的概念及结构

1.1栈的概念

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

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

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

1.2栈的结构

入数据和出数据都是从栈顶入和出；保持后进先出的原则*

1.3栈的实现

栈的实现：数组和链表都可以用来实现栈，保证先进后出原则；

数组：尾插就是进栈 尾删就是出栈（相比链表较为方便）

我这里定义的是Top指向的是栈顶元素的下一个位置

链表：可以选择头插进栈 头删出栈

如果选择的是尾插和尾删的话，需要找尾灯操作，不方便

1.4栈的实现

数组实现栈（相对于链表，数组实现栈更优）

1.4.1功能函数的实现

一般的栈需要完成这几个函数

1. 栈的初始化
2. 栈的销毁
3. 入栈
4. 出栈
5. 取栈顶元素
6. 判断栈是否为空

void StackInit(ST* st);void StackDestory(ST* st);void StackPush(ST* st, STDateType x);void StackPop(ST* st);STDateType GetTop(ST* st);bool StackEmpty(ST* st);

1.定义一个栈的结构体

这里我们实现的是动态的栈typedef int STDateType;    //方便数据类型的替换typedef struct Stack        {STDateType* a;         //存储数据的数组int top;               int capacity;          //容量}ST;

2.栈的初始化

这里top的初始化不同，top含义就不同；1.如果top初始化给0，则每次入栈后top就会++；当入第一个数据时，top++后为1，则top含义为指向的是栈顶元素的下一个元素2.如果top初始化为-1，则含义为指向栈顶元素void StackInit(ST* st){assert(st);st->a = (STDateType* )malloc(4 * sizeof(STDateType));   if (st->a == NULL){perror("malloc fail");exit(-1);}st->top = 0;             //指向栈顶元素的下一个位置st->capacity = 4;        //初始容量给4}   

3.入栈函数

void StackPush(ST* st, STDateType x){assert(st);if (st->top == st->capacity)      //扩容逻辑与顺序表一样{//扩容STDateType* tmp = (STDateType* )realloc(st->a,sizeof(STDateType) * st->capacity *2);if (tmp == NULL)     {perror("malloc fail");exit(-1);}st->a = tmp;st->capacity *= 2;     //2倍扩容}st->a[st->top] = x;      //尾插数据st->top++;}

4.出栈函数

直接将top--；top--后虽然数据没有改变，但是在下一次入栈时会将原数据给覆盖void StackPop(ST* st){assert(st);st->top--;}

5.获取栈顶元素

STDateType GetTop(ST* st){assert(st);assert(st->top);            //断言return st->a[st->top - 1];    //直接返回top后一个位置的元素}

6.判断栈是否为空

bool StackEmpty(ST* st){assert(st);return st->top;      //返回栈的top,如果为0则为空   非0则不为空；}

7.栈的销毁函数

void StackDestory(ST* st){assert(st);free(st->a);    //释放开辟的空间st->capacity = st->top = 0;    //置空}

1.5总代码

#pragma once#include#include#include#includetypedef int STDateType;typedef struct Stack{STDateType* a;int top;int capacity;}ST;void StackInit(ST* st);void StackDestory(ST* st);void StackPush(ST* st, STDateType x);void StackPop(ST* st);STDateType GetTop(ST* st);bool StackEmpty(ST* st);

#include"Stack.h"void StackInit(ST* st){assert(st);st->a = (STDateType* )malloc(4 * sizeof(STDateType));if (st->a == NULL){perror("malloc fail");exit(-1);}st->top = 0;st->capacity = 4;}void StackPush(ST* st, STDateType x){assert(st);if (st->top == st->capacity){//扩容STDateType* tmp = (STDateType* )realloc(st->a,sizeof(STDateType) * st->capacity *2);if (tmp == NULL){perror("malloc fail");exit(-1);}st->a = tmp;st->capacity *= 2;}st->a[st->top] = x;st->top++;}void StackPop(ST* st){assert(st);st->top--;}STDateType GetTop(ST* st){assert(st);assert(st->top);return st->a[st->top - 1];}bool StackEmpty(ST* st){assert(st);return st->top;}void StackDestory(ST* st){assert(st);free(st->a);st->capacity = st->top = 0;}