目录
引言
栈的概念与结构
栈的实现
定义
初始化
销毁
压栈
检测栈是否为空
出栈
获取栈顶元素
检测栈中有效元素个数
元素访问
源代码
stack.h
stack.c
test.c
引言
数据结构之路经过链表后，就来到了栈（Stack）
栈的概念与结构
栈： 一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素 操作。 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。 栈中的数据元素遵守 后进先出 LIFO （ Last In First Out ）的原则。压栈： 栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。出栈： 栈的删除操作叫做出栈。 出数据也在栈顶 。
栈的实现
栈的实现 一般可以使用 数组或者链表实现 ，相对而言 数组的结构实现更优 一些。因为数组在尾上插入数据的代价比较小。
定义
这里，当前元素个数用栈顶top来表示，是栈独有的表示方法
初始化
栈的初始化，top可以为0或-1，top为0，则指向栈顶元素的下一个位置，top为-1，则指向栈顶元素的位置。这里选用top为0，因为后面写的适合方便理解
销毁
栈的销毁和顺序表一样，直接释放数组空间即可
压栈
压栈前，先判断是否需要扩容，再将元素压栈。因为这里只有压栈函数需要判断扩容，所以就不用专门再写一个扩容函数
这里realloc函数在pst为NULL时，充当malloc的作用，所以既可以为初始栈开辟空间，又可以扩容
检测栈是否为空
专门写一个函数判断，增强复用性和可读性 。如果top为0，则栈为空，返回真；反之，返回假
出栈
出栈前，先assert断言判断，栈是否为空，因为top不能减到负数
获取栈顶元素
同样，先判断栈是否为空，再返回栈顶元素。因为这里top指向的是栈顶元素的下一位，所以下标访问时top要减一
检测栈中有效元素个数
这里很多函数实现都很简单，有些操作直接外部对结构体都可以直接实现，但最后还是写成函数封装，因为top的含义有多重，防止别人使用时误解，导致使用错误
元素访问
栈中元素访问（打印），不是用函数实现。因为它的特殊结构，决定了它的元素不能从任意位置访问 ，必须符合后进先出原则才可以。所以，我们通常用循环的方式进行访问，同时每访问一个元素，就将它弹出栈，在进行下一个元素的访问。
以及变式
有人可能会疑惑，将元素访问以后就弹出栈，不进行其他操作吗？其实，在实际生产中，栈也是这样实现特定的需求的。
这样我们就实现了栈的增删等功能
源代码
stack.h
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//压栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//获取栈顶元素
STDataType STTop(ST* pst);
//检测栈是否为空
bool STEmpty(ST* pst);
//检测栈中有效元素个数
int STSize(ST* pst);stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;//top指向栈顶元素的下一个位置
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->top = pst->capacity = 0;
}
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newCapacity;
}
pst->a[pst->top++] = x;
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
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;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
void TestStack1()
{
ST st;
//初始化
STInit(&st);
//压栈
STPush(&st, 1);
STPush(&st, 2);
printf("%d\n", STTop(&st));
STPop(&st);
STPush(&st, 3);
STPush(&st, 4);
STPush(&st, 5);
//打印
while (!STEmpty(&st))
{
printf("%d\n", STTop(&st));
STPop(&st);
}
//销毁
STDestroy(&st);
}
int main()
{
TestStack1();
return 0;
}
