服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - 九个动画组图轮播总结全栈数据结构数组链表

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

2021-11-23 13:05英雄哪里出来 Java教程

数据结构和算法是密不可分的,两者往往是相辅相成的存在,所以在学习数据结构过程中,不免会遇到各种算法,数据结构常用操作一般为:增删改查。基本上所有的数据结构都是围绕这几个操作进行展开,本文用九张动图来阐述

「栈」

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

栈可以用顺序表实现,也可以用链表实现,浓缩为以下两张图:

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

看不懂没有关系,我会把它拆开来一个一个讲。

一、概念

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语言实现如下所示:

?
1
2
3
4
5
6
7
#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、源码详解

入栈操作,算上函数参数列表,总共也才几句话,代码实现如下:

?
1
2
3
4
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)(2)(2)和(3)(3)(3)合成一句话,如下:

?
1
2
3
void StackPushStack(struct Stack *stk, DataType dt) {
    stk->data[ stk->top++ ] = dt;                   
}

stk->top++表达式的值是自增前的值,并且自身进行了一次自增。

3、出栈

1、动画演示

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

如图所示,蓝色元素为原本在栈中的元素,红色元素为当前需要出栈的元素,执行完毕以后,栈顶的指针减一。具体来看下代码实现。

2、源码详解

出栈操作,只需要简单改变将栈顶减一即可,代码实现如下:

?
1
2
3
void StackPopStack(struct Stack* stk) {
    --stk->top;
}

4、清空栈

1、动画演示

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

如图所示,对于数组来说,清空栈的操作只需要将栈顶指针置为栈底,也就是数组下标0即可,下次继续入栈的时候会将之前的内存重复利用。

2、源码详解

清空栈的操作只需要将栈顶指针直接指向栈底即可,对于顺序表,也就是C语言中的数组来说,栈底就是下标0的位置了,代码实现如下:

?
1
2
3
void StackClear(struct Stack* stk) {
    stk->top = 0;
}

5、只读接口

只读接口包含:获取栈顶元素、获取栈大小、栈的判空,实现如下:

?
1
2
3
4
5
6
7
8
9
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、栈的顺序表实现源码

栈的顺序表实现的源码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/************************************* 栈的顺序表实现 *************************************/
#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语言实现如下所示:

?
1
2
3
4
5
6
7
8
9
10
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、源码详解

入栈操作,其实就是类似头插法,往链表头部插入一个新的结点,代码实现如下:

?
1
2
3
4
5
6
7
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、源码详解

出栈操作,由于链表头结点就是栈顶,其实就是删除这个链表的头结点的过程。代码实现如下:

?
1
2
3
4
5
6
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、源码详解

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

?
1
2
3
4
5
6
void StackClear(struct Stack* stk) {
    while(!StackIsEmpty(stk)) {       // (1)
        StackPopStack(stk);           // (2)
    }
    stk->top = NULL;                  // (3)
}

(1)-(2)的每次操作其实就是一个出栈的过程,如果栈不为空;则进行出栈操作,直到栈为空;

(2)然后将栈顶指针置为空,代表这是一个空栈了;

5、只读接口

只读接口包含:获取栈顶元素、获取栈大小、栈的判空,实现如下:

?
1
2
3
4
5
6
7
8
9
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、栈的链表实现源码

栈的链表实现源码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/************************************* 栈的链表实现 *************************************/
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),唯一的不足之处是:需要预先申请好空间,而且当空间不够时,需要进行扩容,扩容方式本文未提及,可以参考服务器之家其他相关文章。

2、链表实现

在利用链表实现栈时,入栈和出栈的常数时间复杂度略高,主要是每插入一个栈元素都需要申请空间,每删除一个栈元素都需要释放空间,且清空栈操作是O(n)O(n)O(n)的,直接将栈顶指针置空会导致内存泄漏。好处就是:不需要预先分配空间,且在内存允许范围内,可以一直入栈,没有顺序表的限制。

关于「栈」的内容到这里就结束了。如果还有不懂的问题,可以想方设法找到作者的联系方式,线上沟通交流,希望大家以后多多支持服务器之家!

原文链接:https://blog.csdn.net/WhereIsHeroFrom/article/details/119580434

延伸 · 阅读

精彩推荐