| English | 释义 | 拼音 |
|---|---|---|
| overflow/ˌəʊvəˈfləʊ/ | 溢出 | yì chū |
| underflow/ˌʌndəˈfləʊ/ | 下溢 | xià yì |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | 循环数组 | xún huán shù zǔ |
| free list/friː lɪst/ | 空闲列表 | kòng xián liè biǎo |
内存里根本没有栈
- 打开一台计算机去找栈。你找不到。内存是一个巨大的、编了号的单元数组,仅此而已。
- 每个栈、每个队列、每个链表都是那个数组加上两三个记住东西在哪里的整数变量。入栈是"给一个数加一然后存";出队是"读一个单元然后给另一个数加一"。
- 这一课整个都是记账:哪些指针、哪些检查,以及边界上发生什么。
- 考试要求你描述声明、让指针走过几个操作,并说出为什么要有那些检查。
数组中的栈
- 把项存在
Stack[1:MaxSize]中,配一个整数Top,栈空时为 0。 - Push(x):如果
Top = MaxSize则栈满,即溢出(overflow);否则Top ← Top + 1,Stack[Top] ← x。 - Pop():如果
Top = 0则栈空,即下溢(underflow);否则返回Stack[Top],Top ← Top − 1。

数组从不移动;只有 Top 在动
把一个项 push 到一个已经满的栈上引起一个栈______。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
上溢 = 当 Top = MaxSize 时 push;从一个空栈(Top = 0)pop 是下溢。
把每个数组栈条件与它的含义配对。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Top 计数项:0 = 空,MaxSize = 满;两个错误情况是下溢和上溢。
例题:声明并初始化栈
- 描述用数组实现一个最多 50 个整数的栈所需的声明和初始化。[5]
- 一个 50 个
INTEGER元素的数组,DECLARE Stack : ARRAY[1:50] OF INTEGER,用来保存项。 - 一个设为 50 的常量或变量
MaxSize,让入栈能测满。 - 一个
INTEGER栈顶指针Top,初始化为 0 表示栈空;出栈用它测下溢,入栈把它与MaxSize比较测溢出。
哪些属于基于数组的栈的声明和初始化?选出所有适用的。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
栈只需要一个指针 Top。头指针属于队列。
普通数组中的队列
- 两个指针:
Front指向下一个要离开的项,Rear指向下一个空位。入队存到Rear并移动它;出队从Front读并移动它。 - 两个指针只会向前移动,所以几次操作后它们就走出数组末尾,而开头的单元空着却无法使用。
- 解决办法是让指针绕回来。
循环数组
- 循环数组(circular array)在指针越过最后一个单元时把它绕回第一个:索引从 1 开始时,
Rear ← (Rear MOD MaxSize) + 1。 - Enqueue(x):检查不满;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x。Dequeue():检查不空;返回Queue[Front];Front ← (Front MOD MaxSize) + 1。 - 保留一个单独的计数:队列完全满和完全空时,两个指针的相对位置相同,所以仅靠指针分不出两者。

最后一个单元之后是第一个单元
用数组实现 ADT
先进先出
一个队列是先进先出——在后面 enqueue,从前面 dequeue。
为什么为一个队列用一个循环数组?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一个线性队列在 Front 前进时浪费开始的单元格;用 MOD 绕回重用它们。
一个循环队列用 MOD,这样前/后指针绕回并重用在数组开始释放的单元格。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
(pointer MOD MaxSize) + 1 把索引绕回第一个单元格,所以一个线性队列不再浪费 Front 经过的单元格。
例题:让指针走一走
MaxSize = 6时:若Rear = 5,则(5 MOD 6) + 1 = 6,下一项进入第 6 格。若Rear = 6,则(6 MOD 6) + 1 = 1:指针绕到第 1 格。- 一个大小为5的数组存储环形队列,索引从0到4,其中包含
Front = 3、Rear = 3和一个已存储项。先添加两项,再移除两项。 使用0基索引时,每次移动操作耗时(pointer + 1) MOD 5。 - 添加两次移动
Rear:3 → 4,再 4 → 0,因为 (4 + 1) MOD 5 = 0。移除两次移动Front:3 → 4 → 0。剩下一项,在索引 0,队列复用了数组开头空出的单元。
循环队列使用第 1 到 6 格,Rear = 6。执行 Rear ← (Rear MOD 6) + 1 后,下一项放在哪里?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
6 MOD 6 = 0,加 1 得 1。指针绕回数组开头。
例题:用文字描述入队算法
- 描述向循环队列添加一项的算法。[4]
- 如果计数等于大小,报告队列已满并停止。
- 否则给尾指针加一;如果它现在越过了最后一个索引,把它设为第一个索引。
- 把项存到尾指针处,计数加一。
把向循环队列添加的步骤按顺序排列。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
检查、移动、绕回、存储、计数。绕回正是让数组循环的那一步。
数组中的链表
- 用一个节点记录数组,每个节点带一个
NextIndex索引;-1标记末尾。一个Head索引标记第一个节点,列表为空时是-1。 - 未使用的槽从
FreeListHead起串成一个空闲列表(free list),就像数据列表串起已使用的槽一样。
TYPE TNode
DECLARE Value : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- 插入:取
FreeListHead处的槽,设置它的Value和NextIndex,再重接前一个节点的NextIndex或Head。删除:解开该节点,把它的槽还到空闲列表前端。

两个列表共用一个数组:数据列表和空闲列表
在一个基于数组的链表中,空闲列表:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
空闲列表把空闲的槽链接起来,所以一个插入能抓一个、一个删除能还一个——像一个空槽的第二个链表。
例题:向数组存放的列表插入
Data和Pointer数组存储链表1 → 3 → 4,其中Start = 1;索引1存储D40,索引3存储D32,索引4存储D11并带有空指针。空闲列表从索引2开始,后续依次为2 → 5。将D6插入到D32和D11之间。- 取第一个空闲节点,索引 2,把
FreeStart设为它的指针 5。把D6存入Data[2]。 - 把
Pointer[2]设为Pointer[3]原来的值 4。然后把Pointer[3]设为 2。 - 列表现在是 1 → 3 → 2 → 4,空闲列表是 5 → 空。若问实现:一个数据数组、一个平行的指针数组(或记录字段)、一个起始指针和一个空闲列表指针。
在例题中,插入 D6 之后空闲列表从索引 ____ 开始。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
索引 2 被从空闲列表取走,所以 FreeStart 移到索引 2 原来指向的 5。
向列表插入时,应先改前一个节点的指针,再设新节点的指针。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
先把新节点的指针设为原来的下一个节点。先重接前一个节点会丢掉列表其余部分的地址。
容易丢掉的分
- 检查在最前:入栈或入队前测满,出栈或出队前测空。要描述它们;它们是分。
- 绕回公式取决于索引:从 1 开始用
(Rear MOD MaxSize) + 1,从 0 开始用(Rear + 1) MOD Size。与题目的边界一致。 - 计数才能把满的循环队列和空的区分开。仅靠指针不行。
- 先设新节点的
NextIndex再重接前一个节点,并把删除节点的槽还回空闲列表,否则数组会慢慢被不可达的单元填满。
你掌握了
- 数组中的栈:
Stack[1:MaxSize]和从 0 开始的Top指针;Top = MaxSize是溢出,Top = 0是下溢 - 循环队列:
Front和Rear用MOD绕回;单独的计数区分满与空 - 数组中的链表:带
NextIndex索引的节点记录、一个Head,以及串起空闲槽的空闲列表 - 每个操作都是检查、指针运算、然后存或读;ADT 的行为不因存储方式而改变