数据结构 --- 栈

前言

栈是一个特殊的线性表，遵循一个先进后出的特性，即操作数据（入栈，出栈）只能从栈顶操作，栈底是一个封口的结构。既然是线性表从逻辑结构上是线性的，物理结构上取决于底层实现的结构，若是顺序栈（底层为数组），则是线性的，若是链栈，则是非线性的，本次实现的栈为顺序栈，对比链栈空间更小：

对比上述两种栈的实现结构，进行入栈出栈操作时，两种结构的时间复杂度都为O(1)，但是在进行入栈操作时，假设type是int类型，那么数组结构就只增加4个字节，而链表结构会增加8个或者12个字节，对比而得顺序栈更好，当然也不是一定不能使用链表实现。
同时本次实现栈使用C语言实现。

一、栈结构

经由前文使用数组定义栈结构，有三个属性，一个指向栈的指针arr，一个标记栈顶位置和栈实际大小的top（其实也就是顺序表的size）是有效数据的下一个位置，以及一个空间容量capacity。

//定义栈结构
typedef int STDataType;   // 方便更改栈存储数据的类型
typedef struct Stack
{STDataType* arr; //指向栈的指针int top;         //栈顶位置和栈实际大小int capacity;    //空间容量
}ST;

二、相关方法

1.初始化

初始化是将栈初始化成一个空栈，即栈底层数组置为NULL，将top和capacity等于0。

//初始化
void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}

2.入栈

入栈操作四步，首先判断传递过来的参数栈是否不为空，不为空才能进行入栈操作，第二步，判断是否需要扩容，当top == capacity时进行扩容操作（两种情况，一为空栈，二为栈满），使用realloc进行扩容操作，第三步，更新数据，当扩容完成后，需要将扩容后的数组和空间大小更新回arr和capacity，最后再在top栈顶位置插入数据，top再加加；
当空间充足时直接进行最后的插入操作。

//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);   //ps不能传空//首先判断栈空间是否需要增容 --- 没有空间或者空间已满if (ps->top == ps->capacity){// 增容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* temp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (temp == NULL){perror("realloc");exit(1);}ps->arr = temp;ps->capacity = newcapacity;}//空间充足 --- top位置入栈,入栈完成top+1ps->arr[ps->top++] = x;
}

3.出栈

出栈首先需要断言传递过来的参数栈不为空，并且栈内需存在元素方可进行出栈操作，其次直接减减top栈顶位置即可。

//出栈 --- 要改变top位置 
void StackPop(ST* ps)
{//assert(ps && ps->top);assert(ps && !StackEmpty(ps));   //ps不能传空,top==0不能再出栈--ps->top;
}

4.判空

当栈为空时，返回true，不为空时返回false。

//判定栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);   //ps不能传空return ps->top == 0;
}

5.获取栈顶元素

获取栈顶元素即获取top位置的元素，并且只是读取元素而不是出栈，故top大小不会改变。

//获取栈顶元素 --- top位置不用改变
STDataType StackTop(ST* ps)
{assert(ps);   //ps不能传空return ps->arr[ps->top-1];
}

6.获取栈大小

//获取栈中有效数据个数
int StackGetSize(ST* ps)
{assert(ps);   //ps不能传空return ps->top;
}

7.销毁

销毁栈空间即将数组置为空，top和capacity等于0，也就是恢复至空栈状态，当然数组若已为NULL了，则无需置空。

//销毁
void StackDestroy(ST* ps)
{assert(ps);if (ps->arr != NULL){free(ps->arr);ps->arr = NULL;}ps->top = ps->capacity = 0;
}