正常操作，正常分析，大家好我是D1N910。

下面是我学郝斌老师的数据结构入门的学习笔记。

那么开卷。

链表的我已经学完了，后面可能会补。

线性结构的两种常见应用 栈/队列，本文讲的是栈。

本文学习自：

栈的定义/分类/算法/应用

0、前言

首先要说一下计算机的内存。什么是计算机的内存呢？

内存(Memory)是计算机的重要部件，也称内存储器和主存储器，它用于暂时存放CPU中的运算数据，以及与硬盘等外部存储器交换的数据。

内存分为静态内存（栈）/动态内存（堆）

静态内存是在栈里分配的，操作系统自动分配的。

动态内存是在堆里分配的，堆是要程序员主动建立起来的。

举个实际的例子，比如说下面的 1.c 文件有变量 m、p、i、p，同样也有 200、100 这两个变量，前者存在栈里，后者存在堆里。栈是计算机进行分配分配的。堆是程序员进行分配的。

为什么说是程序员分配的堆呢？因为后面200等可能会做修改，所以是程序员进行分配的。

栈、堆表示分配数据的一种方式，静态/局部变量一样以出栈的方式分配内存；堆是以堆排序的方式分配内存。

1、栈定义

栈就是一种可以实现“先进后出”的存储结构（存储方式）。只要我们搞出一个东西能够先进后出存储数据，那么就是栈 —— 这像是鸭式辨型的概念，鸭式辨型的通俗说法是:“如果它走起路来像鸭子,叫起来也是鸭子,那么它就是鸭子。

栈类似于箱子装书，先进后出。先放进去的最后取出来。

x 不是这种横着装书啊！

2、栈分类（静态栈、动态栈）

2.1、静态栈

以数组为内核，想要删掉其中一个，要把想要删最后的全部拿出来 ——

因为是以数组为内核，所以栈具有数组的特性，长度是固定的、每个数据之间的地址是连续的，会先占一定的内存，所以是静态栈。

2.2、动态栈

栈的特性和链表相似，每个栈元素之间的地址不相连。和链表比砍了一些功能，只能从头部加和删，不能够在尾部进行加和删。也叫链式栈。

4->3->2->1->0

2.3、队列定义

先进先出。类似排队买东西，只有两个口，一个入口，一个出口，只能够从一端添加元素，只能够从另一端减少元素。

3、栈的算法

一般就是 出栈/压栈 两个算法

类似生产者-消费者模式，先把生产好的东西直接压进去，消费的时候直接从里面拿东西进行消费。

4、栈程序演示（33_栈程序演示 55:24）

一般的动态栈程序如上演示，栈的每个元素都是有意义的，PTop永远指向栈的顶部，PButtom永远指向栈的底部。所以PTop会疯狂动和修改。但是这里有一个问题就是栈的每一个元素都是有意义的，特别是PButtom指向的也是有意义的元素，不太方便处理。

那么就参考链表中头结点的设计。PButtom指向没有意义的头节点。

【入栈】如果要入栈的话，就先生产一个节点，然后往栈中接入，把PTop往上移一位；

【判空】判断栈是否为空，只要PTop和PButton相等就行

【判满】动态栈是链表，不存在满不满的问题~

下面就演示这个程序。

4.1、栈程序演示-头文件的引入

#include <stdio.h>

#include <stdlib.h>

4.2、栈程序演示-定义栈和栈对应链表结构体

typedef struct Node // 箱子里的书

{

   int data;

   struct Node * pNext;

} NODE, * PNODE;

typedef struct Stack // 栈  - 箱子

{

   PNODE pTop; // 指向栈的顶部

   PNODE pBottom; // 指向栈的底部

} STACK, * PSTACK;

4.3、栈程序演示-定义栈的基本算法（初始化/压栈/遍历/判断栈是否为空/出栈/清空栈内容）

int main(void)

{

   STACK S; // STACK 等价于 struct Stack

上面可以在main中声明栈变量 S，现在 S 有PTop 和 PButtom，PTop 和 PButtom还没指向任何东西。我们要初始化栈，初始化方法名可自定义，一般叫init，对应的还有其他基本算法，push: 压栈，往栈中添加元素；traverse：遍历输出栈的元素

init 初始化栈

给栈的pTop分配一个节点内存地址；

如果分配的地址为NULL，说明分配失败：

-打印报错信息，并退出程序。

如果分配的地址不为NULL，说明分配成功：

-栈的pBottom也指向栈的pTop指向的节点；

-栈的pTop指向的节点存储的下一节点的地址赋为NULL，以此保证是空节点。

结束。

void init (PSTACK pS)

{

pS->pTop = (PNODE)malloc(sizeof(NODE));

if (NULL == pS->pTop) {

printf("分配内存失败！\n");

exit(-1);

}

else

{

pS->pBottom = pS->pTop;

pS->pTop->pNext = NULL;

}

}

现在初始化以后，S的PTop和PBottom都指向同一个空结点。

push 压栈

创建一个新的结点；

新的节点data存储值；

新的节点的pNext指向栈的pTop；

栈的pTop指向新的节点。

结束。

traverse 遍历

创建一个p节点指针指向栈的最顶部元素；

循环执行：当p节点指针和栈的最底部元素指向地址不同时，打印p节点指针的值，改变p节点指针的指向为下一个节点地址；

结束循环，打印个回车；

结束。

执行一波看看结果。

调用函数。

结果

empty 判断栈是否为空

接受栈的指针作为参数。

判断栈的pTop是不是和栈的pBottom指向相同；

-如果是，返回true；

-如果不是，返回false。

结束

pop 出栈

接受栈的指针、存储出栈的值的整数指针作为参数，

判断栈是否为空（用刚刚的empty方法）

-如果是，出栈失败，返回false；

-如果不是，则继续执行

--定义新节点指针存储当前栈的pTop，新节点指针即为出栈节点

--修改当前栈的pTop指向为pTop的下一个节点（1）

--将出栈节点的指赋值给存储出栈的值的整数指针；（2）

【注】（1）、（2）顺序可变；

--释放出栈节点内存；

--手动将栈定义为空；

--返回true

main调用执行一波

成功时结果如下：

将压栈代码注释，重新跑程序，查看出栈失败场景。

出栈失败时结果如下

clear 清空栈

创建两个节点指针p、q，分别指向pTop、pTop->pNext，这样释放p内存以后仍旧可以找到下一个节点去释放。

这是老师给的方法。

先判断是否为空，为空不执行；

定义p存放pS.pTop；

定义q存放NULL；

当p不等于pS->pBottom，那么不断地free；

循环结束后将pTop指向pBottom。

结束。

栈的内容确实比链表的简单。

5、栈的应用（34_栈的应用 06:58）

函数调用

假设有f、g、y、k这几个函数是这么调用的

f() {g()}

g() {y()}

y() {k()}

k() {}

那么函数执行顺序是这样的

f() -> g() -> y() ->k()

当执行到了k函数以后，又会把值往上面回传

k()-> y() ->  g() -> f()

那么计算机就是用压栈的原理去实现上面的函数调用的过程，仔细一看我们可以发现，当f()内等待g()的值的返回时，f()函数接下来要执行的地址就可以压栈中，以此类推，k函数是最顶部被压入的函数，然后再逐个出栈找到下一个要执行的语句的地址进行执行（将值回传），直到到了栈底的去执行。

中断 - 老师说不讲，但是也很重要（？

表达式求值

3x2+5/6-4

利用两个栈可以编计算器↑

内存分配

缓冲处理

迷宫

以上源代码

https://github.com/D1N910/learn-c/blob/main/haobingDataStructure/30/stack08.c

学习进度（34/63）

继续加油