九个动画组图轮播总结全栈数据结构数组链表九个动画组图轮播总结全栈数

一、概念

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、栈的定义
栈是仅限在表尾进行插入和删除的线性表。
栈又被称为后进先出（LastInFirstOut）的线性表，简称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)用DataType这个宏定义来统一代表栈中数据的类型，这里将它定义为整型，根据需要可以定义成其它类型，例如浮点型、字符型、结构体等等；
(2)maxn代表我们定义的栈的最大元素个数；
(3)Stack就是我们接下来会用到的栈结构体；
(4)DataTypedata[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 如果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)数组中栈元素从0开始计数，所以实际获取元素时，下标为栈顶元素下标减一；
(2)因为只有在入栈的时候，栈顶指针才会加一，所以它正好代表了栈元素个数；
(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)栈结点元素的数据域，这里定义为整型；
(2)structStackNode; 是对链表结点的声明；
(3)定义链表结点，其中DataTypedata代表数据域；structStackNode*next代表指针域；
(4)top作为栈顶指针，当栈为空的时候，top==NULL；否则，永远指向栈顶；
(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)利用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 = 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)，唯一的不足之处是：需要预先申请好空间，而且当空间不够时，需要进行扩容，扩容方式本文未提及，可以参考脚本之家其他相关文章。

2、链表实现
在利用链表实现栈时，入栈和出栈的常数时间复杂度略高，主要是每插入一个栈元素都需要申请空间，每删除一个栈元素都需要释放空间，且清空栈操作是O(n)O(n)O(n)的，直接将栈顶指针置空会导致内存泄漏。好处就是：不需要预先分配空间，且在内存允许范围内，可以一直入栈，没有顺序表的限制。
【九个动画组图轮播总结全栈数据结构数组链表】关于「栈」的内容到这里就结束了。如果还有不懂的问题，可以想方设法找到作者的联系方式，线上沟通交流,希望大家以后多多支持脚本之家！