C语言 栈与数组的实现详解
栈的实现
首先我们思考一个问题，什么是栈？
栈是数据结构的一种，栈在我们日常编码中遇到的非常多，很多人对栈的接触可能仅仅局限在 递归使用的是栈 和 StackOverflowException，栈是一种后进先出的数据结构(可以想象生化金字塔的牢房和生化角斗场的狗洞)。
栈的定义
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素
栈的应用广泛，比如你的程序执行查看调用堆栈、计算机四则加减运算、算法的非递归形式、括号匹配问题等等。所以栈也是必须掌握的一门数据结构。最简单大家都经历过，你拿一本书上下叠在一起，就是一个后进先出的过程，你可以把它看成一个栈。下面我们介绍数组实现的栈两种形式。
数组实现
静态栈
一般不推荐使用这种方法，因为当空间不够用时，增容会有点麻烦，不实用。
typedef struct Stack
{
STDataType _a[]; //STDataType 为int宏定义，当然你也可以将它定义为其他类型，宏定义是为了换栈类型的时候方便一点
int _top; // 栈顶
int _capacity; // 容量
}Stack;
动态栈
相比静态栈，动态栈空间不够时可以直接时用realloc动态扩容，但是动态扩会有一定程度的消耗，我们会直接扩容一倍，当使用不完时会造成一定程度的空间浪费。
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);
栈的初始化
void StackInit(Stack* ps)
{
ps->_a = NULL; //初始化时将指针指向空,此时没有开辟空间
//这里可以将top赋值为0，也可以赋值为-1。
ps->_top = -1; //赋值为0时表示top为栈顶元素的下一个位置的下标，赋值为-1时top为栈顶元素的下标
ps->_capacity = 0; //栈的容量
}
入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//考虑要不要增容
//当top为0时判断条件为
//if(ps->top==ps->_capacity)
if (ps->_top+1 == ps->_capacity)//当栈满时进入
{
//判断当前栈的容量是否为0，为0的话开辟4个空间，不为0时扩容一倍
int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp = realloc(ps->_a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newcapacity;
}
//扩容完成，或者不用扩容，开始插入
ps->_top++;
ps->_a[ps->_top] = data;
//当top为0时插入操作
//ps->_a[ps->_top] = data;
//ps->_top++;
}
出栈
void StackPop(Stack* ps)
{
assert(ps);
//判断是否为空
assert(!StackEmpty(ps));//暴力判断
//if (top==-1)//温柔判断
//{
// printf("栈已经空了！\n");
// exit(-1); //甩出异常
//}
ps->_top--;
}
取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
//判断是否为空,为空甩出异常。
assert(!StackEmpty(ps));
//if (!StackEmpty(ps)) {
// printf("栈为空！\n");
// exit(-1);
//}
return ps->_a[ps->_top]; //返回栈顶元素
}
判断栈中有几个有效数据
//取出栈里有效元素个数。
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top+1;
}
判断栈是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == -1; //ps->_top为-1返回true,否则返回false.
?
}
销毁栈
销毁栈是必不可少的的一步，如果没有销毁的话会造成内存泄露
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_top = -1;
ps->_capacity = 0;
}
链栈
最后介绍一下链栈，这里就不实现了有兴趣的话可以自己实现一下。
链栈和链表一样的，也是通指针将各个数据块链接起来的
设计链栈是最好设计为双向链表，否则当你设计为用尾作栈顶是出栈效率低。
用头做栈顶时，头插头删，可以设计为单链表。
