| English | 释义 | 拼音 |
|---|---|---|
| queue/kjuː/ | 队列 | duì liè |
| push/pʊʃ/ | 入栈 | rù zhàn |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | 抽象数据类型 | chōu xiàng shù jù lèi xíng |
| stack/stæk/ | 栈 | zhàn |
| linked list/lɪŋkt lɪst/ | 链表 | liàn biǎo |
| LIFO/ˈlaɪfəʊ/ | 后进先出 | hòu jìn xiān chū |
| pop/pɒp/ | 出栈 | chū zhàn |
| pointer/ˈpɔɪntə/ | 指针 | zhǐ zhēn |
| FIFO/ˈfaɪfəʊ/ | 先进先出 | xiān jìn xiān chū |
| enqueue/enˈkjuː/ | 入队 | rù duì |
| dequeue/diːˈkjuː/ | 出队 | chū duì |
| node/nəʊd/ | 节点 | jié diǎn |
| traverse/trəˈvɜːs/ | 遍历 | biàn lì |
后退按钮和打印队列
- 你访问的每个页面都被压到一堆上;后退按钮把最上面那个拿走。你最近离开的页面是你最先回到的页面。
- 走廊那头,打印机按任务到达的顺序处理它们。先发送的文档先打出来,不管后面的有多小。
- 两种结构,相反的规则,课间休息前你都用过。两者都不说自己怎样存储;各自只说它的操作做什么。
- 这就是抽象数据类型(abstract data type)。这一课讲大纲点名的三种、各自的操作,以及怎样为一个情境论证选择。
什么是 ADT
- 抽象数据类型(ADT)是一组数据加上对这些数据的一组操作。这一句话就是一分的定义。
- 它由操作做什么定义,而不是数据怎样存储。实现被隐藏,所以可以改变而不影响使用它的代码。
- 栈、队列、链表、二叉树和数组都是 ADT。
一个抽象数据类型(ADT)由以下定义:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一个 ADT 指定操作(接口);实现是隐藏的,能自由改变。
栈
- 栈(stack)是一种在同一端——顶部——添加和移除项的列表,所以最后加入的项最先被移除:后进先出(LIFO)。
- 操作:入栈(push)加到顶部,出栈(pop)从顶部移除,peek 查看顶部,以及空和满的测试。
- 用途:撤销历史、后退按钮、函数调用的返回地址、括号匹配、回溯。

一切都发生在顶部
一个栈以哪种顺序工作?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一个栈是 LIFO:最近被 push 的项是第一个被 pop 的。
例题:追踪栈
- 一个栈从底部起保存
'P' 'N' 'Z' 'X' 'Y' 'W';顶指针在'W'。执行操作POP、POP、PUSH 'A'、PUSH 'B'、POP。栈里有什么,指针在哪里? - 两次出栈移除
'W'然后'Y'。两次入栈把'A'然后'B'放到它们的位置。最后一次出栈移除'B'。 - 栈保存
'P' 'N' 'Z' 'X' 'A',指针在'A'。在栈里最久的是最底下的'P';还能出栈五次,第六次就是错误——这正是出栈要先测空的原因。
一个栈保存 P N Z X Y W(顶是 W)。执行 POP、POP、PUSH 'A'、PUSH 'B'、POP 之后,哪一项在顶部?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
W 和 Y 出栈,A 然后 B 入栈,B 出栈。顶是 A,在 X 之上。
队列
- 队列(queue)是一种在尾部添加、从头部移除项的列表,所以最先加入的项最先被移除:先进先出(FIFO)。
- 操作:入队(enqueue)加到尾部,出队(dequeue)从头部移除,以及空和满的测试。
- 用途:打印假脱机、键盘缓冲、调度、商店里的顾客、广度优先搜索。

从后面加入,从前面离开
栈、队列和链表
后进先出 对 先进先出
一个栈是后进先出;push 和 pop 在同一端(顶)发生。
一个队列是先进先出:项从______被移除并在后面被添加。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
FIFO:从前面 dequeue,在后面 enqueue——像一队人。
例题:描述向队列添加和从队列移除
- 添加:检查队列不满;把项存到尾指针指示的位置;移动尾指针(并给计数加一)。
- 移除:检查队列不空;读取头指针处的项;移动头指针(并给计数减一)。
- 说明你用的约定:如果尾指针标记下一个空位,先存再移;如果它标记最后一项,先移再存。只要一致,两种都得分。
把向队列添加一项的步骤按顺序排列(尾指针标记下一个空位)。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
检查在最前;在这个约定下,然后存、再移。说明你用的约定。
链表
- 链表(linked list)是一种列表,其中每个节点(node)保存一个数据项和一个指向下一个节点的指针(pointer),再加一个指向第一个节点的起始指针。最后一个节点的指针是
NULL这样的哨兵。 - 操作:插入、删除、查找,以及遍历(traverse)——从头沿着指针按顺序访问每个节点。
- 相对数组的优点:插入或删除便宜,只需重接指针,列表按需增长。缺点:没有随机访问;到第十个节点要顺着九个指针走。

一个值和一个箭头,不断重复
一个链表:由指针连接的节点
每个节点存储一个值和一个指向下一个节点的指针。插入或删除只是重新连接指针——没有项移动,不像一个数组。
一个链表的每个节点保存:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一个节点存储它的值加上一个指向下一个节点的指针(引用);头标记开始,NULL 标记末尾。
一个链表使插入/删除便宜(只是重新连接指针)但随机访问慢(你必须从头跟着指针)。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
那就是数组对列表的权衡:数组给出 O(1) 索引访问;列表给出便宜的插入/删除。
例题:按顺序添加一个节点
- 描述怎样把一个新值插入保持升序的链表。[4]
- 从头开始沿指针遍历列表,直到找到位置之前的那个节点:最后一个值小于新值的节点。
- 取一个空闲节点,把新值存进去。把新节点的指针设为前一个节点当前指向的地址。
- 然后把前一个节点的指针设为新节点。如果新值应在最前面,改变的是头指针。
把向有序链表插入一个值的步骤按顺序排列。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
找到、填入、让新节点向前指,再重接前一个节点。最后两步颠倒会丢掉列表的其余部分。
论证选择
- 项必须按到达顺序处理——打印任务、按键、顾客:队列,因为它先进先出。
- 最近的项必须最先处理——撤销、后退、嵌套调用:栈,因为它后进先出。
- 项频繁地在有序集合的中间插入或删除,而且大小未知:链表,因为只有指针改变,什么都不用移动。
- 说出结构,说出它的规则,把规则和情境联系起来。
把每个 ADT 与它的规则和一个典型用途配对。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
栈 = 后进先出;队列 = 先进先出;一个链表用指针把节点串成链。
打印任务必须按发送顺序打印。用哪种 ADT,为什么?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
到达顺序就是 FIFO 规则。栈会先打印最近的任务。
ADT 与实现
- ADT 是行为:入栈和出栈、入队和出队、插入和遍历。
- 实现是存储:在本课程中,是一个数组加几个指针变量(下一课)。
- 关于 ADT 的题要操作和规则;关于实现的题要数组、指针和检查。
容易丢掉的分
- 入栈和入队先测满;出栈和出队先测空。把检查写进描述里。
- 向链表插入:先设新节点的指针,再改前一个节点的,否则列表的其余部分就丢了。
- 栈只在一端变化,队列在两端。"从队列顶部移除"是栈的答案。
- 缩写展开一次:LIFO,后进先出;FIFO,先进先出。
你掌握了
- ADT 是一组数据加上对它的一组操作;是行为,不是存储
- 栈:在顶部添加和移除,LIFO,入栈和出栈 · 队列:尾部添加、头部移除,FIFO,入队和出队
- 链表:从头指针出发的值 + 指针节点;插入删除便宜,随机访问慢;沿指针遍历
- 按规则论证:到达顺序 → 队列;最近优先 → 栈;频繁在中间插入 → 链表