文章目录
- 写在前面
- 1 栈的定义
- 2 栈的初始化
- 3 数据入栈
- 4 数据出栈
- 5 获取栈顶元素
- 6 获取栈元素个数
- 7 判断栈是否为空
- 8 栈的销毁
写在前面
本片文章详细介绍了另外两种存储逻辑关系为 “一对一” 的数据结构——栈和队列中的栈，并使用C语言实现了数组栈。
栈C语言实现源码：栈源码
以栈在存储数据时具有特殊的顺序规则：
栈：使用栈结构存储数据，遵循“**先进后出”**的原则，即最先进栈的数据最后出栈。栈可以分为顺序栈（基于数组实现）和链栈（基于链表实现）。
栈的实现方式分为顺序和链式结构，分别适用于不同的场景。顺序结构在内存中占据一块连续的空间，而链式结构通过节点之间的指针连接。这使得栈和队列在实际应用中更灵活，可以根据具体需求选择不同的实现方式。
1 栈的定义
栈结构的定义通常包括一个动态开辟的数组，用来存储数据，一个用于记录栈顶位置以及一个用于记录栈容量的变量。下面是栈结构的定义：
typedef int STDataType;
//数组栈
typedef struct Stack
{
STDataType* nums;//动态开辟的数组
int top;//栈顶位置
int capacity;//栈容量
}Stack;
2 栈的初始化
刚开始栈是一个空栈，因此需要将栈的元素数组指针 nums 初始化为 NULL，表示栈中当前没有元素。capacity 表示栈的容量，初始时为0，表示栈中没有元素。而将top 初始化为0，表示top指向栈顶元素的下一个位置。
代码如下：
void StackInit(Stack* pst)
{
assert(pst);//检查参数有效性
pst->nums = NULL;
pst->top = pst->capacity = 0;//top初始化为0，说明top指向栈顶元素的下一个位置
}
3 数据入栈
数据入栈的操作：
- 检查栈是否已满，如果满了要进行扩容操作。
- 根据上面栈的初始化操作，我们知道，top是指向栈顶元素的下一个位置，因此，数据入栈时，只需将数据放在top指向的位置，再将top向后移动一个位置即可。
图解如下：
代码如下：
void StackPush(Stack* pst, STDataType x)
{
assert(pst); //检查参数有效性
//检查是否需要扩容
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->nums, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("StackPush->malloc");
exit(-1);
}
pst->nums = tmp;
pst->capacity = newcapacity;
}
//元素入栈
pst->nums[pst->top++] = x;
}
4 数据出栈
我们知道，栈只能在栈顶一端出入数据，出数据时只能出栈顶的数据。
数据出栈的步骤如下：
- 在执行出栈操作之前，需要检查栈是否为空。如果栈为空（即没有数据），则无法执行出栈操作，因为没有数据可以出栈。
- 如果栈不为空，即存在数据，就可以执行出栈操作。调整栈顶指针 top，通过将 top 向前移动一个位置，实现了出栈操作（这里是数组栈，top指向栈顶元素的下一个位置）。
图解如下：
代码如下：
void StackPop(Stack* pst)
{
assert(pst);//检查参数有效性
assert(!StackEmpty(pst));//为空不能进行删除
//元素出栈
pst->top--;
}
5 获取栈顶元素
取栈顶元素的步骤如下：
- 在执行取栈顶元素操作之前，需要检查栈是否为空。如果栈为空（即没有数据），则无法执行此操作。
- top指向栈顶元素的下一个位置，如要获取栈顶元素，因此只需返回top-1位置的元素即可。
代码如下：
STDataType StackTop(Stack* pst)
{
assert(pst);//检查参数有效性
assert(!StackEmpty(pst));//为空不能取栈顶元素
return pst->nums[pst->top - 1];
}
6 获取栈元素个数
栈的栈顶指针top是指向栈顶元素的下一个位置，同时top的值也是栈元素个数。
代码如下：
int StackSize(Stack* pst)
{
assert(pst);//检查参数有效性
return pst->top;
}
7 判断栈是否为空
根据初始化栈的函数我们知道，当栈为空时，栈的栈顶指针top是指向nums数组的0位置。
代码如下：
bool StackEmpty(Stack* pst)
{
assert(pst);//检查参数有效性
return pst->top == 0;
}
8 栈的销毁
根据栈结构的定义，我们知道，栈用来存储数据的数组，是动态申请的，因此栈在销毁时需要手动释放动态申请的空间，同时将top和capacity置为0。
代码如下：
void StackDestroy(Stack* pst)
{
assert(pst);//检查参数有效性
free(pst->nums);
pst->nums = NULL;
pst->top = pst->capacity = 0;
}
至此，本片文章就结束了，若本篇内容对您有所帮助，请三连点赞，关注，收藏支持下。
创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！
如果本篇博客有任何错误，请批评指教，不胜感激 ！！！
