Abstract Data Types — stack, queue, linked list · 抽象数据类型——栈、队列、链表
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| 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ì |
The Back button and the printer queue
- Every page you visit is pushed onto a pile; the Back button takes the top one off. The page you left most recently is the first you return to.
- Down the corridor, a printer works through jobs in the order they arrived. The document sent first comes out first, however small the ones behind it.
- Two structures, opposite rules, and you use both before break. Neither says how it is stored; each says only what its operations do.
- That is an abstract data type 抽象数据类型. This lesson is the three the syllabus names, the operations on each, and how to justify one for a situation.
后退按钮和打印队列
- 你访问的每个页面都被压到一堆上;后退按钮把最上面那个拿走。你最近离开的页面是你最先回到的页面。
- 走廊那头,打印机按任务到达的顺序处理它们。先发送的文档先打出来,不管后面的有多小。
- 两种结构,相反的规则,课间休息前你都用过。两者都不说自己怎样存储;各自只说它的操作做什么。
- 这就是抽象数据类型(abstract data type)。这一课讲大纲点名的三种、各自的操作,以及怎样为一个情境论证选择。
What an ADT is
- An abstract data type (ADT) is a collection of data together with a set of operations on that data. That one sentence is the one-mark definition.
- It is defined by what the operations do, not by how the data is stored. The implementation is hidden, so it can change without affecting the code that uses it.
- A stack, a queue, a linked list, a binary tree and an array are all ADTs.
什么是 ADT
- 抽象数据类型(ADT)是一组数据加上对这些数据的一组操作。这一句话就是一分的定义。
- 它由操作做什么定义,而不是数据怎样存储。实现被隐藏,所以可以改变而不影响使用它的代码。
- 栈、队列、链表、二叉树和数组都是 ADT。
An Abstract Data Type (ADT) is defined by: · 一个抽象数据类型(ADT)由以下定义:
An ADT specifies the operations (the interface); the implementation is hidden and can change freely. · 一个 ADT 指定操作(接口);实现是隐藏的,能自由改变。
The stack
- A stack 栈 is a list in which items are added to and removed from the same end, the top, so the last item added is the first removed: LIFO 后进先出.
- Operations: push 入栈 adds to the top, pop 出栈 removes from the top, peek looks at the top, and tests for empty and full.
- Uses: undo history, the Back button, the return addresses of function calls, checking brackets, backtracking.
Everything happens at the top
栈
- 栈(stack)是一种在同一端——顶部——添加和移除项的列表,所以最后加入的项最先被移除:后进先出(LIFO)。
- 操作:入栈(push)加到顶部,出栈(pop)从顶部移除,peek 查看顶部,以及空和满的测试。
- 用途:撤销历史、后退按钮、函数调用的返回地址、括号匹配、回溯。
一切都发生在顶部
A stack works in which order? · 一个栈以哪种顺序工作?
A stack is LIFO: the most recently pushed item is the first to be popped. · 一个栈是 LIFO:最近被 push 的项是第一个被 pop 的。
Worked example: trace the stack
- A stack holds, from the bottom,
'P' 'N' 'Z' 'X' 'Y' 'W'; the top pointer is at'W'. The operationsPOP,POP,PUSH 'A',PUSH 'B',POPare performed. What does the stack hold, and where is the pointer? - The two pops remove
'W'then'Y'. The pushes put'A'then'B'in their places. The last pop removes'B'. - The stack holds
'P' 'N' 'Z' 'X' 'A', with the pointer at'A'. The item on the stack longest is the bottom one,'P'; five more pops are possible, and a sixth would be an error, which is why pop tests for empty first.
例题:追踪栈
- 一个栈从底部起保存
'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';还能出栈五次,第六次就是错误——这正是出栈要先测空的原因。
A stack holds P N Z X Y W (top is W). After POP, POP, PUSH 'A', PUSH 'B', POP, which item is on top? · 一个栈保存 P N Z X Y W(顶是 W)。执行 POP、POP、PUSH 'A'、PUSH 'B'、POP 之后,哪一项在顶部?
W and Y are popped, A then B pushed, B popped. The top is A, above X. · W 和 Y 出栈,A 然后 B 入栈,B 出栈。顶是 A,在 X 之上。
The queue
- A queue 队列 is a list in which items are added at the rear and removed from the front, so the first item added is the first removed: FIFO 先进先出.
- Operations: enqueue 入队 adds at the rear, dequeue 出队 removes from the front, and tests for empty and full.
- Uses: print spooling, keyboard buffers, scheduling, customers in a shop, breadth-first search.
Join at the back, leave from the front
队列
- 队列(queue)是一种在尾部添加、从头部移除项的列表,所以最先加入的项最先被移除:先进先出(FIFO)。
- 操作:入队(enqueue)加到尾部,出队(dequeue)从头部移除,以及空和满的测试。
- 用途:打印假脱机、键盘缓冲、调度、商店里的顾客、广度优先搜索。
从后面加入,从前面离开
Stacks, queues & linked lists · 栈、队列和链表
LIFO vs FIFO · 后进先出 对 先进先出
A stack · 栈 is last-in-first-out; push and pop happen at the same end (the top). · 一个栈是后进先出;push 和 pop 在同一端(顶)发生。
A queue is first-in-first-out: items are removed from the ______ and added at the rear. · 一个队列是先进先出:项从______被移除并在后面被添加。
FIFO: dequeue from the front, enqueue at the rear — like a line of people. · FIFO:从前面 dequeue,在后面 enqueue——像一队人。
Worked example: describe adding to and removing from a queue
- Adding: check that the queue is not full; store the item at the position given by the rear pointer; move the rear pointer on (and add one to the count).
- Removing: check that the queue is not empty; read the item at the front pointer; move the front pointer on (and subtract one from the count).
- State the convention you use: if the rear pointer marks the next free space, store first and then move; if it marks the last item, move first and then store. Either scores, if you are consistent.
例题:描述向队列添加和从队列移除
- 添加:检查队列不满;把项存到尾指针指示的位置;移动尾指针(并给计数加一)。
- 移除:检查队列不空;读取头指针处的项;移动头指针(并给计数减一)。
- 说明你用的约定:如果尾指针标记下一个空位,先存再移;如果它标记最后一项,先移再存。只要一致,两种都得分。
Put the steps of adding an item to a queue in order (rear pointer marks the next free space). · 把向队列添加一项的步骤按顺序排列(尾指针标记下一个空位)。
The check comes first; then store, then move, under this convention. Say which convention you use. · 检查在最前;在这个约定下,然后存、再移。说明你用的约定。
The linked list
- A linked list 链表 is a list in which each node 节点 holds a data item and a pointer 指针 to the next node, with a start pointer to the first node. The last node's pointer is a sentinel such as
NULL. - Operations: insert, delete, search, and traverse 遍历, following the pointers from the head to visit every node in order.
- Advantage over an array: inserting or deleting is cheap, just rewire pointers, and the list grows as needed. Disadvantage: no random access; reaching the tenth node means following nine pointers.
A value and an arrow, repeated
链表
- 链表(linked list)是一种列表,其中每个节点(node)保存一个数据项和一个指向下一个节点的指针(pointer),再加一个指向第一个节点的起始指针。最后一个节点的指针是
NULL这样的哨兵。 - 操作:插入、删除、查找,以及遍历(traverse)——从头沿着指针按顺序访问每个节点。
- 相对数组的优点:插入或删除便宜,只需重接指针,列表按需增长。缺点:没有随机访问;到第十个节点要顺着九个指针走。
一个值和一个箭头,不断重复
A linked list: nodes joined by pointers · 一个链表:由指针连接的节点
Each node stores a value and a pointer to the next node. Inserting or deleting just re-links pointers — no items shift along, unlike an array. · 每个节点存储一个值和一个指向下一个节点的指针。插入或删除只是重新连接指针——没有项移动,不像一个数组。
Each node of a linked list holds: · 一个链表的每个节点保存:
A node stores its value plus a pointer (reference) to the next node; the head marks the start, NULL the end. · 一个节点存储它的值加上一个指向下一个节点的指针(引用);头标记开始,NULL 标记末尾。
A linked list makes inserting/deleting cheap (just rewire pointers) but random access slow (you must follow pointers from the head). · 一个链表使插入/删除便宜(只是重新连接指针)但随机访问慢(你必须从头跟着指针)。
That is the array-vs-list trade-off: arrays give O(1) index access; lists give cheap insert/delete. · 那就是数组对列表的权衡:数组给出 O(1) 索引访问;列表给出便宜的插入/删除。
Worked example: add a node in order
- Describe how a new value is inserted into a linked list that is kept in ascending order. [4]
- Traverse the list from the head, following the pointers, until the node before the position is found: the last node whose value is smaller than the new one.
- Take a free node and store the new value in it. Set the new node's pointer to the address the previous node currently points to.
- Then set the previous node's pointer to the new node. If the new value belongs at the front, it is the head pointer that changes instead.
例题:按顺序添加一个节点
- 描述怎样把一个新值插入保持升序的链表。[4]
- 从头开始沿指针遍历列表,直到找到位置之前的那个节点:最后一个值小于新值的节点。
- 取一个空闲节点,把新值存进去。把新节点的指针设为前一个节点当前指向的地址。
- 然后把前一个节点的指针设为新节点。如果新值应在最前面,改变的是头指针。
Put the steps of inserting a value into an ordered linked list in order. · 把向有序链表插入一个值的步骤按顺序排列。
Find, fill, point the new node forward, then rewire the previous node. Reversing the last two loses the rest of the list. · 找到、填入、让新节点向前指,再重接前一个节点。最后两步颠倒会丢掉列表的其余部分。
Justifying the choice
- Items must be handled in the order they arrived, print jobs, key presses, customers: a queue, because it is first in, first out.
- The most recent item must be handled first, undo, going back, nested calls: a stack, because it is last in, first out.
- Items are frequently inserted or deleted in the middle of an ordered collection, and the size is unknown: a linked list, because only pointers change and nothing is shifted.
- Name the structure, name its rule, tie the rule to the situation.
论证选择
- 项必须按到达顺序处理——打印任务、按键、顾客:队列,因为它先进先出。
- 最近的项必须最先处理——撤销、后退、嵌套调用:栈,因为它后进先出。
- 项频繁地在有序集合的中间插入或删除,而且大小未知:链表,因为只有指针改变,什么都不用移动。
- 说出结构,说出它的规则,把规则和情境联系起来。
Match each ADT to its rule and a typical use. · 把每个 ADT 与它的规则和一个典型用途配对。
Stack = last-in-first-out; queue = first-in-first-out; a linked list chains nodes with pointers. · 栈 = 后进先出;队列 = 先进先出;一个链表用指针把节点串成链。
Print jobs must be printed in the order they were sent. Which ADT, and why? · 打印任务必须按发送顺序打印。用哪种 ADT,为什么?
Order of arrival is the FIFO rule. A stack would print the most recent job first. · 到达顺序就是 FIFO 规则。栈会先打印最近的任务。
ADT versus implementation
- The ADT is the behaviour: push and pop, enqueue and dequeue, insert and traverse.
- The implementation is the storage: in this course, an array plus a few pointer variables (next lesson).
- A question about the ADT wants operations and rules; a question about implementation wants arrays, pointers and the checks.
ADT 与实现
- ADT 是行为:入栈和出栈、入队和出队、插入和遍历。
- 实现是存储:在本课程中,是一个数组加几个指针变量(下一课)。
- 关于 ADT 的题要操作和规则;关于实现的题要数组、指针和检查。
Marks that slip away
- Push and enqueue test for full first; pop and dequeue test for empty first. Write the check into the description.
- Inserting into a linked list: set the new node's pointer before changing the previous node's, or the rest of the list is lost.
- A stack changes at one end, a queue at both. "Remove from the top of the queue" is a stack answer.
- Expand the abbreviations once: LIFO, last in first out; FIFO, first in first out.
容易丢掉的分
- 入栈和入队先测满;出栈和出队先测空。把检查写进描述里。
- 向链表插入:先设新节点的指针,再改前一个节点的,否则列表的其余部分就丢了。
- 栈只在一端变化,队列在两端。"从队列顶部移除"是栈的答案。
- 缩写展开一次:LIFO,后进先出;FIFO,先进先出。
You've got it
- an ADT is a collection of data together with a set of operations on it; behaviour, not storage
- stack: add and remove at the top, LIFO, push and pop · queue: add at the rear, remove at the front, FIFO, enqueue and dequeue
- linked list: nodes of value + pointer from a head pointer; cheap insert and delete, slow random access; traverse by following pointers
- justify by rule: order of arrival → queue; most recent first → stack; frequent insertion in the middle → linked list
你掌握了
- ADT 是一组数据加上对它的一组操作;是行为,不是存储
- 栈:在顶部添加和移除,LIFO,入栈和出栈 · 队列:尾部添加、头部移除,FIFO,入队和出队
- 链表:从头指针出发的值 + 指针节点;插入删除便宜,随机访问慢;沿指针遍历
- 按规则论证:到达顺序 → 队列;最近优先 → 栈;频繁在中间插入 → 链表