《画解数据结构》|??《画解数据结构》九个动图，画解栈?? 数据结构|栈|链表|数组|算法

本文已收录于专栏 《画解数据结构》
零、前言

??「数据结构」 和 「算法」 是密不可分的，两者往往是「相辅相成」的存在，所以，在学习 「数据结构」 的过程中，不免会遇到各种「算法」。
??到底是先学数据结构，还是先学算法，我认为不必纠结这个问题，一定是一起学的。
??数据结构常用的操作一般为：「增」「删」「改」「查」。基本上所有的数据结构都是围绕这几个操作进行展开的。
??那么这篇文章，作者将用 「九张动图」 来阐述一种 「后进先出」 的数据结构

「栈」

文章图片

饭不食，水不饮，题必须刷
C语言免费动漫教程，和我一起打卡！ 《光天化日学C语言》
LeetCode 太难？先看简单题！ 《C语言入门100例》
数据结构难？不存在的！ 《画解数据结构》
闭关刷 LeetCode，剑指大厂Offer！ 《LeetCode 刷题指引》
LeetCode 太简单？算法学起来！ 《夜深人静写算法》
?? 栈可以用 顺序表 实现，也可以用链表实现，浓缩为以下两张图：

??看不懂没有关系，我会把它拆开来一个一个讲，首先来看一下今天要学习的内容目录。

文章目录

零、前言
一、概念
- 1、栈的定义
- 2、栈顶
- 3、栈底
二、接口
- 1、可写接口
- - 1）数据入栈
  - 2）数据出栈
  - 3）清空栈
- 2、只读接口
- - 1）获取栈顶数据
  - 2）获取栈元素个数
  - 3）栈的判空
三、栈的顺序表实现
- 1、数据结构定义
- 2、入栈
- - 1、动画演示
  - 2、源码详解
- 3、出栈
- - 1、动画演示
  - 2、源码详解
- 4、清空栈
- - 1、动画演示
  - 2、源码详解
- 5、只读接口
- 6、栈的顺序表实现源码
四、栈的链表实现
- 1、数据结构定义
- 2、入栈
- - 1、动画演示
  - 2、源码详解
- 3、出栈
- - 1、动画演示
  - 2、源码详解
- 4、清空栈
- - 1、动画演示
  - 2、源码详解
- 5、只读接口
- 6、栈的链表实现源码
五、两种实现的优缺点
- 1、顺序表实现
- 2、链表实现
六、栈的入门
- 1、逆序链表
- 2、括号匹配
- 3、回文链表
- 4、表达式求值
- 5、双栈判等
七、栈的进阶
- 1、最小栈
- 2、化栈为队
- 3、直方图最大矩形

一、概念 1、栈的定义 ??栈是仅限在表尾进行插入和删除的线性表。
??栈又被称为后进先出（Last In First Out）的线性表，简称 LIFO 。
2、栈顶 ??栈是一个线性表，我们把允许插入和删除的一端称为栈顶。

文章图片

3、栈底 ??和栈顶相对，另一端称为栈底，实际上，栈底的元素我们不需要关心。

文章图片

二、接口 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代表空栈；

2、入栈 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++表达式的值是自增前的值，并且自身进行了一次自增。

3、出栈 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 100010struct 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) 的时间复杂度。

2、入栈 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 = https://www.it610.com/article/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) 栈元素加一；

3、出栈 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 = https://www.it610.com/article/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、逆序链表《LeetCode 206. 反转链表》解题报告
2、括号匹配《LeetCode 20. 有效的括号》解题报告
《LeetCode 32. 最长有效括号》解题报告
3、回文链表《LeetCode 234. 回文链表》解题报告
4、表达式求值《LeetCode 682. 棒球比赛》解题报告
5、双栈判等《LeetCode 844. 比较含退格的字符串》解题报告
七、栈的进阶

??栈的进阶主要是单调栈相关的内容，可以参考我的另一篇文章：夜深人静写算法（十一）- 单调栈。看完以后，别忘了进行相关题目的练习。

1、最小栈《LeetCode 155. 最小栈》解题报告
2、化栈为队《LeetCode 232. 用栈实现队列》解题报告
3、直方图最大矩形《LeetCode 84. 柱状图中最大的矩形》解题报告

关于 「栈」 的内容到这里就结束了。
如果还有不懂的问题，可以通过 「博客主页」找到作者的「联系方式」 ，线上沟通交流。

有关《画解数据结构》 的源码均开源，链接如下：《画解数据结构》

【《画解数据结构》|??《画解数据结构》九个动图，画解栈??】

饭不食，水不饮，题必须刷
C语言免费动漫教程，和我一起打卡！ 《光天化日学C语言》
LeetCode 太难？先看简单题！ 《C语言入门100例》
数据结构难？不存在的！ 《画解数据结构》
闭关刷 LeetCode，剑指大厂Offer！ 《LeetCode 刷题指引》
LeetCode 太简单？算法学起来！ 《夜深人静写算法》