前言
本文章主要介绍用c语言实现栈，包括栈的各个接口比如STInit，STpush，STpop等等
一.栈的概念及结构
栈：一种特殊的线性表，其只允许在固定一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶。另一端称为栈底。栈中的数据元素遵从后进先出的LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶
入栈即加入数据到栈顶
出栈即将栈顶数据删除
二.栈实现的结构选择
1）选择数组来存储栈的数据还是链表来存储？
这涉及到顺序表和链表两种数据结构的特性。两个都能实现栈，但是根据栈最常用的操作是入栈和出栈，即尾删和尾插。而数组的尾删和尾插是优于链表的。因为链表的尾删还要获取尾结点要涉及找尾操作，不像数组可以通过下标直接访问到尾部的空间。
更加详细对比请看这篇文章
顺序表和链表的区别-CSDN博客
先看下要实现的接口函数有哪些，然后相关的头文件也一并列出了。我们用多文件编写这个栈的实现。stack.h放函数的声明，顺便把所有要用的头文件都在这个文件引用。这样在其他文件只要引用一个stack.h文件即可。
stack.c放函数的实现。stack.c放函数的测试（放main函数）。
stack.h文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;
//创建动态栈，栈的核心是对栈顶的操作，所以创建结构体包含栈顶下标top，便于管理栈顶
typedef struct STDataType
{STDataType* a; //使用顺序表来当栈int top; // 栈的最后一位有效元素的后一位的下标 数值上等于栈的所有有效元素数量//比如top初始化为0，则有效元素数为0个，且是‘最后一位有效元素’的后一位下标。//即在此下标对应的空间赋值，就是入栈int capacity; //栈的容量大小（顺序表）
}ST;//初始化栈 -- 注意，每一个接口函数的参数都要有一级指针，因为这样才能实际改变栈。否则就只是实参的拷贝，出函数后就会销毁。
void STInit(ST* ps);//压栈
void STpush(ST* ps, STDataType x);//出栈
void STpop(ST* ps);//释放malloc开辟空间
void STDestroy(ST* ps);//拿到栈顶元素
STDataType STtop(ST* ps);//拿到栈的有效元素个数
int Stsize(ST* ps);//检查栈是否为空
bool STEmpty(ST* ps);stack.c --- 函数的实现
#include "stack.h"void STInit(ST* ps)
{assert(ps); //断言 ，ps指针不能为空ps->a = NULL;ps->capacity = 0;ps->top = 0;
}void STpush(ST* ps, STDataType x)
{assert(ps);
//栈顶到容量顶就扩容if (ps->top == ps->capacity){
//这里用三目运算符是为了应对一开始栈为空的情况，对容量*2并不能实现扩容int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//直接用realloc，当ps->a中是空时，realloc的功能和malloc一样STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);//checkif (tmp == NULL){perror("realloc fail");exit(-1);}//refresh更新ps->capacity = newcapacity;ps->a = tmp;}//push ps->a[ps->top] = x;// initialize a = 0 a就是最后有效元素的后一位下标（其对应位置为空）ps->top++;
}//出栈 只要删减top即可
void STpop(ST* ps)
{assert(ps);assert(ps->top>0);--ps->top;
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->capacity = 0;ps->top = 0;}STDataType STtop(ST* ps)
{assert(ps);//NULL top = 0 无意义，栈顶没有元素可取assert(ps->top > 0);return ps->a[ps->top - 1]; //如我们一开始初始化时一样，top所指下标是最后一个有效元素的下一个
}//栈的最后一位有效元素的后一位的下标 数值上等于栈的所有有效元素数量
int Stsize(ST* ps)
{assert(ps);return ps->top;
}//判断栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0; //为0时表示为空，返回true ，否则返回false
}test.c--主函数的控制
#include "stack.h"int main()
{ST st1;STInit(&st1);STpush(&st1, 1);STpush(&st1, 2);STpush(&st1, 3);STpush(&st1, 4);STpush(&st1, 5);
//栈的打印，打印栈顶元素后出栈，删除栈顶元素以取得下一个栈顶元素。
//实际应用场景也是如此，使用完的栈顶元素就不要了。while (!STEmpty(&st1)){printf("%d ", STtop(&st1));STpop(&st1);}printf("\n");//不要忘了释放malloc出来的空间STDestroy(&st1);return 0;
}
