Implementing ADTs using arrays · 用数组实现 ADT
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| 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 |
There is no such thing as a stack in memory
- Open a computer and look for the stack. You will not find one. Memory is one enormous array of numbered cells, and that is all there is.
- Every stack, every queue, every linked list is that array plus two or three integer variables that remember where things are. Push is "add one to a number and store"; dequeue is "read a cell and add one to a different number".
- The whole of this lesson is bookkeeping: which pointers, which checks, and what happens at the edges.
- The exam asks you to describe the declarations, walk the pointers through a few operations, and say why the checks are there.
内存里根本没有栈
- 打开一台计算机去找栈。你找不到。内存是一个巨大的、编了号的单元数组,仅此而已。
- 每个栈、每个队列、每个链表都是那个数组加上两三个记住东西在哪里的整数变量。入栈是"给一个数加一然后存";出队是"读一个单元然后给另一个数加一"。
- 这一课整个都是记账:哪些指针、哪些检查,以及边界上发生什么。
- 考试要求你描述声明、让指针走过几个操作,并说出为什么要有那些检查。
A stack in an array
- Hold the items in
Stack[1:MaxSize]with an integerTop, 0 when the stack is empty. - Push(x): if
Top = MaxSizethe stack is full, an overflow 溢出; otherwiseTop ← Top + 1andStack[Top] ← x. - Pop(): if
Top = 0the stack is empty, an underflow 下溢; otherwise returnStack[Top]andTop ← Top − 1.
The array never moves; only Top does
数组中的栈
- 把项存在
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 在动
Pushing an item onto a stack that is already full causes a stack . · 把一个项 push 到一个已经满的栈上引起一个栈。
Overflow = push when Top = MaxSize; popping from an empty stack (Top = 0) is underflow. · 上溢 = 当 Top = MaxSize 时 push;从一个空栈(Top = 0)pop 是下溢。
Match each array-stack condition to what it means. · 把每个数组栈条件与它的含义配对。
Top counts the items: 0 = empty, MaxSize = full; the two error cases are underflow and overflow. · Top 计数项:0 = 空,MaxSize = 满;两个错误情况是下溢和上溢。
Worked example: declare and initialise the stack
- Describe the declarations and initialisation needed to implement a stack of up to 50 integers using an array. [5]
- An array of 50 elements of type
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, to hold the items. - A constant or variable
MaxSizeset to 50, so that push can test for full. - An
INTEGERtop-of-stack pointer,Top, initialised to 0 to show the stack is empty; pop tests it for underflow, and push compares it withMaxSizefor overflow.
例题:声明并初始化栈
- 描述用数组实现一个最多 50 个整数的栈所需的声明和初始化。[5]
- 一个 50 个
INTEGER元素的数组,DECLARE Stack : ARRAY[1:50] OF INTEGER,用来保存项。 - 一个设为 50 的常量或变量
MaxSize,让入栈能测满。 - 一个
INTEGER栈顶指针Top,初始化为 0 表示栈空;出栈用它测下溢,入栈把它与MaxSize比较测溢出。
Which belong in the declaration and initialisation of an array-based stack? Select all · 所有 that apply. · 哪些属于基于数组的栈的声明和初始化?选出所有适用的。
A stack needs one pointer, Top. A front pointer belongs to a queue. · 栈只需要一个指针 Top。头指针属于队列。
A queue in a plain array
- Two pointers:
Frontfor the next item to leave,Rearfor the next free space. Enqueue stores atRearand moves it on; dequeue reads atFrontand moves it on. - Both pointers only ever move forward, so after a few operations they march off the end of the array while the cells at the start sit empty and unusable.
- The fix is to let the pointers wrap around.
普通数组中的队列
- 两个指针:
Front指向下一个要离开的项,Rear指向下一个空位。入队存到Rear并移动它;出队从Front读并移动它。 - 两个指针只会向前移动,所以几次操作后它们就走出数组末尾,而开头的单元空着却无法使用。
- 解决办法是让指针绕回来。
The circular array
- A circular array 循环数组 wraps a pointer back to the first cell when it passes the last: with 1-based indices,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): check not full;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): check not empty; returnQueue[Front];Front ← (Front MOD MaxSize) + 1. - Keep a separate count: when the queue is completely full and when it is completely empty the two pointers are in the same relative position, so the pointers alone cannot tell the two apart.
After the last cell comes the first cell
循环数组
- 循环数组(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。 - 保留一个单独的计数:队列完全满和完全空时,两个指针的相对位置相同,所以仅靠指针分不出两者。
最后一个单元之后是第一个单元
Implementing ADTs with arrays · 用数组实现 ADT
FIFO · 先进先出
A queue · 队列 is first-in-first-out — enqueue at the back, dequeue from the front. · 一个队列是先进先出——在后面 enqueue,从前面 dequeue。
Why use a circular array for a queue? · 为什么为一个队列用一个循环数组?
A linear queue wastes the cells at the start as Front advances; wrapping with MOD reuses them. · 一个线性队列在 Front 前进时浪费开始的单元格;用 MOD 绕回重用它们。
A circular queue uses MOD so the front/rear pointers wrap around and reuse the cells freed at the start of the array. · 一个循环队列用 MOD,这样前/后指针绕回并重用在数组开始释放的单元格。
(pointer MOD MaxSize) + 1 wraps the index back to the first cell, so a linear queue no longer wastes the cells Front has passed. · (pointer MOD MaxSize) + 1 把索引绕回第一个单元格,所以一个线性队列不再浪费 Front 经过的单元格。
Worked example: walk the pointers
- With
MaxSize = 6: ifRear = 5, then(5 MOD 6) + 1 = 6, so the next item goes in cell 6. IfRear = 6, then(6 MOD 6) + 1 = 1: the pointer wraps to cell 1. - A circular queue is held in an array of size 5, indices 0 to 4, with
Front = 3,Rear = 3and one item stored. Two items are added, then two removed. With 0-based indices each move is(pointer + 1) MOD 5. - Adding twice moves
Rear: 3 → 4, then 4 → 0, because (4 + 1) MOD 5 = 0. Removing twice movesFront: 3 → 4 → 0. One item remains, at index 0, and the queue reused the cells freed at the start of the array.
例题:让指针走一走
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 开始时,每次移动是(指针 + 1) MOD 5。 - 添加两次移动
Rear:3 → 4,再 4 → 0,因为 (4 + 1) MOD 5 = 0。移除两次移动Front:3 → 4 → 0。剩下一项,在索引 0,队列复用了数组开头空出的单元。
A circular queue uses cells 1 to 6 and Rear = 6. After Rear ← (Rear MOD 6) + 1, where does the next item go? · 循环队列使用第 1 到 6 格,Rear = 6。执行 Rear ← (Rear MOD 6) + 1 后,下一项放在哪里?
6 MOD 6 = 0, plus 1 gives 1. The pointer wraps to the start of the array. · 6 MOD 6 = 0,加 1 得 1。指针绕回数组开头。
Worked example: the enqueue algorithm in words
- Describe the algorithm for adding an item to a circular queue. [4]
- If the count equals the size, report that the queue is full and stop.
- Otherwise add one to the rear pointer; if it is now past the last index, set it to the first index.
- Store the item at the rear pointer and add one to the count.
例题:用文字描述入队算法
- 描述向循环队列添加一项的算法。[4]
- 如果计数等于大小,报告队列已满并停止。
- 否则给尾指针加一;如果它现在越过了最后一个索引,把它设为第一个索引。
- 把项存到尾指针处,计数加一。
Put the steps of adding to a circular queue in order. · 把向循环队列添加的步骤按顺序排列。
Check, move, wrap, store, count. The wrap is what makes the array circular. · 检查、移动、绕回、存储、计数。绕回正是让数组循环的那一步。
A linked list in an array
- Use an array of node records, each with a
Nextindex;-1marks the end. AHeadindex marks the first node,-1if the list is empty. - The unused slots are chained into a free list 空闲列表 from
FreeListHead, exactly as the data list chains its used ones.
- Insert: take the slot at
FreeListHead, set itsValueandNext, then rewire the previous node'sNextorHead. Delete: unlink the node and return its slot to the front of the free list.
Two lists share one array: the data list and the free list
数组中的链表
- 用一个节点记录数组,每个节点带一个
Next索引;-1标记末尾。一个Head索引标记第一个节点,列表为空时是-1。 - 未使用的槽从
FreeListHead起串成一个空闲列表(free list),就像数据列表串起已使用的槽一样。
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : INTEGER // 下一个节点的索引,或 -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // 空时为 -1
DECLARE FreeListHead : INTEGER // 第一个未使用的槽
- 插入:取
FreeListHead处的槽,设置它的Value和Next,再重接前一个节点的Next或Head。删除:解开该节点,把它的槽还到空闲列表前端。
两个列表共用一个数组:数据列表和空闲列表
In an array-based linked list, the free list: · 在一个基于数组的链表中,空闲列表:
The free list links the spare slots, so an insert can grab one and a delete can return one — like a second linked list of empties. · 空闲列表把空闲的槽链接起来,所以一个插入能抓一个、一个删除能还一个——像一个空槽的第二个链表。
Worked example: insert into the array-held list
DataandPointerarrays hold the list 1 → 3 → 4, withStart = 1; index 1 holdsD40, index 3 holdsD32, index 4 holdsD11with a null pointer. The free list starts at index 2 and continues 2 → 5. InsertD6betweenD32andD11.- Take the first free node, index 2, and set
FreeStartto its pointer, 5. StoreD6inData[2]. - Set
Pointer[2]to the valuePointer[3]held, which is 4. Then setPointer[3]to 2. - The list now reads 1 → 3 → 2 → 4 and the free list is 5 → null. The implementation, if asked: an array for the data, a parallel array (or record field) for the pointers, a start pointer, and a free-list pointer.
例题:向数组存放的列表插入
Data和Pointer数组保存列表 1 → 3 → 4,Start = 1;索引 1 存D40,索引 3 存D32,索引 4 存D11,指针为空。空闲列表从索引 2 开始,接着 2 → 5。在D32和D11之间插入D6。- 取第一个空闲节点,索引 2,把
FreeStart设为它的指针 5。把D6存入Data[2]。 - 把
Pointer[2]设为Pointer[3]原来的值 4。然后把Pointer[3]设为 2。 - 列表现在是 1 → 3 → 2 → 4,空闲列表是 5 → 空。若问实现:一个数据数组、一个平行的指针数组(或记录字段)、一个起始指针和一个空闲列表指针。
In the worked example, after D6 is inserted the free list starts at index ____. · 在例题中,插入 D6 之后空闲列表从索引 ____ 开始。
Index 2 was taken from the free list, so FreeStart moves to what index 2 pointed to, which was 5. · 索引 2 被从空闲列表取走,所以 FreeStart 移到索引 2 原来指向的 5。
When inserting into the list, the previous node's pointer should be changed before the new node's pointer is set. · 向列表插入时,应先改前一个节点的指针,再设新节点的指针。
Set the new node's pointer to the old next node first. Rewiring the previous node first loses the address of the rest of the list. · 先把新节点的指针设为原来的下一个节点。先重接前一个节点会丢掉列表其余部分的地址。
Marks that slip away
- The checks come first: full before push or enqueue, empty before pop or dequeue. Describe them; they are marks.
- The wrap formula depends on the indices:
(Rear MOD MaxSize) + 1for 1-based,(Rear + 1) MOD Sizefor 0-based. Match the question's bounds. - The count is what tells a full circular queue from an empty one. Pointers alone cannot.
- Set the new node's
Nextbefore rewiring the previous node, and return a deleted node's slot to the free list, or the array slowly fills with unreachable cells.
容易丢掉的分
- 检查在最前:入栈或入队前测满,出栈或出队前测空。要描述它们;它们是分。
- 绕回公式取决于索引:从 1 开始用
(Rear MOD MaxSize) + 1,从 0 开始用(Rear + 1) MOD Size。与题目的边界一致。 - 计数才能把满的循环队列和空的区分开。仅靠指针不行。
- 先设新节点的
Next再重接前一个节点,并把删除节点的槽还回空闲列表,否则数组会慢慢被不可达的单元填满。
You've got it
- stack in an array:
Stack[1:MaxSize]and aToppointer starting at 0;Top = MaxSizeis overflow,Top = 0is underflow - circular queue:
FrontandRearwrap withMOD; a separate count distinguishes full from empty - linked list in an array: node records with a
Nextindex, aHead, and a free list chaining the spare slots - every operation is check, then pointer arithmetic, then store or read; the ADT's behaviour is unchanged by how it is stored
你掌握了
- 数组中的栈:
Stack[1:MaxSize]和从 0 开始的Top指针;Top = MaxSize是溢出,Top = 0是下溢 - 循环队列:
Front和Rear用MOD绕回;单独的计数区分满与空 - 数组中的链表:带
Next索引的节点记录、一个Head,以及串起空闲槽的空闲列表 - 每个操作都是检查、指针运算、然后存或读;ADT 的行为不因存储方式而改变