知识卡片
栈限制同一端进入与离开
栈只在栈顶放入或取出元素,后进入的先离开。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 ]