 入栈出栈的完整解析)
Hello 算法仓库中的链表栈用「头插法」实现 O(1) 入栈出栈的完整解析【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇技术指南聚焦 hello-algo 仓库中「基于链表实现栈」这一主题以 ru/codes/pythontutor/chapter_stack_and_queue/linkedlist_stack.md 中的可视化代码为核心结合仓库各语言源码完整讲解 LIFO 语义、头插法入栈与头部删除出栈的底层机制、LinkedListStack类的逐方法实现、驱动代码的运行结果以及 Python / C / Rust 三种实现的源码级差异。读完本文后你将能够独立用链表手写一个功能完整的栈并理解它与数组栈在性能与内存上的取舍。一、主题定位这个文档在仓库中对应什么linkedlist_stack.md 是俄语版代码教程pythontutor目录下的一个可视化代码文件服务于文档章节 ru/docs/chapter_stack_and_queue/stack.md 中「基于链表实现栈」一节。该文件本身结构极简由两部分组成文件头注释标注文件名、创建时间2024-01-05与作者一条 Python Tutor 渲染链接链接的#code参数是一段 URL 编码的完整 Python 源码内容为ListNode与LinkedListStack两个类的定义加上驱动代码Driver Code可直接粘贴到 Python Tutor 中逐步可视化执行。文档头部的标签行[file]{linkedlist_stack}-[class]{linked_list_stack}-[func]{}是 mkdocs 构建系统的取码标记文档页面ru/docs/chapter_stack_and_queue/stack.md 第 379–381 行通过该标记从真实源码文件 ru/codes/python/chapter_stack_and_queue/linkedlist_stack.py 中自动抽取LinkedListStack类注入页面。也就是说本文展开的所有代码都可以在仓库源码中找到逐行对应的实现而非仅存在于可视化链接中。二、栈的基本语义与操作复杂度栈Stack是一种遵循 LIFO后进先出Last In First Out逻辑的线性数据结构只能在一端栈顶插入和删除元素。仓库文档中将其类比为一摞盘子——想拿走底部的盘子必须先依次移走上面所有盘子。LinkedListStack支持的六个方法及其时间复杂度如下与 ru/docs/chapter_stack_and_queue/stack.md 的操作表格一致方法功能时间复杂度push(val)将元素入栈置于栈顶$O(1)$pop()弹出栈顶元素并返回$O(1)$peek()查看栈顶元素但不弹出$O(1)$size()返回栈中元素个数$O(1)$is_empty()判断栈是否为空$O(1)$to_list()序列化为普通列表以便打印$O(n)$所有核心操作的 $O(1)$ 复杂度正是「头插法」设计带来的入栈、出栈都只发生在链表头部无需遍历。三、核心数据结构头节点即栈顶链表栈的关键设计决策只有一条把链表的头节点当作栈顶peek尾节点当作栈底。push(val)等价于链表的头插——新建节点令其next指向当前头节点再把头指针移到新节点上pop()等价于链表的删头——取出头节点的值把头指针前移到下一个节点。由于不维护尾指针push/pop均不需要遍历链表这保证了严格意义上的常数时间操作。四、Python 实现逐段解析以下内容与 linkedlist_stack.md 中解码后的代码完全一致同时对应源码 ru/codes/python/chapter_stack_and_queue/linkedlist_stack.py。4.1 节点定义与导入from modules import ListNode # 仓库中定义于 ru/codes/python/modules/list_node.py仓库提供的 ListNode 只有两个字段class ListNode: Класс узла связного списка def __init__(self, val: int): self.val: int val # 节点值 self.next: ListNode | None None # 指向后继节点的引用ru/codes/python/modules/init.py 将ListNode统一导出因此各章代码都以from modules import ListNode的方式复用同一套节点定义。4.2 类成员与构造L14-L20class LinkedListStack: Стек на основе связного списка def __init__(self): self._peek: ListNode | None None # 头指针指向栈顶节点空栈为 None self._size: int 0 # 栈内元素个数两个私有成员即可覆盖全部状态_peek链表头指针。之所以命名为_peek而非_head是因为它同时兼任「栈顶」角色直接读它的.val就是peek()的返回值_size独立计数器。维护它可以让size()和is_empty()都不必遍历链表保持 $O(1)$。4.3 入栈三步头插L30-L35def push(self, val: int): Поместить в стек node ListNode(val) # ① 创建新节点 node.next self._peek # ② 新节点指向当前栈顶 self._peek node # ③ 头指针移到新节点 self._size 1这三行是链表头插的标准写法。顺序上第 ②、③ 步不可颠倒若先执行self._peek node就会丢失对原栈顶的引用。4.4 出栈与查看栈顶L37-L48def pop(self) - int: Извлечь из стека num self.peek() # 先取栈顶值空栈时 peek 会抛 IndexError self._peek self._peek.next # 头指针前移完成删头 self._size - 1 return num def peek(self) - int: Доступ к верхнему элементу стека if self.is_empty(): raise IndexError(стек пуст) return self._peek.val值得注意的设计点pop()通过先调用peek()实现空栈保护——对空栈执行pop()会抛出IndexError(стек пуст)而不是让self._peek.next在None上触发属性错误Python 由垃圾回收器处理被摘除节点因此pop()中没有显式的释放代码这一点与 C 版本形成对照见第六节。4.5 长度、判空与序列化L22-L28, L50-L58def size(self) - int: return self._size def is_empty(self) - bool: return self._size 0 def to_list(self) - list[int]: Преобразовать в список для вывода arr [] node self._peek while node: arr.append(node.val) node node.next arr.reverse() # 链表顺序为 栈顶 - 栈底翻转后为 栈底 - 栈顶 return arrto_list()沿next指针从头走到尾天然得到「栈顶在前」的顺序所以最后需要arr.reverse()让打印结果[1, 3, 2, 5, 4]以栈底元素 1 排在最左符合人们看「一摞盘子」的直觉。五、驱动代码与运行结果驱动部分位于 linkedlist_stack.py与可视化文档中的代码一致if __name__ __main__: stack LinkedListStack() stack.push(1) stack.push(3) stack.push(2) stack.push(5) stack.push(4) print(Стек stack , stack.to_list()) peek: int stack.peek() print(Верхний элемент peek , peek) pop: int stack.pop() print(Извлеченный элемент pop , pop) print(stack после извлечения , stack.to_list()) size: int stack.size() print(Длина стека size , size) is_empty: bool stack.is_empty() print(Пуст ли стек , is_empty)按 LIFO 语义逐步推演其运行结果步骤操作栈内状态左栈底右栈顶输出1push(1) push(3) push(2) push(5) push(4)[1, 3, 2, 5, 4]Стек stack [1, 3, 2, 5, 4]2peek()[1, 3, 2, 5, 4]Верхний элемент peek 43pop()[1, 3, 2, 5]Извлеченный элемент pop 44size()[1, 3, 2, 5]Длина стека size 45is_empty()[1, 3, 2, 5]Пуст ли стек False最后弹出的 4 恰好是最后压入的元素直观验证了「后进先出」栈顶指针始终指向最后入栈者。六、跨语言实现的源码对照仓库为同一算法提供了 14 种语言实现ru/codes/lang/chapter_stack_and_queue/linkedlist_stack.*其中 Python 与可视化文档逐行对应。以 C 和 Rust 为例可以看到同一个头插法设计在不同内存模型下的落地差异。6.1 C显式内存管理ru/codes/cpp/chapter_stack_and_queue/linkedlist_stack.cpp 中成员为ListNode *stackToppush同样是三步头插void push(int num) { ListNode *node new ListNode(num); node-next stackTop; stackTop node; stkSize; } int pop() { int num top(); ListNode *tmp stackTop; stackTop stackTop-next; delete tmp; // 手动释放被摘除节点 stkSize--; return num; }与 Python 版的差异集中在三处pop()中必须delete被摘除的节点析构函数里遍历链表逐个释放L21-L24top()对空栈抛出的异常类型是std::out_of_range而非 Python 的IndexError。此外C 的toVector()利用已知长度做逆序回填省去了 Python 版to_list()里的reverse()调用。6.2 Rust借用检查下的RcRefCell写法ru/codes/rust/chapter_stack_and_queue/linkedlist_stack.rs 中头指针类型为OptionRcRefCellListNodeTpub fn push(mut self, num: T) { let node ListNode::new(num); node.borrow_mut().next self.stack_peek.take(); // take() 临时取出旧头 self.stack_peek Some(node); self.stk_size 1; } pub fn pop(mut self) - OptionT { self.stack_peek.take().map(|old_head| { self.stack_peek old_head.borrow_mut().next.take(); self.stk_size - 1; old_head.borrow().val }) }从源码结构看这里用take()先移走Option里的旧头节点再赋值新头是为了在借用检查器borrow checker面前构造出合法的独占可变借用pop()返回OptionT而非抛异常是 Rust 处理「空栈」这一不可预期状态惯用手法。6.3 小结三种实现的共同骨架维度PythonCRust头指针类型ListNode \| NoneListNode *OptionRcRefCellListNodeT空栈弹出行为抛IndexError抛out_of_range返回None节点释放GC 自动回收delete 析构遍历Rc引用计数to_list策略正向收集后reverse()逆序回填递归拼接三种实现的状态都只有「头指针 计数器」两个变量进一步说明链表栈的实现骨架极其紧凑语言差异全部落在内存管理层面。七、链表栈的适用场景与性能特征结合仓库文档 ru/docs/chapter_stack_and_queue/stack.md 中「两种实现比较」一节的结论扩容数组栈在容量耗尽时扩容单次push退化为 $O(n)$属于「平时快、偶尔慢」链表栈每次push都新分配一个节点没有整体搬迁各次操作耗时稳定内存链表节点要为next指针额外付出空间而数组可能预留超出实际需要的容量两者各有所失需按场景权衡天然适配如果入栈的元素本身已经是节点对象例如遍历树时压入TreeNode链表栈可以直接压入节点而不需要额外包装这正是文档中提到的「跳过节点初始化步骤」的情形典型应用浏览器前进/后退历史两个栈配合实现 undo/redo、函数调用的栈帧管理递归深入即连续push回溯即连续pop。八、总结本文围绕 ru/codes/pythontutor/chapter_stack_and_queue/linkedlist_stack.md 的可视化代码展开先确认了该文档与 mkdocs 构建标记、真实源码文件之间的对应关系再逐一拆解了 LinkedListStack 的头插式push、带空栈保护的pop/peek、常数时间的size/is_empty与需要翻转的to_list随后通过驱动代码的运行推演验证了 LIFO 语义并用 C、Rust 源码对照说明了同一算法在不同内存模型下的实现差异。掌握这一实现后读者可以将其作为理解数组栈ru/codes/python/chapter_stack_and_queue/array_stack.py、双端队列deque等后续数据结构的基础。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法仓库中的链表栈：用「头插法」实现 O(1) 入栈出栈的完整解析
Hello 算法仓库中的链表栈用「头插法」实现 O(1) 入栈出栈的完整解析【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇技术指南聚焦 hello-algo 仓库中「基于链表实现栈」这一主题以 ru/codes/pythontutor/chapter_stack_and_queue/linkedlist_stack.md 中的可视化代码为核心结合仓库各语言源码完整讲解 LIFO 语义、头插法入栈与头部删除出栈的底层机制、LinkedListStack类的逐方法实现、驱动代码的运行结果以及 Python / C / Rust 三种实现的源码级差异。读完本文后你将能够独立用链表手写一个功能完整的栈并理解它与数组栈在性能与内存上的取舍。一、主题定位这个文档在仓库中对应什么linkedlist_stack.md 是俄语版代码教程pythontutor目录下的一个可视化代码文件服务于文档章节 ru/docs/chapter_stack_and_queue/stack.md 中「基于链表实现栈」一节。该文件本身结构极简由两部分组成文件头注释标注文件名、创建时间2024-01-05与作者一条 Python Tutor 渲染链接链接的#code参数是一段 URL 编码的完整 Python 源码内容为ListNode与LinkedListStack两个类的定义加上驱动代码Driver Code可直接粘贴到 Python Tutor 中逐步可视化执行。文档头部的标签行[file]{linkedlist_stack}-[class]{linked_list_stack}-[func]{}是 mkdocs 构建系统的取码标记文档页面ru/docs/chapter_stack_and_queue/stack.md 第 379–381 行通过该标记从真实源码文件 ru/codes/python/chapter_stack_and_queue/linkedlist_stack.py 中自动抽取LinkedListStack类注入页面。也就是说本文展开的所有代码都可以在仓库源码中找到逐行对应的实现而非仅存在于可视化链接中。二、栈的基本语义与操作复杂度栈Stack是一种遵循 LIFO后进先出Last In First Out逻辑的线性数据结构只能在一端栈顶插入和删除元素。仓库文档中将其类比为一摞盘子——想拿走底部的盘子必须先依次移走上面所有盘子。LinkedListStack支持的六个方法及其时间复杂度如下与 ru/docs/chapter_stack_and_queue/stack.md 的操作表格一致方法功能时间复杂度push(val)将元素入栈置于栈顶$O(1)$pop()弹出栈顶元素并返回$O(1)$peek()查看栈顶元素但不弹出$O(1)$size()返回栈中元素个数$O(1)$is_empty()判断栈是否为空$O(1)$to_list()序列化为普通列表以便打印$O(n)$所有核心操作的 $O(1)$ 复杂度正是「头插法」设计带来的入栈、出栈都只发生在链表头部无需遍历。三、核心数据结构头节点即栈顶链表栈的关键设计决策只有一条把链表的头节点当作栈顶peek尾节点当作栈底。push(val)等价于链表的头插——新建节点令其next指向当前头节点再把头指针移到新节点上pop()等价于链表的删头——取出头节点的值把头指针前移到下一个节点。由于不维护尾指针push/pop均不需要遍历链表这保证了严格意义上的常数时间操作。四、Python 实现逐段解析以下内容与 linkedlist_stack.md 中解码后的代码完全一致同时对应源码 ru/codes/python/chapter_stack_and_queue/linkedlist_stack.py。4.1 节点定义与导入from modules import ListNode # 仓库中定义于 ru/codes/python/modules/list_node.py仓库提供的 ListNode 只有两个字段class ListNode: Класс узла связного списка def __init__(self, val: int): self.val: int val # 节点值 self.next: ListNode | None None # 指向后继节点的引用ru/codes/python/modules/init.py 将ListNode统一导出因此各章代码都以from modules import ListNode的方式复用同一套节点定义。4.2 类成员与构造L14-L20class LinkedListStack: Стек на основе связного списка def __init__(self): self._peek: ListNode | None None # 头指针指向栈顶节点空栈为 None self._size: int 0 # 栈内元素个数两个私有成员即可覆盖全部状态_peek链表头指针。之所以命名为_peek而非_head是因为它同时兼任「栈顶」角色直接读它的.val就是peek()的返回值_size独立计数器。维护它可以让size()和is_empty()都不必遍历链表保持 $O(1)$。4.3 入栈三步头插L30-L35def push(self, val: int): Поместить в стек node ListNode(val) # ① 创建新节点 node.next self._peek # ② 新节点指向当前栈顶 self._peek node # ③ 头指针移到新节点 self._size 1这三行是链表头插的标准写法。顺序上第 ②、③ 步不可颠倒若先执行self._peek node就会丢失对原栈顶的引用。4.4 出栈与查看栈顶L37-L48def pop(self) - int: Извлечь из стека num self.peek() # 先取栈顶值空栈时 peek 会抛 IndexError self._peek self._peek.next # 头指针前移完成删头 self._size - 1 return num def peek(self) - int: Доступ к верхнему элементу стека if self.is_empty(): raise IndexError(стек пуст) return self._peek.val值得注意的设计点pop()通过先调用peek()实现空栈保护——对空栈执行pop()会抛出IndexError(стек пуст)而不是让self._peek.next在None上触发属性错误Python 由垃圾回收器处理被摘除节点因此pop()中没有显式的释放代码这一点与 C 版本形成对照见第六节。4.5 长度、判空与序列化L22-L28, L50-L58def size(self) - int: return self._size def is_empty(self) - bool: return self._size 0 def to_list(self) - list[int]: Преобразовать в список для вывода arr [] node self._peek while node: arr.append(node.val) node node.next arr.reverse() # 链表顺序为 栈顶 - 栈底翻转后为 栈底 - 栈顶 return arrto_list()沿next指针从头走到尾天然得到「栈顶在前」的顺序所以最后需要arr.reverse()让打印结果[1, 3, 2, 5, 4]以栈底元素 1 排在最左符合人们看「一摞盘子」的直觉。五、驱动代码与运行结果驱动部分位于 linkedlist_stack.py与可视化文档中的代码一致if __name__ __main__: stack LinkedListStack() stack.push(1) stack.push(3) stack.push(2) stack.push(5) stack.push(4) print(Стек stack , stack.to_list()) peek: int stack.peek() print(Верхний элемент peek , peek) pop: int stack.pop() print(Извлеченный элемент pop , pop) print(stack после извлечения , stack.to_list()) size: int stack.size() print(Длина стека size , size) is_empty: bool stack.is_empty() print(Пуст ли стек , is_empty)按 LIFO 语义逐步推演其运行结果步骤操作栈内状态左栈底右栈顶输出1push(1) push(3) push(2) push(5) push(4)[1, 3, 2, 5, 4]Стек stack [1, 3, 2, 5, 4]2peek()[1, 3, 2, 5, 4]Верхний элемент peek 43pop()[1, 3, 2, 5]Извлеченный элемент pop 44size()[1, 3, 2, 5]Длина стека size 45is_empty()[1, 3, 2, 5]Пуст ли стек False最后弹出的 4 恰好是最后压入的元素直观验证了「后进先出」栈顶指针始终指向最后入栈者。六、跨语言实现的源码对照仓库为同一算法提供了 14 种语言实现ru/codes/lang/chapter_stack_and_queue/linkedlist_stack.*其中 Python 与可视化文档逐行对应。以 C 和 Rust 为例可以看到同一个头插法设计在不同内存模型下的落地差异。6.1 C显式内存管理ru/codes/cpp/chapter_stack_and_queue/linkedlist_stack.cpp 中成员为ListNode *stackToppush同样是三步头插void push(int num) { ListNode *node new ListNode(num); node-next stackTop; stackTop node; stkSize; } int pop() { int num top(); ListNode *tmp stackTop; stackTop stackTop-next; delete tmp; // 手动释放被摘除节点 stkSize--; return num; }与 Python 版的差异集中在三处pop()中必须delete被摘除的节点析构函数里遍历链表逐个释放L21-L24top()对空栈抛出的异常类型是std::out_of_range而非 Python 的IndexError。此外C 的toVector()利用已知长度做逆序回填省去了 Python 版to_list()里的reverse()调用。6.2 Rust借用检查下的RcRefCell写法ru/codes/rust/chapter_stack_and_queue/linkedlist_stack.rs 中头指针类型为OptionRcRefCellListNodeTpub fn push(mut self, num: T) { let node ListNode::new(num); node.borrow_mut().next self.stack_peek.take(); // take() 临时取出旧头 self.stack_peek Some(node); self.stk_size 1; } pub fn pop(mut self) - OptionT { self.stack_peek.take().map(|old_head| { self.stack_peek old_head.borrow_mut().next.take(); self.stk_size - 1; old_head.borrow().val }) }从源码结构看这里用take()先移走Option里的旧头节点再赋值新头是为了在借用检查器borrow checker面前构造出合法的独占可变借用pop()返回OptionT而非抛异常是 Rust 处理「空栈」这一不可预期状态惯用手法。6.3 小结三种实现的共同骨架维度PythonCRust头指针类型ListNode \| NoneListNode *OptionRcRefCellListNodeT空栈弹出行为抛IndexError抛out_of_range返回None节点释放GC 自动回收delete 析构遍历Rc引用计数to_list策略正向收集后reverse()逆序回填递归拼接三种实现的状态都只有「头指针 计数器」两个变量进一步说明链表栈的实现骨架极其紧凑语言差异全部落在内存管理层面。七、链表栈的适用场景与性能特征结合仓库文档 ru/docs/chapter_stack_and_queue/stack.md 中「两种实现比较」一节的结论扩容数组栈在容量耗尽时扩容单次push退化为 $O(n)$属于「平时快、偶尔慢」链表栈每次push都新分配一个节点没有整体搬迁各次操作耗时稳定内存链表节点要为next指针额外付出空间而数组可能预留超出实际需要的容量两者各有所失需按场景权衡天然适配如果入栈的元素本身已经是节点对象例如遍历树时压入TreeNode链表栈可以直接压入节点而不需要额外包装这正是文档中提到的「跳过节点初始化步骤」的情形典型应用浏览器前进/后退历史两个栈配合实现 undo/redo、函数调用的栈帧管理递归深入即连续push回溯即连续pop。八、总结本文围绕 ru/codes/pythontutor/chapter_stack_and_queue/linkedlist_stack.md 的可视化代码展开先确认了该文档与 mkdocs 构建标记、真实源码文件之间的对应关系再逐一拆解了 LinkedListStack 的头插式push、带空栈保护的pop/peek、常数时间的size/is_empty与需要翻转的to_list随后通过驱动代码的运行推演验证了 LIFO 语义并用 C、Rust 源码对照说明了同一算法在不同内存模型下的实现差异。掌握这一实现后读者可以将其作为理解数组栈ru/codes/python/chapter_stack_and_queue/array_stack.py、双端队列deque等后续数据结构的基础。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考