目录:
一、栈的概念
二、栈的实现
1.栈的初始化
2.栈的销毁
3.入栈
4.出栈
5.获取栈顶数据
6.判断栈是否为空
7.获取栈的个数
三、代码
一、栈的概念
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
例：比如手枪弹夹，先压进去的子弹往往是后发射出去，也就是遵循后进先出的原则。
首先来创建一个结构体，我们是基于数组实现的栈，一个栈首先要有数组存放数据，给一个top表示个数，给一个capacity表示空间大小：
typedef int stacktype;
typedef struct Stack
{stacktype* a;//动态数组int top; //个数int capacity;//空间
}ST;二、栈的实现
1.栈的初始化
一开始，数组为空，并且top和capacity都为0，这里的top有两种初始化方法，如果我们想让他指向栈中的最后一个数据，那么它的值就不能是数组的起始下标0，而应该给一个无关的数，比如-1；第二种就是top表示栈顶数据的下一个位置，那我们就可以给他赋值0，这里我们使用第二种方法：
void STInit(ST* pst)//初始化
{assert(pst);pst->a = NULL;pst->top = 0;//基于size指向的是栈顶数据的下一个位置pst->capacity = 0;
}2.栈的销毁
删除也是很简单，原理和顺序表都差不多：
void STDestroy(ST* pst)//销毁
{assert(pst);free(pst->a);//free掉pst->a = NULL;//置为空，防止变成野指针pst->top = 0;pst->capacity = 0;
}3.入栈
首先要明白，栈是栈顶入，栈顶出，所以所有数据都从栈顶进入，也就是top的位置，随后top++就可以，扩容和顺序表一样，详情可以参考：https://blog.csdn.net/xpcxpt/article/details/147466492?spm=1001.2014.3001.5501
总体代码如下：
void STPush(ST* pst, stacktype x)//插入 入栈
{assert(pst);//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;stacktype* tmp = (stacktype*)realloc(pst->a, newcapacity * sizeof(stacktype));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}4.出栈
出栈也就是删除一个栈顶的数据，那只需要让top--就可以了：
void STPop(ST* pst)//删除 出栈
{assert(pst);assert(pst->top > 0);//top是非负数pst->top--;//删除一个
}5.获取栈顶数据
top的位置的栈顶数据的下一个位置，所以要想获取栈顶元素，就要获取top-1位置的元素:
stacktype STTop(ST* pst)//获取栈顶数据
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}6.判断栈是否为空
直接判断栈中数据数量top是否为空，这里可以使用bool类型，不为空返回true，为空返回fulse：
bool STEmpty(ST* pst)//判断栈是否为空
{assert(pst);return pst->top == 0;
}7.获取栈的个数
这里也是非常简单，就是获取top的大小，几行代码就搞定了：
int STSize(ST* pst)//判断栈的数据个数
{assert(pst);return pst->top;//从0开始的，所以返回size的大小-1,也就是下表从0-top-1，一共top个
}三、代码
总体代码如下:
test.c:
#include "stack.h"int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);//printf("%d ", STTop(&s));STPush(&s, 3);STPush(&s, 4);while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}STDestroy(&s);
}
stack.h:
#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int stacktype;
typedef struct Stack
{stacktype* a;//动态数组int top; //个数int capacity;//空间
}ST;void STInit(ST* pst);//初始化
void STDestroy(ST* pst);//销毁
void STPush(ST* pst, stacktype x);//插入 入栈
void STPop(ST* pst);//删除 出栈
stacktype 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->top = 0;//基于size指向的是栈顶数据的下一个位置pst->capacity = 0;
}void STDestroy(ST* pst)//销毁
{assert(pst);free(pst->a);//free掉pst->a = NULL;//置为空，防止变成野指针pst->top = 0;pst->capacity = 0;
}void STPush(ST* pst, stacktype x)//插入 入栈
{assert(pst);//扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;stacktype* tmp = (stacktype*)realloc(pst->a, newcapacity * sizeof(stacktype));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);//top是非负数pst->top--;//删除一个
}
stacktype 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;//从0开始的，所以返回size的大小-1,也就是下表从0-top-1，一共top个
}
