[C语言 数据结构] 栈

1.什么是栈？

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

我们可以把它看作一个像桶，我们放东西进去一定在桶的顶端，而我们直接拿出桶中的东西也是从顶端拿取。、

2.栈的实现

（声明：C语言的数据结构就是手搓呗，虽然效率低了一点，但是强烈建议大家一起搓一遍，能很好的帮大家理解数据结构的同时，对动态内存管理，指针的理解都有好处）

简单认识了一下栈之后呢我们开始着手实现栈的功能：

栈的实现一般可以使用数组或者链表实现，链表相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。（链表不用移动元素，程序的时间复杂度会大大降低）

好了，接下来大家就看着这个头文件搓起来吧。

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
/*
typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;
*/
// 支持动态增长的栈
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 
int StackEmpty(Stack* ps); 
// 销毁栈
void StackDestroy(Stack* ps); 

以下是我写的，大家可以用作参考

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data) {
	assert(ps);

	//判断是否扩容
	if (ps->_capacity == ps->_top) {
		int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		Stack* tmp = (Stack*)realloc(ps->_a, sizeof(Stack) * newCapacity);
		assert(tmp);
		ps->_a = tmp;
	}
	//加上新数据
	ps->_a[ps->_top] = data;
	ps->_top++;
}
// 出栈
void StackPop(Stack* ps) {
	assert(ps);
	assert(ps->_top);
	ps->_top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps) {
	assert(ps);
	assert(ps->_top);
	return ps->_a[ps->_top-1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps) {
	return ps->_top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps) {
	assert(ps);
	if (ps->_top) {
		return 0;
	}
	else {
		return 1;
	}
}
// 销毁栈
void StackDestroy(Stack* ps) {
	assert(ps);
	if (ps->_a) {
		free(ps->_a);
	}
	return;
}