数据结构线性表——栈

前言：哈喽小伙伴们，今天我们将一起进入数据结构线性表的第四篇章——栈的讲解，栈还是比较简单的哦，跟紧博主的思路，不要掉队哦。

---

目录

一.什么是栈

二.如何实现栈

三.栈的实现

栈的初始化

四.栈的操作

1.数据入栈

2.数据出栈

3.返回栈顶数据

4.判断空栈

5.销毁栈

6.测试栈

五.完整代码展示

1.Stack.h

2.Stack.c

3.test.c

六.总结

---

一.什么是栈

栈，其实是一种特殊的线性表，他只允许在线性表固定的一端进行插入和删除元素的操作。

进行插入和删除的一端称为栈顶，另一端则称为栈底。

栈中的元素遵循后进先出的原则。

其中有两个对栈中元素进行操作的专业名词：

压栈：栈的插入操作，也可以叫入栈或进栈，入数据在栈顶。出栈：栈的删除操作叫做出栈，出数据也在栈顶。

---

二.如何实现栈

经过我们前边的学习，我们已经掌握了数据结构实现的两种方式，数组和链表。

那么对于栈，我们是用数组，还是用链表呢？？？不妨来分析一下：

关于栈的操作，主要是要方便栈顶的操作。

如果是数组栈：

数组可以直接通过下标来实现访问，方便快捷。

如果是单链表栈：

如果追求高效，就需要让单链表的头作为栈顶，因为单链表的尾部操作比较复杂。

如果是双链表栈，那么无论头尾都可。但是双链表的设计更加麻烦，空间占用也更大。

综合全局因素考虑，用数组实现栈是最合适的。 

---

三.栈的实现 栈的初始化 //初始化 void StackInit(ST* pst) { assert(pst); pst->data = NULL; pst->capacity = 0; pst->top = -1; }

栈的初始化和顺序表一样，但是不同于顺序表的是，栈需要一个top，表示栈顶的当前位置，方便对栈顶数据的操作。

值得注意的是，栈是以数组为基础的，而数组的下标是从0开始的，所以我们如果想让top指向当前栈顶的位置，就要初始化为-1，这样每输入一个数据，top++，就可以完全等同于数组下标啦。

---

四.栈的操作 1.数据入栈

数据入栈之前，我们还是要提前判断一下栈当前空间是否已满，满了则扩容：

//数据入栈 void StackPush(ST* pst, STDataType x) { assert(pst); if (pst->top + 1 == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("StackBush->realloc"); exit(-1); } pst->data = tmp; pst->capacity = newcapacity; } pst->data[pst->top + 1] = x; pst->top++; }

这些操作我们都已经很熟悉了，唯一值得注意的就是对top当前值的判断及后续操作。

---

2.数据出栈 //数据出栈 void StackPop(ST* pst) { assert(pst); assert(pst->top >= 0); pst->top--; }

出栈就很简单了，要注意的就是要断言一下是否为空栈。

---

3.返回栈顶数据 //返回栈顶数据 STDataType StackTop(ST* pst) { assert(pst); assert(pst->top >= 0); return pst->data[pst->top]; }

同样需要断言一下是否为空栈。

---

4.判断空栈 //判断空栈 bool StackEmpty(ST* pst) { assert(pst); if (pst->top >= 0) { return true; } else { return false; } }

这里我们造一个函数来判断栈是否为空，并返回bool型数据，用于我们后续遍历栈的操作。 

---

5.销毁栈 //销毁栈 void StackDestroy(ST* pst) { assert(pst); free(pst->data); pst->data = NULL; pst->capacity = 0; pst->top = -1; }

销毁也是不变的操作，将所有数据复原。

---

6.测试栈

是的，栈总共就上边的5种基础操作方式，因为栈仅允许在栈顶操作数据，所以没有任意位置的入栈，出栈这些操作。

下面我们就来测试：

int main() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); while (StackEmpty(&st)) { STDataType top = StackTop(&st); printf("%d ", top); StackPop(&st); } StackDestroy(&st); return 0; }

能够看出，我们直接将所有的操作整合在一起。

想要遍历栈的数据，就需要返回一个栈顶数据，就让它出栈，再进行循环出栈，直到栈为空，也就是while循环的判断条件。

结果如下：

---

五.完整代码展示 1.Stack.h #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* data; int top; int capacity; }ST; //初始化 void StackInit(ST* pst); //入栈 void StackPush(ST* pst, STDataType x); //出栈 void StackPop(ST* pst); //栈顶数据 STDataType StackTop(ST* pst); //判断空栈 bool StackEmpty(ST* pst); //销毁栈 void StackDestroy(ST* pst);

---

2.Stack.c #include "Stack.h" //初始化 void StackInit(ST* pst) { assert(pst); pst->data = NULL; pst->capacity = 0; pst->top = -1; } //入栈 void StackPush(ST* pst, STDataType x) { assert(pst); if (pst->top + 1 == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("StackBush->realloc"); exit(-1); } pst->data = tmp; pst->capacity = newcapacity; } pst->data[pst->top + 1] = x; pst->top++; } //出栈 void StackPop(ST* pst) { assert(pst); assert(pst->top >= 0); pst->top--; } //栈顶数据 STDataType StackTop(ST* pst) { assert(pst); assert(pst->top >= 0); return pst->data[pst->top]; } //判断空栈 bool StackEmpty(ST* pst) { assert(pst); if (pst->top >= 0) { return true; } else { return false; } } //销毁栈 void StackDestroy(ST* pst) { assert(pst); free(pst->data); pst->data = NULL; pst->capacity = 0; pst->top = -1; }

---

3.test.c #include "Stack.h" int main() { ST st; StackInit(&st); StackPush(&st, 1); StacKPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); while (StackEmpty(&st)) { STDataType top = StackTop(&st); printf("%d ", top); StackPop(&st); } StackDestroy(&st); return 0; }

---

六.总结

栈就是在顺序表的基础上进行一些整改，如果顺序表小伙伴们已经掌握，那么栈就是小趴菜！！！

最后喜欢博主文章的小伙伴不要忘记一键三连哦！！！

我们下期再见啦！！！