对应学习内容普林斯顿算法课mudule4第一节stack。虽然标题是c但这个算法课是java的。简单概述本节内容①java的自建栈是一个系统栈上的对象②使用数组建立的自建栈里面存储的不是一个个数据而是不同对象的存储地址③当对自建栈弹出数据如果同时不把自建栈数组里的内存置null可能造成内存泄漏这是因为堆内存的地址还在系统栈上④在java中对自建栈中数据进行弹出一定要注意同时对该索引对应空间置null释放对应的堆内存Q好我现在看完stack这一节了我有一个问题是为什么要设计回收的null因为我觉得既然你已经把它给弹出来那如果这个内存空间他自己给注销了就直接流畅回收了而如果待会儿你可能还会重复写入一个东西那其实没有必要去把它给写成null哇A因为逻辑弹出N--只改变了栈顶指针的位置但数组槽位里仍然存着那个被弹出对象的引用reference。本质原因Java的垃圾回收器Garbage CollectorGC回收对象的唯一标准是“该对象是否仍然可达reachable”。分两步解释清楚1. 为什么必须置null当你执行N--后栈顶指针往下移了一位。在逻辑上这个元素已经不在栈里了。但在物理内存上s[N]原来的栈顶位置依然存着那个对象的引用地址。也就是说那个被弹出的String对象仍然被数组s这个对象强引用strong reference着。GC判断可达性时会顺着s数组遍历所有槽位。只要槽位里有引用GC就认为这个对象还在被使用永远不会回收它。这就是PPT第14页提到的loitering游荡引用——对象已经没用了但内存还被占着。2. 如果待会重复写入为什么不覆盖掉就算了因为“待会重复写入”不一定会发生或者不会立刻发生。如果你pop掉一个元素后这个栈很长一段时间没有再push到相同容量比如栈从10个元素pop到1个之后保持很小那么原本[9]位置的那个过期引用会一直留在数组里。对于客户端程序这个对象已经不可见了但内存却无法释放造成内存泄漏Memory Leak。即使你立刻push新元素新元素会覆盖s[N]那个槽位旧引用自然消失。但在被覆盖之前的那一小段时间窗口内存是白白被占着的。在算法分析中我们考虑的是一系列操作后的峰值内存peak memory和长期持有的情况而不是假设“马上会被覆盖”。结论置nulls[N] null是主动切断引用链让对象变为不可达unreachableGC可以在它认为合适的时机回收这块堆内存。这不是为了“注销内存空间”而是为了告诉GC这块内存可以安全回收了。你不置nullGC不会知道逻辑上已经不需要它了。对应术语引用reference强引用strong reference可达reachable/ 不可达unreachable垃圾回收器garbage collector游荡引用loitering内存泄漏memory leakQ我觉得你的解释挺简洁的但是我没有听懂我不太明白你说在物理内存上S[N]也就是原来的栈顶位置还存着那个对象的引用地址这个我能明白因为你通过改变N这个索引值你还是能找到那个被弹出的元素本来所在的位置。那么他永远还可达永远不会回收他我觉得这非常正确那如果要讲到loitering这个游荡引用的话照你这么说是我已经把这个对象给释放掉了但内存还被占着呀。所以这里的意思是说可能我在不用这个栈以后把这个对象给释放掉了但是由于本身里面不用的元素没有置空所以他依旧会被系统判断为不能回收吗那我是不是可以认为在JAVA下面光是释放掉这块内存并不足以让垃圾回收站去回收它而是释放掉的内存里面必须为空才可以被回收呢还有就是我还是不明白为什么待会儿可能会重复写入就不能暂时把它留在那里我不明白这个情况为什么会造成内存泄露因为我认为既然你已经创建了这个对象那么相应的你的client那边已经写入了一个这样的capacity大小那这个capacity就一直是留给这个栈的它并不会有什么内存泄露的问题呀。A你提出了一个非常关键的问题。你的困惑来源于混淆了“数组本身占用的内存槽位”和“被弹出的那个对象占用的内存堆内存”。这两者是分开的。分两个层面解释清楚层面一置null回收的到底是哪一块内存回答你第一个困惑你说“释放掉这块内存”——你并没有释放掉数组的那个槽位Slot。数组被创建后new String[capacity]它拥有的那 N 个槽位的空间每个槽位 8 字节用于存引用地址是固定不变的直到整个数组被销毁。置nulls[N] null释放的是被弹出对象占用的那块“堆内存”Heap Memory。举例数字只为说明逻辑你在堆上创建了一个巨大的String对象占用 100MB 内存。你把它push进数组数组s[0]存了它的地址8字节。你执行pop把N减为 0逻辑上弹出了。如果你不置null数组s[0]依然存着那个100MB 对象的地址。GC 扫描数组时看到这个地址认为“这 100MB 还在被使用”绝不回收。如果你置null数组s[0] null。GC 扫描时发现这个槽位是空的那个 100MB 对象没有任何引用指向它立刻标记为可回收。结论GC 回收的唯一标准是“是否还有引用指向它”而不是“逻辑上是否被释放”。数组槽位不置空指向该对象的引用就永远存在该对象的堆内存就永远被霸占。“释放掉的内存里面必须为空才可以被回收”——这句话准确地说应该是“将引用置空null对应的堆内存才会变得可回收”。数组槽位本身不需要为空是槽位里存的地址引用必须被清除GC才能放过那个被指向的对象。层面二为什么固定容量capacity下不置 null 依然算内存泄漏回答你第二个困惑你说“capacity已经固定了内存大小就固定了为什么还会泄漏”——泄漏的不是数组的 capacity数组内存大小而是被弹出的大对象本身占用的额外堆内存。数组的 capacity 决定的是“能存多少个引用地址”比如容量 10数组只占248*10104字节。但被引用的对象比如那个 100MB 的字符串是独立于数组之外、额外分配在堆上的。用 C 语言类比你熟悉的char** arr malloc(10 * sizeof(char*));// 数组的 capacity 固定占 80 字节。arr[0] malloc(100);// 在堆上额外分配了 100 字节。你逻辑上不再需要arr[0]指向的这块内存了相当于 Java 的 pop。如果你只是把索引标记为“已删除”Java 的N--但没有执行free(arr[0])Java 的s[0]null那这额外分配的 100 字节就永远留在堆里无法被重新利用。Java 的“泄漏”就是指这种情况程序逻辑上已经用不着的大对象因为数组槽位还抱着它的地址不放导致 GC 无法回收。如果连续弹出 10 个大对象即使数组 capacity 只有 10 个槽位堆内存里也积压了 10 个大对象10 * 100MB 1GB的垃圾。这就是泄漏——泄漏的是被引用的大对象本身的内存而不是数组的槽位内存。关于“待会重复写入”的补充解答你说“待会可能重复写入不置 null 也能覆盖”——技术上确实能覆盖。但算法分析Analysis of Algorithms考察的是最坏情况和平均情况下的峰值内存占用。如果客户端的操作序列是push(大对象A)→pop()→再也没有执行过push或者执行了很多次其他操作才push那么在这段“真空期”内内存被白白占用。在工业级长时运行程序中服务器、EDA工具这种临时积压足以撑爆内存。置null是最小代价的防御性编程Defensive Programming它不依赖“待会是否会写入”而是在当前时刻立即释放不再需要的资源。Q我认为我并没有混淆我很清楚的知道对象是建立在栈上的而数组存储是建立在堆上的但或许在我刚刚的表述中我确实使用了不正确的表述但实际上我明白你说的这些东西。我只是不明白为什么这个站既然已经通过client给的capacity容量占领了堆上这个大小的存储空间我还非要把这个空间写成空。还是说你这里指的是当我把这个栈已经弹出到所有东西而在他的零号位不去把它写为空的话这个栈会一直占着那个堆的内存呢你说的而不是在我一般把它弹出一个数据以后我站里面还有别的数据也非要把它写成空的。是我理解的这样吗是指这个栈你已经弹出了全部的数据以后再也不使用了才要把它写成空吗但我还是不太理解呀因为在C加加里面我学到的是当你这个对象存储在系统的栈上然后你把系统栈上的这个对象给注销了他的堆内存也同时回收掉了呀。那我知道或许你觉得我在混淆什么了我确实在上面的表述中没有指明栈是我们自己建立的那一个还是系统的那一个A你说到关键分歧点了。我明白你刚才真正的困惑了你以为“置空”是为了回收数组本身占用的那capacity大小的堆内存。我现在明确告诉你不是。我们分开拆成两个完全独立的“堆内存”1. 数组本身占用的堆内存固定大小不可回收当你执行new String[capacity]时Java在堆上分配了一块连续内存大小是24字节对象头 8*capacity字节引用槽位。这块内存永远不会因为你执行了pop或者置了null而变小或回收。只要这个Stack对象你写的那个类实例还存在这块数组内存就一直在那里大小不变。你说的“capacity一直留给这个栈”完全正确针对这块内存不存在泄漏。2. 被弹出的“元素对象”本身占用的堆内存可变大小需要回收当你执行push(new String(very large))时new String在堆上额外申请了一块独立的内存比如1MB。数组槽位里存的只是指向这块1MB内存的地址8字节。关键区别数组内存capacity个槽位是早就分好了的。元素对象内存new String得到的那1MB是额外分的独立于数组。pop操作做了什么事它把N减了1逻辑删除。如果不置null数组的某个槽位比如s[N]里依然还写着那个1MB内存的地址。结果逻辑上你已经不用这个1MB了但GC扫描数组时发现数组里还存着这个地址GC会认为“这个1MB还在被使用”因此永远不回收它。3. 回答你最核心的问题“是必须等到栈清空才置空吗”不是。是每弹出一个元素就必须立刻置空那个具体的槽位。你要理解栈里同时有N个元素。你pop()掉的是最顶上那个索引N-1。这个被弹出来的元素对象比如那个1MB内存已经不属于栈了。栈里剩下的其他N-1个元素索引0到N-2是合法的槽位当然不能置空。只有那个被移出栈顶的特定索引N-1它的槽位必须置null。否则数组里剩下的其他槽位和GC没关系只有那个特定的旧槽位会让GC误以为“那个被弹出的1MB对象还在栈里”。4. 用你熟悉的C来类比绝对精准在C里假如你写了一个栈底层是std::vectorstd::string*存指针cppvectorstring* stack; stack.push_back(new string(big)); // 堆上分配1MB string* item stack.back(); // 取出指针 stack.pop_back(); // 只把指针从vector里移除 // 这里如果不写 delete item; 那1MB内存就永远泄漏了。对应到JavaC的stack.pop_back()只移除指针对应Java的N--只把索引减1。C的delete item;删除指针指向的对象对应Java的s[N] null;清除数组里的地址切断引用。你回忆一下在C里如果你只pop_back()而不delete那个string那块堆内存泄漏。Java没有手动delete它靠GC。但GC没有读心术你不把数组槽位里的地址清掉置nullGC就不知道那个对象已经死了于是它不敢回收——这和C里忘记delete是一个意思。5. 直接回答你上一段话的最后一句“在C加加里面我学到的是当你这个对象存储在系统的栈上然后你把系统栈上的这个对象给注销了他的堆内存也同时回收掉了呀。”你把两个“栈”搞混了这恰好是混淆点系统栈调用栈存局部变量比如你的Stack对象本身。当函数结束系统销毁局部对象这时候C的析构函数会释放数组内存——这对应的是回收“第1点”里那个数组本身。我们这门课讲的“数据结构栈”它是一个容器里面装的元素String是在堆上独立分配的。你把这个容器销毁了析构数组跟着没里面的元素指针也跟着没——但在pop时容器没有销毁它只是要释放其中一个元素。你现在正在学习的操作是在程序运行过程中只弹出一个元素但容器数据结构栈还在继续用。这时候必须手动切断引用置null否则那个被弹出的元素对象堆内存在C里就是delete没写在Java里就是null没置——都是泄漏。现在能区分开“数组本身的内存”和“数组里某槽位指向的那个额外对象的堆内存”了吗Q我好像明白了你让我来澄清一下吧就是说我们所建立的这个客户栈它里面的数组位置存放的并不是单一孤立的另一个数组的位置也就是说并不是我们建立的这个客户栈对象它里面只有一个地址位置地址位置存着堆里面一块连续的内存远远不是的而是我这个指针数组里面存放的是不同数组的指针我每次放入的不是一个单一的基础类型的数据而可能是一个数组。所以因此我必须得每次不用那个数组了就把它清空而我每次要push一个新的元素的时候我都在拿出一个新的数组放到我们客户栈的这个指针数组里面去。是这样吗所以他依旧是那个逻辑就是当我们在堆上划分一个内存的时候在栈上只要释放掉它那么这个堆内存就会回收我们刚刚讲的把那片内存空间里的内容置空指的正是要去置零我们客户站上所写的那个新PUSH进来的元素的堆内存空间。A对。你只需要把表述里的“数组”换成“对象”因为push进去的不一定是数组可以是任意String、自定义类等剩下的逻辑一字不差底层物理事实你理解对了客户栈数据结构内部那个Item[] s或String[] s是一个引用数组Array of References。这个引用数组的每一个槽位比如s[0]、s[1]都是一个 8 字节的“地址盒子”各自独立指向堆上各自独立的对象。push(new Item())在堆上新建一个对象把它的地址放进当前栈顶槽位s[N]。pop()把栈顶指针N减 1逻辑上移出该对象。为什么必须置null如果不置null那个被弹出的对象仍然被s[N]减 1 之前那个槽位这个“地址盒子”指着。GC 只看地址盒子它认为“既然有盒子指着你你就是活着的”。你执行s[N] null的物理动作是把那个特定槽位地址盒子里的内容擦写成 0空指针。这样一来那个堆上的对象就再也没有任何地址盒子指着它了GC 立刻判定它为垃圾并回收。和 C 的映射给你锚定Java 的Item[] s相当于 C 的Item** s二级指针数组存指针。Java 的s[N] null相当于 C 的s[N] nullptr;清掉地址。至于delete释放堆内存在 Java 里是 GC 自动做的前提是你先把地址清掉置 null。你之前怀疑的“只为了回收数组本身”是错的你现在理解成了“回收每个被弹出对象本身”这是完全正确的答案。这一节最底层的坑你踩过去了。Q原来如此所以栈是一个如此通用的东西而他之所以如此通用正是他存储的数据并不是那些数据本身而是那些数据的地址地址与地址都是八位的本质上没有差别所以他才能做到如此通用是吗这跟我学到的确实很不一样我在微机原理里面他们教我的东西都是把一个个int或者是char类型的数据放到栈里面以至于我以为栈里面存的东西就必须是一样的。这个结构很漂亮。A对。1. 为什么数据结构栈Stack能做到“通用”底层数组Item[] s在Java底层被擦除后就是Object[] s里每个槽位固定占8 字节引用即地址。不管你是String、Integer、自定义的CircuitNet它们在堆上的对象实体大小千差万别有的64字节有的2MB。但指向它们的地址统一都是 8 字节。所以这个数据结构栈的数组本质上存的是一批 8 字节的地址盒子。它根本不关心盒子外面指向的那个对象是什么类型。这就是它通用的物理基础。2. 为什么你之前微机原理/汇编里认为“栈必须存一样的东西”因为那是硬件调用栈Call Stack不是数据结构栈。硬件栈系统栈CPU 的RSP/ESP寄存器直接操作内存地址。它存的是函数的返回地址、局部基本类型int/char和寄存器备份。数据是直接按值Value拷贝到栈顶的。int占4字节char占1字节大小不一CPU 必须通过类型大小来移动指针所以你直觉认为它存的东西必须一样或大小可知。数据结构栈容器这门课讲的是堆上的容器对象。它存的不是数据值而是指向堆内存的指针引用。所有指针固定8字节所以数组槽位均匀整齐天然支持泛型。你从硬件栈转到 Java 容器栈时把“栈内存里存值”的惯性带过来了。现在你彻底把这两个概念分离了。3. 你现在对栈“漂亮”在哪里的感知漂亮在间接层Indirection数组槽位里只是一个 8 字节的门牌号引用。真正的货物数据对象堆在另一个大仓库堆内存里。因此门牌号槽位可以做得整齐划一、无限复用而仓库货物可以随意更改大小。Q那么在C加加里面应该也是一样的咯A既是也不是。取决于你在C里怎么写。C和Java在“容器如何存储数据”这一点上有一个本质分水岭你需要区分清楚1. 如果你在C里写std::stackMyClass默认写法底层完全不一样。C的std::stack默认底层容器是std::dequeT或vectorT这些容器采用的是值语义Value Semantics。当你push(MyClass obj)时容器在内部连续内存里直接拷贝/移动了整个MyClass对象的字节占sizeof(MyClass)字节。如果MyClass有100字节槽位就是100字节如果有1000字节槽位就是1000字节。这个槽位大小在编译期就由MyClass的类型决定了不是统一的8字节。因此C默认的std::stack并不通用在“存地址”这个层面它通用在“模板Template”层面——编译时为每种类型生成一份独立的机器码。2. 如果你在C里写std::stackMyClass*或std::stackstd::unique_ptrMyClass底层完全一样。此时容器里存的是指针64位系统占8字节或unique_ptr也是8字节仅指针大小。真正的MyClass对象实体在堆上new或make_unique容器只负责搬运那8字节的地址。这时候的物理存储模型和Java的StackMyClass完全等价槽位固定8字节对象实体在堆上独立存放。3. 那C为什么默认不这么干因为C让你选要性能局部性好存值。对象紧挨着放CPU缓存命中率高不需要额外去堆上跳转寻址。要多态/共享/节省栈空间存指针或智能指针。牺牲一点缓存性能换来实现Java那样的“通用引用”和多态基类指针指向子类对象。Java没有“存值”这个选项除了基本类型int通过包装类间接实现所有对象天然在堆上容器天然存引用。所以你在Java里观察到的“漂亮结构”在C里只是一种可选策略而非唯一策略。Q哦所以我发现所谓的不同编程语言他们好像确实是一个抽象层级高低的问题像C语言跟C加加这种自由度更高的他抽象级别好像就更低一点相对来说他也需要你更多的去管理内存而我遇到的JAVA还有python这种他就不会允许你去做一些比较特殊的操作。反而从语法层面上讲我感觉学到目前课程里面的JAVA语句没有很难读好像跟C语言差的也不多。A观察准确而且你自己总结出了编程语言设计中的一个核心分水岭。1. 关于语法层面C 和 Java 长得像是因为历史原因Java 的设计者James Gosling在设计语法时刻意沿用了 C 和 C 的语法风格花括号{}、分号;、for/while循环结构目的是让 C/C 程序员能零成本切换到 Java。所以你看到if、for、while、函数调用写法几乎一样这是表层语法Syntax的继承不代表底层运行机制相同。2. 关于抽象层级C/C vs Java/Python 的本质区别在“对硬件的控制权”C / C系统级语言提供对内存地址的直接操作指针算术、取地址、手动malloc/free。你写的代码几乎直接对应 CPU 指令和内存地址。缺点是容易写出内存泄漏或野指针。抽象层级低贴近硬件。Java托管语言把“内存地址”封装成“引用Reference”禁用指针算术你不能对引用做运算由 JVMJava 虚拟机统一管理内存布局和垃圾回收GC。你写的代码对应的是 JVM 的字节码指令再由 JVM 翻译成 CPU 指令。抽象层级高贴近程序员逻辑屏蔽硬件细节。Python脚本语言一切皆为对象甚至连int都是堆上的对象动态类型解释执行。抽象层级最高彻底屏蔽了类型和内存概念。你感觉 Java 语句不难读是因为它借用了 C 语言的“外貌”但它的“内在逻辑”对象全部在堆上只能通过引用访问更像一个简化版的、安全的 C去掉了很多让你容易犯错的功能多重继承、指针运算、手动内存释放。3. 对应到你这节课的具体体会你昨天被卡住的“引用地址”问题在 C 语言里是显式暴露的int* p a你必须自己写*p或p[0]来操作。在 Java 里编译器帮你把底层地址的取址和解引用*步骤全部隐藏了所以你写arr[0] text时感觉像在直接操作数据但底层的机器码实际在搬运那个 8 字节的地址。所以说你现在学 Java 版的算法课最大的好处是不需要操心内存分配释放可以专注于算法本身的逻辑指针怎么跳、数组索引怎么变。等你在 Java 里把算法的“状态变化”理解透了回头用 C 实现时只需要在原来放“引用”的地方换成“指针或智能指针”就行。你现在的硬件底子微机原理是理解 Java 引用的最大优势而不是阻碍。