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

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

目录一、概念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、栈的定义

栈是仅限在表尾进行http://插入和删除的线性表。

栈又被称为后进先出（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 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)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为当前需要入栈的元素CxGyKLs，即图中的橙色结点。入栈操作完成后，栈顶元素变为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、顺序表实现

在利用顺序表实现栈时，入栈和出栈的常数时间复杂度低，且清空栈操作相比链表实现能做到O(1)O(1)O(1)，唯一的不足之处是：需要预先申请好空间，而且当空间不够时，需要进行扩容，扩容方式本文未提及，可以参考我们其他相关文章。

2、链表实现

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

如果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 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)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为当前需要入栈的元素CxGyKLs，即图中的橙色结点。入栈操作完成后，栈顶元素变为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、顺序表实现

在利用顺序表实现栈时，入栈和出栈的常数时间复杂度低，且清空栈操作相比链表实现能做到O(1)O(1)O(1)，唯一的不足之处是：需要预先申请好空间，而且当空间不够时，需要进行扩容，扩容方式本文未提及，可以参考我们其他相关文章。

2、链表实现

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。