数据结构——栈
一、栈的定义
栈的概念：
栈：栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈遵守一个规则：先进后出，后进先出
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
其实栈的结构就和弹夹的结构一样，后放入的子弹先打出来（后进栈的数据先出栈），最先放入的子弹最后打（先进栈的数据后出栈）。
如下是栈的流程图：
二、栈的结构
typedef int Type;//数据类型的重命名 typedef struct ST { Type* arr; //存储空间基址 int top; //栈顶下标 int capacity; //栈的容量 }ST;三、栈的核心功能
1、栈的初始化和销毁
1.1、栈的初始化
栈顶top初始化时可以有两种方法
1、top初始化为0，指向下一个栈顶元素的存储地址
2、top初始化为-1，指向的是当前栈顶的位置
而此方法top初始化为0，因为当top初始化为0时也可以等价为size，可以知道栈里面有多少个元素
void STInit(ST* ps) { assert(ps); ps->arr = NULL; ps->top = ps->capacity = 0; }1.2、栈的销毁
void STdestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->top = ps->capacity = 0; }2、入栈和出栈操作
2.1、入栈
我们在入栈时需要检查空间是否够用，如果空间满了就需要进行动态扩容
我们入栈之后需要把top++，让top指向下一个入栈元素的地址
void STPush(ST* ps, Type x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ((ps->top == 0) ? 4 : 2 * ps->top); Type* tmp = (Type*)realloc(ps->arr, sizeof(Type) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } ps->arr = tmp; ps->capacity = newcapacity; ps->arr[ps->top++] = x; } else { ps->arr[ps->top++] = x; } }2.2、出栈
出栈就直接使top--，因为top指向的是下一个入栈元素的地址，所以直接top--，当下一个入栈元素入栈之后就会直接覆盖
void STPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; }3、栈中元素个数、栈顶元素和栈是否为空
3.1、栈中元素个数
上面提到过当top初始化为0，就与size具有相同的效果，记录元素的个数，所以我们直接返回top
int STSize(ST* ps) { return ps->top; }3.2、获取栈顶元素
因为top是指向下一个入栈元素的地址，所以当我们需要获取当前栈顶数据时，需要对top进行-1操作，使其指向当前栈顶
int STTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->arr[ps->top - 1]; }3.3、判断栈是否为空
如果top = 0 说明栈里面没有元素返回true，top != 0 说明栈不为空返回false
bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; }四、栈的实现
ST.h
#pragma once #include<stdio.h> #include<assert.h> #include<string.h> #include<stdbool.h> typedef int Type; typedef struct ST { Type* arr; //存储空间基址 int top; //栈顶下标 int capacity; //栈的容量 }ST; //栈的初始化 void STInit(ST* ps); //栈的销毁 void STdestroy(ST* ps); //入栈 void STPush(ST* ps, Type x); //出栈 void STPop(ST* ps); //获取栈中元素个数 int STSize(ST* ps); //获取栈顶元素 int STTop(ST* ps); //判断栈是否为空 bool STEmpty(ST* ps);ST.c
#define _CRT_SECURE_NO_WARNINGS #include "ST.h" //栈的初始化 void STInit(ST* ps) { assert(ps); ps->arr = NULL; ps->top = ps->capacity = 0; } //栈的销毁 void STdestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->top = ps->capacity = 0; } //入栈 void STPush(ST* ps, Type x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ((ps->top == 0) ? 4 : 2 * ps->top); Type* tmp = (Type*)realloc(ps->arr, sizeof(Type) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } ps->arr = tmp; ps->capacity = newcapacity; ps->arr[ps->top++] = x; } else { ps->arr[ps->top++] = x; } } //出栈 void STPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } //获取栈中元素个数 int STSize(ST* ps) { return ps->top; } //获取栈顶元素 int STTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->arr[ps->top - 1]; } //判断栈是否为空 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; }STtest.c
#include"ST.h" int main() { ST s; STInit(&s); STPush(&s,1); STPush(&s, 2); STPush(&s, 3); STPush(&s, 4); STPush(&s, 5); while (STEmpty(&s) != true) { printf("%d ", STTop(&s)); STPop(&s); } return 0; }