❤️《画解数据结构》九个动图，画解栈❤️
source link: https://blog.csdn.net/WhereIsHeroFrom/article/details/119580434
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
❤️《画解数据结构》九个动图，画解栈❤️
本文已收录于专栏
「 数据结构 」 和 「 算法 」 是密不可分的，两者往往是「 相辅相成 」的存在，所以，在学习 「 数据结构 」 的过程中，不免会遇到各种「 算法 」。
到底是先学 数据结构 ，还是先学 算法，我认为不必纠结这个问题，一定是一起学的。
数据结构 常用的操作一般为：「 增 」「 删 」「 改 」「 查 」。基本上所有的数据结构都是围绕这几个操作进行展开的。
那么这篇文章，作者将用 「 九张动图 」 来阐述一种 「 后进先出 」 的数据结构「 栈 」
🙉饭不食，水不饮，题必须刷🙉
C语言免费动漫教程，和我一起打卡！ 🌞《光天化日学C语言》🌞
LeetCode 太难？先看简单题！ 🧡《C语言入门100例》🧡
数据结构难？不存在的！ 🌳《画解数据结构》🌳
闭关刷 LeetCode，剑指大厂Offer！ 🌌《LeetCode 刷题指引》🌌
LeetCode 太简单？算法学起来！ 💜《夜深人静写算法》💜
栈可以用 顺序表 实现，也可以用 链表 实现，浓缩为以下两张图：
看不懂没有关系，我会把它拆开来一个一个讲，首先来看一下今天要学习的内容目录。
1、栈的定义
栈 是仅限在 表尾 进行 插入 和 删除 的 线性表。
栈 又被称为 后进先出 （Last In First Out） 的线性表，简称 LIFO 。
栈 是一个线性表，我们把允许 插入 和 删除 的一端称为 栈顶。
和 栈顶 相对，另一端称为 栈底，实际上，栈底的元素我们不需要关心。
1、可写接口
1）数据入栈
栈的插入操作，叫做 入栈，也可称为 进栈、压栈。如下图所示，代表了三次入栈操作：
2）数据出栈
栈的删除操作，叫做 出栈，也可称为 弹栈。如下图所示，代表了两次出栈操作：
3）清空栈
一直 出栈，直到栈为空，如下图所示：
2、只读接口
1）获取栈顶数据
对于一个栈来说只能获取 栈顶 数据，一般不支持获取 其它数据。
2）获取栈元素个数
栈元素个数一般用一个额外变量存储，入栈 时加一，出栈 时减一。这样获取栈元素的时候就不需要遍历整个栈。通过 O ( 1 ) O(1) O(1) 的时间复杂度获取栈元素个数。
3）栈的判空
当栈元素个数为零时，就是一个空栈，空栈不允许 出栈 操作。
三、栈的顺序表实现
1、数据结构定义
对于顺序表，在 C语言 中表现为 数组，在进行 栈的定义 之前，我们需要考虑以下几个点：
1）栈数据的存储方式，以及栈数据的数据类型；
2）栈的大小；
3）栈顶指针；
- 我们可以定义一个 栈 的 结构体，C语言实现如下所示：
#define DataType int // (1)
#define maxn 100005 // (2)
struct Stack { // (3)
DataType data[maxn]; // (4)
int top; // (5)
};
-
(
1
)
(1)
(1) 用
DataType这个宏定义来统一代表栈中数据的类型，这里将它定义为整型，根据需要可以定义成其它类型，例如浮点型、字符型、结构体 等等； -
(
2
)
(2)
(2)
maxn代表我们定义的栈的最大元素个数； -
(
3
)
(3)
(3)
Stack就是我们接下来会用到的 栈结构体； -
(
4
)
(4)
(4)
DataType data[maxn]作为栈元素的存储方式，数据类型为DataType，可以自行定制； -
(
5
)
(5)
(5)
top即栈顶指针，data[top-1]表示栈顶元素，top == 0代表空栈；
1、动画演示
如图所示，蓝色元素 为原本在栈中的元素，红色元素 为当前需要 入栈 的元素，执行完毕以后，栈顶指针加一。具体来看下代码实现。
2、源码详解
- 入栈 操作，算上函数参数列表，总共也才几句话，代码实现如下：
void StackPushStack(struct Stack *stk, DataType dt) { // (1)
stk->data[ stk->top ] = dt; // (2)
stk->top = stk->top + 1; // (3)
}
-
(
1
)
(1)
(1)
stk是一个指向栈对象的指针，由于这个接口会修改栈对象的成员变量，所以这里必须传指针，否则，就会导致函数执行完毕，传参对象没有任何改变； - ( 2 ) (2) (2) 将传参的元素放入栈中；
- ( 3 ) (3) (3) 将栈顶指针自增 1；
- 注意，这个接口在调用前，需要保证 栈顶指针 小于 栈元素最大个数，即
stk->top < maxn， - 如果 C语言 写的熟练，我们可以把 ( 2 ) (2) (2) 和 ( 3 ) (3) (3) 合成一句话，如下：
void StackPushStack(struct Stack *stk, DataType dt) {
stk->data[ stk->top++ ] = dt;
}
stk->top++表达式的值是自增前的值，并且自身进行了一次自增。
1、动画演示
如图所示，蓝色元素 为原本在栈中的元素，红色元素 为当前需要 出栈 的元素，执行完毕以后，栈顶的指针减一。具体来看下代码实现。
2、源码详解
- 出栈 操作，只需要简单改变将 栈顶 减一 即可，代码实现如下：
void StackPopStack(struct Stack* stk) {
--stk->top;
}
4、清空栈
1、动画演示
如图所示，对于数组来说，清空栈的操作只需要将 栈顶指针 置为栈底，也就是数组下标 0 即可，下次继续 入栈 的时候会将之前的内存重复利用。
2、源码详解
- 清空栈的操作只需要将 栈顶 指针直接指向 栈底 即可，对于顺序表，也就是 C语言 中的数组来说，栈底 就是下标 0 的位置了，代码实现如下：
void StackClear(struct Stack* stk) {
stk->top = 0;
}
5、只读接口
- 只读接口包含：获取栈顶元素、获取栈大小、栈的判空，实现如下：
DataType StackGetTop(struct Stack* stk) {
return stk->data[ stk->top - 1 ]; // (1)
}
int StackGetSize(struct Stack* stk) {
return stk->top; // (2)
}
bool StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk); // (3)
}
- ( 1 ) (1) (1) 数组中栈元素从 0 开始计数，所以实际获取元素时，下标为 栈顶元素下标 减一；
- ( 2 ) (2) (2) 因为只有在入栈的时候，栈顶指针才会加一，所以它 正好代表了 栈元素个数；
- ( 3 ) (3) (3) 当 栈元素 个数为 零 时，栈为空。
6、栈的顺序表实现源码
- 栈的顺序表实现的源码如下：
/************************************* 栈的顺序表实现 *************************************/
#define DataType int
#define bool int
#define maxn 100010
struct Stack {
DataType data[maxn];
int top;
};
void StackClear(struct Stack* stk) {
stk->top = 0;
}
void StackPushStack(struct Stack *stk, DataType dt) {
stk->data[ stk->top++ ] = dt;
}
void StackPopStack(struct Stack* stk) {
--stk->top;
}
DataType StackGetTop(struct Stack* stk) {
return stk->data[ stk->top - 1 ];
}
int StackGetSize(struct Stack* stk) {
return stk->top;
}
bool StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk);
}
/************************************* 栈的顺序表实现 *************************************/
四、栈的链表实现
1、数据结构定义
对于链表，在进行 栈的定义 之前，我们需要考虑以下几个点：
1）栈数据的存储方式，以及栈数据的数据类型；
2）栈的大小；
3）栈顶指针；
- 我们可以定义一个 栈 的 结构体，C语言实现如下所示：
typedef int DataType; // (1)
struct StackNode; // (2)
struct StackNode { // (3)
DataType data;
struct StackNode *next;
};
struct Stack {
struct StackNode *top; // (4)
int size; // (5)
};
- ( 1 ) (1) (1) 栈结点元素的 数据域，这里定义为整型；
-
(
2
)
(2)
(2)
struct StackNode;是对链表结点的声明； -
(
3
)
(3)
(3) 定义链表结点，其中
DataType data代表 数据域；struct StackNode *next代表 指针域； -
(
4
)
(4)
(4)
top作为 栈顶指针，当栈为空的时候，top == NULL；否则，永远指向栈顶； -
(
5
)
(5)
(5) 由于 求链表长度 的算法时间复杂度是
O
(
n
)
O(n)
O(n) 的， 所以我们需要记录一个
size来代表现在栈中有多少元素。每次 入栈时size自增，出栈时size自减。这样在询问栈的大小的时候，就可以通过 O ( 1 ) O(1) O(1) 的时间复杂度。
1、动画演示
如图所示，head 为栈顶，tail 为栈底，vtx 为当前需要 入栈 的元素，即图中的 橙色结点。入栈 操作完成后，栈顶 元素变为 vtx，即图中 绿色结点。
2、源码详解
- 入栈 操作，其实就是类似 头插法，往链表头部插入一个新的结点，代码实现如下：
void StackPushStack(struct Stack *stk, DataType dt) {
struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) ); // (1)
insertNode->next = stk->top; // (2)
insertNode->data = dt; // (3)
stk->top = insertNode; // (4)
++ stk->size; // (5)
}
-
(
1
)
(1)
(1) 利用
malloc生成一个链表结点insertNode； -
(
2
)
(2)
(2) 将 当前栈顶 作为
insertNode的 后继结点； -
(
3
)
(3)
(3) 将
insertNode的 数据域 设置为传参dt； -
(
4
)
(4)
(4) 将
insertNode作为 新的栈顶； - ( 5 ) (5) (5) 栈元素 加一；
1、动画演示
如图所示，head 为栈顶，tail 为栈底，temp 为当前需要 出栈 的元素，即图中的 橙色结点。出栈 操作完成后，栈顶 元素变为之前 head 的 后继结点，即图中 绿色结点。
2、源码详解
- 出栈 操作，由于链表头结点就是栈顶，其实就是删除这个链表的头结点的过程。代码实现如下：
void StackPopStack(struct Stack* stk) {
struct StackNode *temp = stk->top; // (1)
stk->top = temp->next; // (2)
free(temp); // (3)
--stk->size; // (4)
}
-
(
1
)
(1)
(1) 将 栈顶指针 保存到
temp中； - ( 2 ) (2) (2) 将 栈顶指针 的 后继结点 作为新的 栈顶；
- ( 3 ) (3) (3) 释放之前 栈顶指针 对应的内存；
- ( 4 ) (4) (4) 栈元素减一；
4、清空栈
1、动画演示
清空栈 可以理解为，不断的出栈，直到栈元素个数为零。
2、源码详解
- 对于链表而言，清空栈 的操作需要删除每个链表结点，代码实现如下：
void StackClear(struct Stack* stk) {
while(!StackIsEmpty(stk)) { // (1)
StackPopStack(stk); // (2)
}
stk->top = NULL; // (3)
}
- ( 1 ) (1) (1) - ( 2 ) (2) (2) 的每次操作其实就是一个 出栈 的过程，如果 栈 不为空；则进行 出栈 操作，直到 栈 为空；
- ( 2 ) (2) (2) 然后将 栈顶指针 置为空，代表这是一个空栈了；
5、只读接口
- 只读接口包含：获取栈顶元素、获取栈大小、栈的判空，实现如下：
DataType StackGetTop(struct Stack* stk) {
return stk->top->data; // (1)
}
int StackGetSize(struct Stack* stk) {
return stk->size; // (2)
}
int StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk);
}
-
(
1
)
(1)
(1)
stk->top作为 栈顶指针，它的 数据域data就是 栈顶元素的值，返回即可； -
(
2
)
(2)
(2)
size记录的是 栈元素个数； - ( 3 ) (3) (3) 当 栈元素 个数为 零 时，栈为空。
6、栈的链表实现源码
- 栈的链表实现源码如下：
/************************************* 栈的链表实现 *************************************/
typedef int DataType;
struct StackNode;
struct StackNode {
DataType data;
struct StackNode *next;
};
struct Stack {
struct StackNode *top;
int size;
};
void StackPushStack(struct Stack *stk, DataType dt) {
struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) );
insertNode->next = stk->top;
insertNode->data = dt;
stk->top = insertNode;
++ stk->size;
}
void StackPopStack(struct Stack* stk) {
struct StackNode *temp = stk->top;
stk->top = temp->next;
--stk->size;
free(temp);
}
DataType StackGetTop(struct Stack* stk) {
return stk->top->data;
}
int StackGetSize(struct Stack* stk) {
return stk->size;
}
int StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk);
}
void StackClear(struct Stack* stk) {
while(!StackIsEmpty(stk)) {
StackPopStack(stk);
}
stk->top = NULL;
stk->size = 0;
}
/************************************* 栈的链表实现 *************************************/
五、两种实现的优缺点
1、顺序表实现
在利用顺序表实现栈时，入栈 和 出栈 的常数时间复杂度低，且 清空栈 操作相比 链表实现 能做到 O ( 1 ) O(1) O(1)，唯一的不足之处是：需要预先申请好空间，而且当空间不够时，需要进行扩容，扩容方式本文未提及，可以参考以下文章：《C/C++ 面试 100 例》（四）vector 扩容策略。
2、链表实现
在利用链表实现栈时，入栈 和 出栈 的常数时间复杂度略高，主要是每插入一个栈元素都需要申请空间，每删除一个栈元素都需要释放空间，且 清空栈 操作是 O ( n ) O(n) O(n) 的，直接将 栈顶指针 置空会导致内存泄漏。好处就是：不需要预先分配空间，且在内存允许范围内，可以一直 入栈，没有顺序表的限制。
六、栈的入门
好啦，接下来，让我们做几个栈的题目练习一下吧。
1、逆序链表
2、括号匹配
《LeetCode 20. 有效的括号》解题报告
《LeetCode 32. 最长有效括号》解题报告
3、回文链表
4、表达式求值
5、双栈判等
七、栈的进阶
栈的进阶主要是单调栈相关的内容，可以参考我的另一篇文章：夜深人静写算法（十一）- 单调栈。看完以后，别忘了进行相关题目的练习。
1、最小栈
2、化栈为队
3、直方图最大矩形
- 关于 「 栈 」 的内容到这里就结束了。
- 如果还有不懂的问题，可以通过 「 博客主页 」找到作者的「 联系方式 」 ，线上沟通交流。
🙉饭不食，水不饮，题必须刷🙉
C语言免费动漫教程，和我一起打卡！ 🌞《光天化日学C语言》🌞
LeetCode 太难？先看简单题！ 🧡《C语言入门100例》🧡
数据结构难？不存在的！ 🌳《画解数据结构》🌳
闭关刷 LeetCode，剑指大厂Offer！ 🌌《LeetCode 刷题指引》🌌
LeetCode 太简单？算法学起来！ 💜《夜深人静写算法》💜
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK