栈（C语言版）

一.栈的概念及结构

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

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

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

二.栈的对比

栈的实现数组和链表都可以，下面我们来对比下各种实现：

1.数组实现：

相当于之前顺序表的尾插尾插用尾去做了栈顶，非常合适。唯一缺陷就是:空间不够，需要增容

2.单链表实现：

如果要用单链表实现，那么就 用头去做栈顶更好，这样可以避免找不到前面的，入栈和出栈效率都是 0(1)，缺点：每一次都要开辟空间，而且空间消耗远比数组大。

3.双链表实现：

此时可以用尾做栈顶，双向链表效率也为0（1),但是双链表缺点更大：不但每次都要开辟空间，而且空间消耗比单链表还要严重。

因此，我们用数组其实更好，增容也不是每次都增的，总体较为合适！

下面我们开始用数组实现栈：（放心，绝对比链表简单）

三.栈的实现

第一步：实现结构体

//定义结构体
typedef int STDataType;
typedef struct Stack
{STDataType* arr;//数据int top;//栈顶int capacity;//容量
}SS;

第二步：实现基本接口

// 初始化栈定义
void StackInit(SS* ps)
{//检查assert(ps);//开辟空间ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);//注意：开辟的空间为STDataType类型ps->top = 0;//此时栈顶为0ps->capacity = 4;//容量为开辟的4个STDataType空间大小
}

// 入栈定义
void StackPush(SS* ps, STDataType x)
{//检查栈空间是否存足if (ps->top == ps->capacity){//空间不够，扩容STDataType* tmp = (STDataType*)realloc(ps->arr, ps->capacity * sizeof(STDataType) * 2);if (tmp == NULL){exit(-1);}else{ps->arr = tmp;ps->capacity *= 2;}}//开始入栈操作ps->arr[ps->top] = x;ps->top++;
}

// 出栈定义
void StackPop(SS* ps)
{//判断assert(ps);//栈不能为空assert(ps->top > 0);ps->top--;
}

// 获取栈顶元素定义
STDataType StackTop(SS* ps)
{//判断assert(ps);//栈不能为空assert(ps->top > 0);return ps->arr[ps->top-1];
}

// 获取栈中有效元素个数定义
int StackSize(SS* ps)
{assert(ps);return ps->top;
}

// 检测栈是否为空，如果为空返回false，如果不为空返回true
bool StackEmpty(SS* ps)
{assert(ps);return ps->top == 0;
}

// 销毁栈定义
void StackDestory(SS* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}

这边建议大家还是边实现边检查，不然出问题了不好找。

由于我这写一个检查一个太耗时间，所以我就写完了统一检查：

#include "Stack.h"
void test1()
{SS s1;StackInit(&s1);StackPush(&s1, 1);StackPush(&s1, 2);StackPush(&s1, 3);StackPush(&s1, 4);StackPush(&s1, 5);StackPush(&s1, 6);StackPush(&s1, 7);StackPush(&s1, 8);StackPush(&s1, 9);StackPush(&s1, 10);while (!StackEmpty(&s1)){printf("%d ",StackTop(&s1));StackPop(&s1);}printf("\n");StackDestory(&s1);
}
int main()
{test1();return 0;
}

结果如下：