正文

❤️《画解数据结构》全网最全栈总结，九个动画组图轮播，不懂都难❤️（建议收藏）(代码片段)

英雄哪里出来  英雄哪里出来  2022-12-22  264

关键词：

本文已收录于专栏 🌳《画解数据结构》🌳

零、前言

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

「栈」

🙉饭不食，水不饮，题必须刷🙉

C语言免费动漫教程，和我一起打卡！ 🌞《光天化日学C语言》🌞
LeetCode 太难？先看简单题！ 🧡《C语言入门100例》🧡
数据结构难？不存在的！ 🌳《画解数据结构》🌳
LeetCode 太简单？算法学起来！ 🌌《夜深人静写算法》🌌
栈可以用 顺序表 实现，也可以用链表实现，浓缩为以下两张图：

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

一、概念

1、栈的定义

栈是仅限在表尾进行插入和删除的 线性表。
栈又被称为后进先出（Last In First Out）的线性表，简称 LIFO 。

2、栈顶

栈是一个线性表，我们把允许插入和删除的一端称为栈顶。

3、栈底

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

二、接口

1、可写接口

1）数据入栈

栈的插入操作，叫做入栈，也可称为进栈、压栈。如下图所示，代表了三次入栈操作：

2）数据出栈

栈的删除操作，叫做出栈，也可称为弹栈。如下图所示，代表了两次出栈操作：

3）清空栈

一直出栈，直到栈为空，如下图所示：

2、只读接口

1）获取栈顶数据

对于一个栈来说只能获取栈顶数据，一般不支持获取其它数据。

2）获取栈元素个数

栈元素个数一般用一个额外变量存储，入栈时加一，出栈时减一。这样获取栈元素的时候就不需要遍历整个栈。通过 $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)$ 用DataType这个宏定义来统一代表栈中数据的类型，这里将它定义为整型，根据需要可以定义成其它类型，例如浮点型、字符型、结构体等等；
$(2)$ maxn代表我们定义的栈的最大元素个数；
$(3)$ Stack就是我们接下来会用到的 栈结构体；
$(4)$ DataType data[maxn]作为栈元素的存储方式，数据类型为DataType，可以自行定制；
$(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)$ stk是一个指向栈对象的指针，由于这个接口会修改栈对象的成员变量，所以这里必须传指针，否则，就会导致函数执行完毕，传参对象没有任何改变；
$(2)$ 将传参的元素放入栈中；
$(3)$ 将栈顶指针自增 1；
注意，这个接口在调用前，需要保证 栈顶指针 小于 栈元素最大个数，即stk->top < maxn，
如果 C语言写的熟练，我们可以把 $(2)$ 和 $(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)$ 数组中栈元素从 0 开始计数，所以实际获取元素时，下标为栈顶元素下标减一；
$(2)$ 因为只有在入栈的时候，栈顶指针才会加一，所以它正好代表了栈元素个数；
$(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)$ 栈结点元素的 数据域，这里定义为整型；
$(2)$ struct StackNode;是对链表结点的声明；
$(3)$ 定义链表结点，其中DataType data代表 数据域；struct StackNode *next代表 指针域；
$(4)$ top作为 栈顶指针，当栈为空的时候，top == NULL；否则，永远指向栈顶；
$(5)$ 由于 求链表长度 的算法时间复杂度是 $O (n)$ 的，所以我们需要记录一个size来代表现在栈中有多少元素。每次入栈时size自增，出栈时size自减。这样在询问栈的大小的时候，就可以通过 $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 = dt;           // (3)
    stk->top = insertNode;           // (4)
    ++ stk->size;                    // (5)

$(1)$ 利用malloc生成一个链表结点insertNode；
$(2)$ 将 当前栈顶 作为insertNode的 后继结点；
$(3)$ 将 insertNode的 数据域 设置为传参 dt；
$(4)$ 将insertNode作为 新的栈顶；
$(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)$ 将 栈顶指针 保存到temp中；
$(2)$ 将 栈顶指针 的 后继结点 作为新的栈顶；
$(3)$ 释放之前 栈顶指针 对应的内存；
$(4)$ 栈元素减一；

4、清空栈

1、动画演示

清空栈 可以理解为，不断的出栈，直到栈元素个数为零。

2、源码详解

对于链表而言，清空栈 的操作需要删除每个链表结点，代码实现如下：

void StackClear(struct Stack* stk) 
    while(!StackIsEmpty(stk))        // (1)
        StackPopStack(stk);           // (2)
    
    stk->top = NULL;                  // (3)

$(1)$ - $(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)$ stk->top作为 栈顶指针，它的 数据域 data就是 栈顶元素的值，返回即可；
$(2)$ size记录的是栈元素个数；
$(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、顺序表实现

在利用顺序表实现栈时，入栈和出栈的常数时间复杂度低，且 清空栈 操作相比 链表实现 能做到 $查看详情$

肝帝一周总结：全网最全最细☀️mysql索引数据结构详解与索引优化☀️《❤️记得收藏❤️》(代码片段)

【肝帝一周总结：全网最全最细】☀️Mysql索引数据结构详解与索引优化☀️《❤️记得收藏❤️》目录🏳️‍🌈开讲啦！！！！🏳️‍🌈🏳️‍🌈1、索引🚣2、索引数据结构... 查看详情

❤️《画解数据结构》目录❤️（进度更新11/31）

本文已收录于专栏🌳《画解数据结构》🌳更新进度(11/31)【🔥最近更新】❤️九个动画“画“解栈❤️初章基础概念《画解数据结构》（0-1）-算法时间复杂度【待更新】《画解数据结构》（0-2）-数据... 查看详情

❤️《画解数据结构》全网最清晰哈希表入门，三张动图搞懂哈希❤️(建议收藏)(代码片段)

...解链表画解栈画解队列画解二叉树画解图零、前言「数据结构」和「算法」是密不可分的，两者往往是「相辅相成」的存在，所以，在学习「数据结构」的过程中，不免会遇到各种「算法」。数据结构常... 查看详情

肝魂一晚上总结：2021年全网最全最面的让你java从零教你变大佬思维图☀️《❤️记得收藏❤️》

【肝魂一晚上总结：2021年全网最全最面的】让你Java从零教你变大佬思维图☀️《❤️记得收藏❤️》目录🏳️‍🌈开讲啦！！！！🏳️‍🌈苏州程序大白🏳️‍🌈😀前言😃... 查看详情

肝魂一晚上总结：全网最全最细手把手教你pyqt5安装与使用☀️《❤️记得收藏❤️》(代码片段)

【肝魂一晚上总结：全网最全最细】手把手教你PyQt5安装与使用☀️《❤️记得收藏❤️》🏳️‍🌈目录🏳️‍🌈开讲啦！！！！🏳️‍🌈⌛前言⏳安装⌚配置⏰使用🌡️入门&#x... 查看详情

❤️《画解数据结构》之顺序表八大算法总结❤️(建议收藏)(代码片段)

您可能感兴趣的文章推荐画解链表画解栈画解队列画解哈希表画解二叉树画解图零、前言这篇文章，作者将用「七张动图」来阐述一种最基础的顺序结构「顺序表」相信看我文章的大多数都是「大学生」，能上... 查看详情

❤️❤️harmonyos（鸿蒙）全网最全资源汇总，吐血整理，赶紧收藏！❤️❤️

目录一、HarmonyOS简介1.1系统定位1.2系统特性2、精品资源总结2.1官网地址2.2论坛地址2.3视频地址2.4API手册2.5开发工具地址2.5超强官方资料一、HarmonyOS简介1.1系统定位HarmonyOS是一款面向万物互联时代的、全新的分布式操作系统。在... 查看详情

❤️《画解数据结构》七个动画“画“解链表(本文出自那个被吊打的面试官，建议收藏)❤️(代码片段)

本文已收录于专栏🌳《画解数据结构》🌳零、前言「数据结构」和「算法」是密不可分的，两者往往是「相辅相成」的存在，所以，在学习「数据结构」的过程中，不免会遇到各种「算法」。到... 查看详情

❤️《画解数据结构》七个动画“画“解链表(本文出自那个被吊打的面试官，建议收藏)❤️(代码片段)

全网最全计算机二级c语言知识总结，还不快来白嫖

第1章、数据结构与算法目录第1章、数据结构与算法1.1算法考点1：算法的基本概念考点2：算法复杂度1.2数据结构的基本概念考点3：数据结构的定义考点4：线性结构与非线性结构1.3栈及线性链表考点5︰栈及其基本... 查看详情

❤️《画解数据结构》目录❤️（进度更新9/31）

画解数据结构更新进度(9/31)【🔥最近更新】❤️「哈希表」+「队列」将会擦出怎样的火花？❤️初章基础概念《画解数据结构》（0-1）-算法时间复杂度【待更新】《画解数据结构》（0-2）-数据结构【... 查看详情

csdn图文专栏：画解数据结构

...会被人唾弃，所以，这次直接进入正题。「画解数据结构」点击我跳转末尾获取粉丝专属《算法和数据结构》源码。第一章线性表❤️《画解数据结构》（1-1）画解顺序表❤️❤️《画解数据结构》（1-2）... 查看详情

❤️《画解数据结构》七张动图，画解单调队列❤️(建议收藏)

...深人静写算法》💜您可能感兴趣的专家文章推荐画解数据结构画解顺序表，画解链表画解栈，画解队列，画解双端队列画解哈希表，画解排序直接跳到末尾获取粉丝专属福利。零、前言「数据结构」和「... 查看详情

❤️六万字《算法和数据结构》之《画解数据结构》总纲，算法零基础教程❤️(建议收藏)(代码片段)

❤️《画解数据结构》两万字，十张动图，画解双端队列❤️(建议收藏)(代码片段)

...解排序直接跳到末尾获取粉丝专属福利。零、前言「数据结构」和「算法」是密不可分的，两者往往是「相辅相成」的存在，所以，在学习「数据结构」的过程中，不免会遇到各种「算法」。到底是先学... 查看详情