栈

---

---

一、栈是什么，为什么使用栈

在内存的存储中了解到压栈和出栈，这种类似的数据结构中也有

栈是限定仅在表尾进行插入或者删除操作的线性表。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则

图片即可解释，凡是具有LIFO特征的问题都可以运用栈的数据结构和思维来求解。

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

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

---

二、栈的接口

为什么使用数组来作为栈呢

因为读取数据时，会先从缓存区读取，而数组是连续的，而且realloc会开辟2倍（约定的扩容倍数）使得每次都有加载到缓存区，而链表时一个一个malloc的缓存区利用不佳

---

1. 初始化栈

//初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;//栈容量0ps->top = 0;//栈顶还是0
}

---

2. 进栈

真的和以前写的顺序表一模一样，直接照搬！

顺序表代码传送门：顺序表源码gitee地址

//进栈
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){//满了需要扩容int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;ST* tmp = (ST*)realloc(ps->a, newcapacity * sizeof(ST));if (tmp == NULL){exit(-1);}ps = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;ps->capacity++;
}

测试结果：1-4很好的入栈了，且是按顺序的

---

3. 销毁栈

轻车熟路！

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

销毁地址，无法访问（变灰色）

---

4. 出栈

//出栈
void StackPop(ST* ps)
{assert(ps);ps->top--;
}

非常简短，将top值减1就行

---

5. 找到栈顶的元素

计算栈中元素个数

//栈中元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}

判断栈是否已经空了

//判断栈是否为空
bool StackEmpty(ST* ps)
{return ps->top == 0;
}

最后找到栈顶

//找到栈顶
STDataType StackTop(ST* ps)
{assert(ps);//assert(ps->top);assert(!StackEmpty(ps));return ps->a[ps->top - 1];}

此图也可以说明，栈的出栈和进栈方式

---