추상 데이터 타입 (HL 전용)
국제바칼로레이트 · IB Diploma · Computer Science · HL 주제 8 3:41 영어 내레이션 · 영어 + 중국어 자막 burned-in
장
전사본
A waiting-line simulation needs the oldest pending item first.
排队模拟需要最先处理最旧的待处理项。
A stack 栈 gives the most recent item first, so the operation contract matters.
栈则优先处理最新项，因此操作契约至关重要。
An abstract data type specifies values and operations independently of a particular implementation.
抽象数据类型独立于具体实现来定义值和操作。
A stack is last in, first out; a queue is first in, first out.
栈是后进先出；队列是先进先出。
A collection interface needs defined behaviour for empty and invalid operations.
集合接口需要对空操作和无效操作定义明确的行为。
Stack: A last-in-first-out abstract data type.
栈：一种后进先出的抽象数据类型。
Queue: A first-in-first-out abstract data type.
队列：一种先进先出的抽象数据类型。
Choose the structure for the required access pattern.
根据所需的访问模式选择数据结构。
Complexity depends on implementation and assumptions: removing the first item from a shifting array differs from advancing a head pointer in a queue.
复杂度取决于实现方式和假设条件：从移动数组中移除第一项与在队列中推进头指针是不同的。
In the lab: Trace operation sequences by hand, then compare a program with the expected states.
在实验室中，手工追踪操作序列，然后将程序与预期状态进行比较。
Test empty, singleton and repeated operations.
测试空、单元素和重复操作。
State overflow behaviour if capacity is fixed.
说明当容量固定时的溢出行为。
Known: enqueue A, B, and C, then dequeue twice.
已知：入队A、B和C，然后出队两次。
A and B leave; C remains.
A和B离开；C留下。
After enqueue D, there are two pending items, C then D.
入队D之后，有两个待处理项，顺序为C然后D。
The same pushes on a stack would remove C then B.
同样的压栈操作会移除C然后B。
Your turn: A queue starts empty, receives 7 items and removes 4.
轮到你了。 一个队列初始为空，接收7个元素后移除4个。
Find the number remaining.
求剩余的元素数量。
An ADT is not a specific memory layout.
抽象数据类型并非特定的内存布局。
A queue does not sort by priority unless its contract defines a priority queue.
队列不会按优先级排序，除非其规范定义了优先队列。
Not true: Every queue automatically sorts items by priority.
并非如此。 并非所有队列都会自动按优先级对项进行排序。
An ordinary queue releases items strictly in arrival order.
普通队列严格按照到达顺序释放项。
Serving by importance is a PRIORITY queue - a different contract that must be stated explicitly.
按重要性服务的是优先队列，这是一种不同的契约，必须明确说明。
An abstract data type specifies values and operations independently of a particular implementation.
抽象数据类型独立于特定实现来指定值和操作。
Choose the structure for the required access pattern.
根据所需的访问模式选择结构。
Watch for: an ADT is not a specific memory layout.
注意：ADT 不是特定的内存布局。
In the queue, A and B leave from the front in arrival order, so C is next, then D.
在队列中，A 和 B 按到达顺序从队首离开，所以下一个是 C，然后是 D。
In the stack, the last item pushed is the first popped, so C leaves first, then B, and only A remains.
在栈中，最后压入的项最先弹出，所以 C 先离开，然后是 B，只剩下 A。
Start empty.
初始为空。
Enqueue A,B; dequeue; enqueue C; dequeue.
入队A，B。 出队。
Give removals and final queue.
入队C。 出队。
Compare the same operations as pushes and pops on a stack.
给出移除元素和最终队列。 将同样的操作与栈上的压入和弹出进行比较。
Queue removes A then B; C remains.
队列移除A然后B；C保留。
Stack removes B then C; A remains.
栈移除B然后C；A保留。
An empty removal needs a defined exception or result, not invented data.
空操作需要一个定义的异常或结果，而不是虚构的数据。
Removing from the left implements FIFO.
从左侧移除实现先进先出。
The explicit empty guard defines the boundary result; deque.popleft without it would raise IndexError.
显式的空值检查定义了边界情况的结果；若使用 deque.popleft 而不加此检查，则会引发 IndexError。
A stack instead removes from the right.
而栈则是从右侧移除元素。
Retrieve the technical meanings, then vary one input in the original transfer and justify the model condition.
回顾相关技术术语，然后在原始迁移中改变一个输入变量，并论证模型条件的合理性。