目录
1. 栈的相关概念与结构
2. 栈的实现
2.1 栈实现的底层结构选择
2.2 Stack.h
2.3 Stack.c
2.4 Test_Stack.c
1. 栈的相关概念与结构
1、栈：一种特殊的线性表，只允许在固定的一端插入和删除数据；
允许进行数据插入和删除操作的一端称为栈顶，另一端称为栈底；
栈中的元素遵守后进先出LIFO（Last In First Out）的原则；
2、压栈：栈的插入操作叫做进栈、压栈、入栈。入数据在栈顶；
3、出栈：栈的删除操作叫做出栈。出数据也在栈顶；
2. 栈的实现
2.1 栈实现的底层结构选择
1、若采用数组实现栈，则可将数组头视为栈底，数组尾视为栈顶，出入栈都在数组尾进行操作。
2、若采用单链表实现栈，则将链尾视为栈底，入栈利用头插实现，出栈利用头删实现。
（若将链首视为栈底，入栈通过尾插实现，但出栈较为麻烦）
3、若采用双链表实现栈，则无论将哪端视为栈底，出栈、入栈等方法的实现都非常方便；
相较而言，数组、单链表的方式均可较为便利实现栈。相对而言数组的实现效果更优，数组在尾上插入数据的效率高且代价小。采用数组实现栈。
2.2 Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack {// 动态开辟数组STDataType* a;// top表示栈顶元素的下一个元素的下标int top;int capacity;
}ST;
void STInit(ST* pst);
void STDestory(ST* pst);
// 压栈
void STPush(ST* pst,STDataType x);
// 出栈
void STPop(ST* pst);
// 获取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取栈元素个数
int STSize(ST* pst);
2.3 Stack.c
#include"Stack.h"
// 初始化
void STInit(ST* pst) {assert(pst);pst->a = NULL;// top表示栈顶元素的下一个元素的下标pst->top = 0;// capacity表示栈内元素个数（等价于栈顶元素的下一个元素的下标）pst->capacity = 0;
}
// 销毁
void STDestory(ST* pst) {assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 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;pst->top++;
}
// 出栈
void STPop(ST* pst) {assert(pst);// 判栈非空assert(pst->top>0);pst->top--;
}
// 获取栈顶数据
STDataType STTop(ST* pst) {assert(pst);assert(pst->top>0);return pst->a[pst->top - 1];
}
// 判空
bool STEmpty(ST* pst) {if (pst->top == 0) {return true;}return false;//return pst->top == 0;
}
// 获取栈元素个数
int STSize(ST* pst) {assert(pst);return pst->top;
}
2.4 Test_Stack.c
#include"Stack.h"
int main() {ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);while (!STEmpty(&st)) {printf("%d ", STTop(&st));STPop(&st);}STDestory(&st);return 0;
}注：在使用数组实现栈的方式中，定义栈时的top表示栈顶位置，关于top的具体含义与初始化、销毁、压栈、出栈等操作需要进行对应：
若top表示栈顶元素的下标，则初始化时(栈内无元素)，top=-1，插入时在a[top++]处入栈元素；
若top表示栈顶元素的下一个元素的下标，则初始化时top为0，插入时在a[top]处入栈元素；
（易有top表示栈顶元素下标，但将top初始化为0的错误写法，注意勿混淆）
