栈的基本操作（C语言实现）创建，销毁，入栈，出栈

文章目录

• 前言
• 一、栈（Stack）的基本量建立
• 二、栈的基本操作
• • 2.1栈的初始化（STInit）
  • 2.2入栈（STPush）
  • 2.25判断是否为空（STEmpty）
  • 2.3获取栈顶元素（STTop）
  • 2.4出栈（STPop）
  • 2.5栈的大小（STSize）
  • 2.6栈的销毁（STDestroy）
• 总结

前言

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

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

一、栈（Stack）的基本量建立

typedef int STDataType;//栈的数据类型typedef struct stack {STDataType* a;//栈存放的位置int top;//用来标记栈顶int capacity;//栈的容量}ST;//把基本量封装成一个结构体

二、栈的基本操作

2.1栈的初始化（STInit）

void STInit(ST* ps) {assert(ps);//栈可以为空，但是存放栈相关基本量的结构体不能为空ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//初始栈的大小为4if (NULL == ps->a) {perror("Init error");return;}//判断是否为有效空间ps->top = 0;//top从0开始，//top在目前栈顶元素的下一个位置，没存放数据ps->capacity = 4;//初始容量}

2.2入栈（STPush）

void STPush(ST* ps,STDataType x) {assert(ps);if (ps->capacity == ps->top) {STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * 2);//判断当前容量是否支持入栈，不够则进行扩容if (tmp == NULL) {perror("STPush error");return;}ps->a = tmp;//a指向新开辟的空间ps->capacity *= 2;//新空间容量为原来二倍}ps->a[ps->top] = x;//在当前top指向插入xps->top++;//top后移一个位置}

2.25判断是否为空（STEmpty）

bool STEmpty(ST* ps) {assert(ps);return ps->top == 0;//因为top指向最后一个数据的后一个位置，所以top//为0，说明前面没有元素}

2.3获取栈顶元素（STTop）

STDataType STTop(ST* ps) {assert(ps);assert(!STEmpty(ps));//判断是否为空，为空则不能读取栈顶元素return ps->a[ps->top - 1];//因为top指向最后一个数据的后一个位置，//top下标的位置为空，所以要向前一位}

2.4出栈（STPop）

void STPop(ST* ps) {assert(ps);assert(!STEmpty(ps));//判断是否为空，为空则不能出栈ps->top--;//这里出栈并不是真正意义上的销毁数据，//而是让top前移一个位置//而我们不会访问top下标及其以后的位置，所以//达到了类似消除的效果//当top为0就代表出栈了全部数据}

2.5栈的大小（STSize）

int STSize(ST* ps) {assert(ps);return ps->top ;//数组是从0开始的，而top的位置在最后一个数据//后一个位置，所以top就是栈中数据数量}

2.6栈的销毁（STDestroy）

void STDestroy(ST* ps){assert(ps);free(ps->a);//释放空间ps->a = NULL;//别忘了置空ps->top = 0;ps->capacity = 0;}

总结

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。