前言：实现栈之前，先来了解一下什么是栈。
1. 栈的概念
栈是一种特殊的线性表，只允许在固定一端插入和删除操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出，后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈（压栈，入栈），入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
2. 栈的底层结构如何选择
现在我们已经了解了栈的结构特性了。那么我们该如何实现栈呢？先来看一个问题，顺序表和链表我们已经学习过了，那么栈的底层结构应该选择哪一个呢？
如果底层结构采用数组实现，在插入元素时只需要在指定的位置插入元素即可，删除元素时，- -top就可以了。唯一的缺点就是会存在空间浪费。
如果采用链表来实现栈，每一次插入数据元素都要开辟空间并且需要遍历链表，使新节点成为链表的尾节点；删除数据元素时也需要遍历链表，将尾节点的空间还给操作系统，还要保证尾节点的前驱节点的next保存NULL，避免成为野指针。优点是按需申请和释放空间，不存在空间浪费。缺点是时间复杂度为O(N)，空间复杂度也为O(N)。
综合下来，采用数组的结构来实现栈更合适。解决了这个问题，接下来就该实现栈了。
3. 栈的实现
3.1 栈的定义
typedef int SDataType;typedef struct Stack
{SDataType* a;int capacity;//栈的容量大小int top;//栈实际存储数据的个数
}Stack;
3.2 栈的接口
//初始化栈
void StackInit(Stack* ps);//栈顶入数据
void StackPush(Stack* ps, SDataType x);//栈顶出数据
SDataType StackTop(Stack* ps);//删除栈顶数据
void StackPop(Stack* ps);//栈是否为空
bool StackEmpty(Stack* ps);//栈的大小
int StackSize(Stack* ps);//销毁栈
void StackDestroy(Stack* ps);
3.2.1 初始化栈
//初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}
3.2.2 栈顶入数据
//栈顶入数据
void StackPush(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 删除栈顶元素
//删除栈顶数据
void StackPop(Stack* ps)
{assert(ps);//说明有数据可以删除，同时避免越界问题//assert(ps->top > 0);assert(!StackEmpty(ps));ps->top--;
}
栈不为空才能删除数据，直接--top就可以了。
3.2.6 栈的大小
//栈的大小
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}
top是记录栈的数据个数的，直接返回top就可以了。
3.2.7 销毁栈
//销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}
数组空间是动态申请的，因此要还给操作系统。其次把capacity和top
置为0。
4. 栈的完整代码实现
Stack.h
#pragma once#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>typedef int SDataType;typedef struct Stack
{SDataType* a;int capacity;//栈的容量大小int top;//栈实际存储数据的个数
}Stack;//初始化栈
void StackInit(Stack* ps);//栈顶入数据
void StackPush(Stack* ps, SDataType x);//栈顶出数据
SDataType StackTop(Stack* ps);//删除栈顶数据
void StackPop(Stack* ps);//栈是否为空
bool StackEmpty(Stack* ps);//栈的大小
int StackSize(Stack* ps);//销毁栈
void StackDestroy(Stack* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"//初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}//栈顶入数据
void StackPush(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];
}//删除栈顶数据
void StackPop(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;
}//栈的大小
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}//销毁栈
void StackDestroy(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"
void TestStack1()
{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);
}
int main()
{TestStack1();return 0;
}