初阶数据结构之栈的实现
前言：实现栈之前，先来了解一下什么是栈。
1. 栈的概念
栈是一种特殊的线性表，只允许在固定一端插入和删除操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出，后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈（压栈，入栈），入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
2. 栈的底层结构如何选择
现在我们已经了解了栈的结构特性了。那么我们该如何实现栈呢？先来看一个问题，顺序表和链表我们已经学习过了，那么栈的底层结构应该选择哪一个呢？
如果底层结构采用数组实现，在插入元素时只需要在指定的位置插入元素即可，删除元素时，- -top就可以了。唯一的缺点就是会存在空间浪费。
如果采用链表来实现栈，每一次插入数据元素都要开辟空间并且需要遍历链表，使新节点成为链表的尾节点；删除数据元素时也需要遍历链表，将尾节点的空间还给操作系统，还要保证尾节点的前驱节点的next保存NULL，避免成为野指针。优点是按需申请和释放空间，不存在空间浪费。缺点是时间复杂度为O(N)，空间复杂度也为O(N)。
综合下来，采用数组的结构来实现栈更合适。解决了这个问题，接下来就该实现栈了。
3. 栈的实现
3.1 栈的定义
typedefint SDataType;typedefstructStack{ SDataType* a;int capacity;//栈的容量大小int top;//栈实际存储数据的个数}Stack;3.2 栈的接口
//初始化栈voidStackInit(Stack* ps);//栈顶入数据voidStackPush(Stack* ps, SDataType x);//栈顶出数据 SDataType StackTop(Stack* ps);//删除栈顶数据voidStackPop(Stack* ps);//栈是否为空 bool StackEmpty(Stack* ps);//栈的大小intStackSize(Stack* ps);//销毁栈voidStackDestroy(Stack* ps);3.2.1 初始化栈
//初始化栈voidStackInit(Stack* ps){assert(ps); ps->a =NULL; ps->capacity = ps->top =0;}3.2.2 栈顶入数据
//栈顶入数据voidStackPush(Stack* ps, SDataType x){assert(ps);//增容if(ps->capacity == ps->top){int newcapacity = ps->capacity ==0?4: ps->capacity *2; SDataType* tmp =(SDataType*)realloc(ps->a,sizeof(SDataType)* newcapacity);if(NULL== tmp){printf("StackPush():realloc fail\n");exit(-1);} ps->a = tmp; ps->capacity = newcapacity;} ps->a[ps->top]= x; ps->top++;}首先判断栈空间是否足够，不够就需要扩容。空间足够直接在top的 位置插入数据，更新栈中数据元素的个数。刚开始栈的容量为0，因 此需要特殊处理，如果栈的容量为0，就将栈的容量设置为4，否则， 就开2倍的空间。 3.2.3 栈是否为空
//栈是否为空 bool StackEmpty(Stack* ps){assert(ps);//选择一种即可if(ps->top ==0){return true;}else{return false;}//return ps->top == 0;}top是记录栈中数据元素的个数的，top为0，栈为空，否则，栈不为空。
3.2.4 栈顶出数据
//栈顶出数据 SDataType StackTop(Stack* ps){assert(ps);//ps->top>0，说明栈顶有数据可以出去//assert(ps->top > 0);assert(!StackEmpty(ps));return ps->a[ps->top -1];}首先应该保证栈不能为空，其次数组中最后一个元素就是栈顶的元素，数组支持随机访问，直接返回数组中最后一个元素即可。
3.2.5 删除栈顶元素
//删除栈顶数据voidStackPop(Stack* ps){assert(ps);//说明有数据可以删除，同时避免越界问题//assert(ps->top > 0);assert(!StackEmpty(ps)); ps->top--;}栈不为空才能删除数据，直接--top就可以了。 3.2.6 栈的大小
//栈的大小intStackSize(Stack* ps){assert(ps);return ps->top;}top是记录栈的数据个数的，直接返回top就可以了。
3.2.7 销毁栈
//销毁栈voidStackDestroy(Stack* ps){assert(ps);free(ps->a); ps->a =NULL; ps->capacity = ps->top =0;}数组空间是动态申请的，因此要还给操作系统。其次把capacity和top 置为0。 4. 栈的完整代码实现
Stack.h
#pragmaonce#include<stdio.h>#include<stdbool.h>#include<stdlib.h>#include<assert.h>typedefint SDataType;typedefstructStack{ SDataType* a;int capacity;//栈的容量大小int top;//栈实际存储数据的个数}Stack;//初始化栈voidStackInit(Stack* ps);//栈顶入数据voidStackPush(Stack* ps, SDataType x);//栈顶出数据 SDataType StackTop(Stack* ps);//删除栈顶数据voidStackPop(Stack* ps);//栈是否为空 bool StackEmpty(Stack* ps);//栈的大小intStackSize(Stack* ps);//销毁栈voidStackDestroy(Stack* ps);Stack.c
#define_CRT_SECURE_NO_WARNINGS#include"Stack.h"//初始化栈voidStackInit(Stack* ps){assert(ps); ps->a =NULL; ps->capacity = ps->top =0;}//栈顶入数据voidStackPush(Stack* ps, SDataType x){assert(ps);//增容if(ps->capacity == ps->top){int newcapacity = ps->capacity ==0?4: ps->capacity *2; SDataType* tmp =(SDataType*)realloc(ps->a,sizeof(SDataType)* newcapacity);if(NULL== tmp){printf("StackPush():realloc fail\n");exit(-1);} ps->a = tmp; ps->capacity = newcapacity;} ps->a[ps->top]= x; ps->top++;}//栈顶出数据 SDataType StackTop(Stack* ps){assert(ps);//ps->top>0，说明栈顶有数据可以出去//assert(ps->top > 0);assert(!StackEmpty(ps));return ps->a[ps->top -1];}//删除栈顶数据voidStackPop(Stack* ps){assert(ps);//说明有数据可以删除，同时避免越界问题//assert(ps->top > 0);assert(!StackEmpty(ps)); ps->top--;}//栈是否为空 bool StackEmpty(Stack* ps){assert(ps);/*if (ps->top == 0) { return true; } else { return false; }*/return ps->top ==0;}//栈的大小intStackSize(Stack* ps){assert(ps);return ps->top;}//销毁栈voidStackDestroy(Stack* ps){assert(ps);free(ps->a); ps->a =NULL; ps->capacity = ps->top =0;}test.c
#define_CRT_SECURE_NO_WARNINGS#include"Stack.h"voidTestStack1(){ Stack st;StackInit(&st);StackPush(&st,1);StackPush(&st,2);StackPush(&st,3);StackPush(&st,4);StackPush(&st,5); SDataType ret =StackTop(&st);printf("%d ", ret);StackPop(&st);StackPop(&st);int size =StackSize(&st);printf("%d ", size);StackDestroy(&st);}intmain(){TestStack1();return0;}
