知识卡片

结构图卡 · 5654.d.1.a.1.c.1.c

栈限制同一端进入与离开

理解等级:中级

栈只在栈顶放入或取出元素,后进入的先离开。push增加顶部,pop移除并返回顶部,peek只观察不移除;限制操作接口就能让数组或链表表现为同一种LIFO抽象。

Go切片可把尾部当栈顶,直接下标访问前必须检查非空。链表实现既可同在头端进出,也可同在尾端进出;原书文字用头插,而Go的container/list例使用PushBack/Back,两种实现都满足同一抽象。

结构图:

flowchart LR
 A[先压入A] --> B[再压入B]
 B --> C[顶部B先弹出]
 C --> D[A后弹出]

链表栈的pop/peek在空时返回nil,在当前只放整数的示例中可区分空;若泛化为any且允许存nil,则应使用额外存在标志,避免把合法值和空状态混在一起。数组栈则用尾部追加和截短,追加仍受扩容均摊条件约束。

arrayStack.peek空时返回nil,但pop随后仍截短切片,空时会产生负边界并panic,不能把peek的空判断当pop已经安全。数组与链表的性能比较还受分配、缓存及扩容影响,没有实测便不承诺所有输入下的快慢顺序。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      栈可以视为一种受限制的数组或链表 。换句话说,我们可以“屏蔽”数组或链表的部分无关 操作,使其对外表现的逻辑符合栈的特性。 1. 基于链表的实现 使用链表实现栈时,我们可以将链表的头节点视为栈顶,尾节点视为栈底。 如图5

    • · 查看原书依据

      func (s *linkedListStack) pop() any { if s.isEmpty() { 第5 章 栈与队列 hello‑algo.com 94 return nil } e := s.data.Ba

    • · 查看原书依据

      func (s *arrayStack) pop() any { 第5 章 栈与队列 hello‑algo.com 96 val := s.peek () s.data = s.data[:len(s.data)-1 ]

    参考来源

    - 位置:《Hello 算法--Go版本》第05章《栈与队列》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/2.html;spine 1,归一字符[34358,34468)) - 结论依据:实际栈定义/操作表/切片及链表实现对照,区分抽象与具体端点。 - 原始内容:栈可以视为一种受限制的数组或链表 。换句话说,我们可以“屏蔽”数组或链表的部分无关 操作,使其对外表现的逻辑符合栈的特性。 1. 基于链表的实现 使用链表实现栈时,我们可以将链表的头节点视为栈顶,尾节点视为栈底。 如图5 补充原书证据:spine 1 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/2.html;归一字符[34916,35026)。 - 结论依据:实际空检查与返回nil及数组栈引入,保留不同实现边界。 - 原始内容:func (s *linkedListStack) pop() any { if s.isEmpty() { 第5 章 栈与队列 hello‑algo.com 94 return nil } e := s.data.Ba 补充原书证据:spine 2 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;归一字符[549,659)。 - 结论依据:实际pop无独立空检查,指出越界而不照抄。 - 原始内容:func (s *arrayStack) pop() any { 第5 章 栈与队列 hello‑algo.com 96 val := s.peek () s.data = s.data[:len(s.data)-1 ]