数据结构：栈（含源码）
目录
一、栈的概念和结构
二、栈的实现
2.1 头文件
2.2 各个功能的实现
初始化栈
入栈
出栈
获取栈顶元素和栈中有效个数
判断栈是否为空
栈的销毁
2.3 测试
完整源码
一、栈的概念和结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵守后进先出的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
后进先出示意图
后进先出步骤分解
二、栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。
2.1 头文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);我们在创建栈时，一般是创建支持动态增长的栈，定长的静态栈不实用。这里的top就相当于是存储栈顶元素，capacity在入栈时为是否要增容提供判断条件。
2.2 各个功能的实现
初始化栈
void StackInit(Stack* ps)
{ps->a = NULL;ps->top = ps->capacity = 0;
}数组置空，栈顶数字和容量归0。
入栈
void StackPush(Stack* ps, STDataType data)
{if (ps->top == ps->capacity){int newcapacity =ps->capacity== 0 ? 4 : ps->capacity*2;STDataType* tem = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));if (tem == NULL){perror("realloc fail");return;}ps->capacity = newcapacity;ps->a = tem;}ps->a[ps->top++] = data;
}先判断容量是否有足够的空间让数据入栈，在第一次入栈是先给定4个空间，后面每次不够时就将空间数乘以2， 还有一个判断是否开辟成功（这个可以不写，一般都会开辟成功）。
出栈
void StackPop(Stack* ps)
{assert(ps);ps->top--;
}出栈非常的简单，只要将top数减少一个就行了，相当于是下一次入栈是直接把这个数据修改掉，就算没修改，打印时也不影响。
获取栈顶元素和栈中有效个数
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top-1];
}int StackSize(Stack* ps)
{assert(ps);return ps->top;
}两个都是比较简单的代码，只要用top就可以知道栈顶元素和栈中的元素个数。
判断栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}栈中个数为0那么就是空栈，也是直接用到了top，。
栈的销毁
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}和初始化类似，数组置空，top和capacity归0。
2.3 测试
写完代码后还是需要测试的
int main()
{Stack s;StackInit(&s);StackPush(&s, 1);StackPush(&s, 2);StackPush(&s, 3);StackPush(&s, 4);StackPush(&s, 5);while (!StackEmpty(&s)){printf("%d\n", StackTop(&s));StackPop(&s);}StackDestroy(&s);
}我这里就是先入栈五个元素，然后在一个循环中打印，每打印一个就将栈顶元素出栈，直到栈变为空栈结束打印。
完整源码
zhan.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; int capacity;
}Stack;void StackInit(Stack* ps);void StackPush(Stack* ps, STDataType data);void StackPop(Stack* ps);STDataType StackTop(Stack* ps);int StackSize(Stack* ps);bool StackEmpty(Stack* ps);void StackDestroy(Stack* ps);zhan.c
#include"zhan.h"
void StackInit(Stack* ps)
{ps->a = NULL;ps->top = ps->capacity = 0;
}
void StackPush(Stack* ps, STDataType data)
{if (ps->top == ps->capacity){int newcapacity =ps->capacity== 0 ? 4 : ps->capacity*2;STDataType* tem = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));if (tem == NULL){perror("realloc fail");return;}ps->capacity = newcapacity;ps->a = tem;}ps->a[ps->top++] = data;
}
void StackPop(Stack* ps)
{assert(ps);ps->top--;
}
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top-1];
}
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}最好是要自己写一遍，这样才能加深印象，也更能理解栈相关的知识。
本篇关于栈的内容就到这里了，希望对各位有帮助，如果有错误欢迎指出，感谢支持。
