数据结构初开课：栈的实现-程序员充电站

本次编译环境为VS2022

文章目录

前言
- 栈的实现
- - 1.什么是栈
  - 2.栈的实现
  - - 一.头文件和源文件的创建以及头文件中的内容
    - 二.功能代码的实现
    - - 1.定义和销毁
      - 2.增加和删除
      - 3.判断空找栈顶获取栈中的个数
总结

前言

在我们了解完链表：单链表和双链表后我们将开始栈和队列的学习
今天我们学习的是栈的代码实现其中会有部分画图内容和代码内容方便各位理解

栈的实现

1.什么是栈

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

通过图例可以更快地理解

2.栈的实现

一.头文件和源文件的创建以及头文件中的内容

老样子一个.h 文件和一个 .c文件
给到.h文件的实现代码`

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefintSTDateType;typedefstructStack{STDateType*a;inttop;intcapacity;}ST;//功能函数//定义voidSTInit(ST*ps);//销毁voidSTDestory(ST*ps);//插入voidSTPush(ST*ps,STDateType x);//删除voidSTPop(ST*ps);//找栈顶STDateTypeSTTop(ST*ps);//判断空boolSTEmpty(ST*ps);//获取栈中的个数intSTSize(ST*ps);

二.功能代码的实现

1.定义和销毁

定义和销毁其实和我们以前学过的链表顺序表大差不差这里放出实现代码直接给各位观看

voidSTInit(ST*ps){assert(ps);ps->a=NULL;ps->capacity=0;ps->top=0;}//销毁voidSTDestory(ST*ps){assert(ps);free(ps->a);ps->a=NULL;ps->capacity=ps->top=0;}

2.增加和删除

了解完图例后呈现代码给各位

//插入voidSTPush(ST*ps,STDateType x){assert(ps);//当我们的 top = capacity的时候 要进行扩容操作 否则无法容纳归纳topif(ps->top=ps->capacity){intnewcapacity=ps->capacity==0?4:2*ps->capacity;STDateType*tmp=(STDateType*)realloc(ps->a,sizeof(STDateType)*newcapacity);if(tmp==NULL){perror("realloc fail");return;}//完成扩容操作ps->a=tmp;ps->capacity=newcapacity;}//扩容结束后 进行插入操作ps->a[ps->top]=x;ps->top++;}//删除voidSTPop(ST*ps){assert(ps);assert(ps->top>0);//top不大于0删不了啊ps->top--;}

这里的扩容操作与顺序表中的几乎一样注意realloc的类型和newcapacity的书写即可

3.判断空找栈顶获取栈中的个数

这三个功能函数其实都大同小异
都是根据 top来进行实现
判断空只需看 top==0 如果等于0 则栈为空

找栈顶也是看数组中[top-1]的值即可

获取栈中的个数其实就是看top的大小当有一个值时 top = 1
同理可得看top大小就能看出栈中的个数
给到代码给各位

//找栈顶STDateTypeSTTop(ST*ps){assert(ps);assert(ps->top>0);returnps->a[ps->top-1];}//判断空boolSTEmpty(ST*ps){assert(ps);returnps->top==0;}//获取栈中的个数intSTSize(ST*ps){assert(ps);returnps->top;}