Abstract data types: an operation contract
Введено| English | Значение |
|---|---|
| stack/stæk/ | стек |
| queue/kjuː/ | очередь |
What would explain this observation?
- A waiting-line simulation needs the oldest pending item first. A stack 栈 gives the most recent item first, so the operation contract matters.
Build the model
- 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.
Which structure models an ordinary arrival-order waiting line?
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
A waiting line is first-in-first-out, which is exactly the queue contract: enqueue at the back, dequeue from the front. A stack is last-in-first-out, and a structure without a contract models nothing reliably.
Match each technical term to its precise meaning.
Сложность 2/5 · 140 монет + небольшой бонус за первое выполнение сегодня
Use the definitions to distinguish related quantities and processes.
Choose evidence that can test it
- 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.
Which two habits make the investigation or model in this case more defensible?
Сложность 2/5 · 140 монет + небольшой бонус за первое выполнение сегодня
Stating the conditions and assumptions lets others repeat the work exactly, and recording the supporting evidence lets them check the conclusion. Hiding disagreeing results removes the evidence that could challenge a wrong conclusion, and one measurement can never establish a wider claim.
Work from known quantities
- Known: enqueue A, B and C, then dequeue twice.
- A and B leave; C remains.
- After enqueue D there are two pending items, C then D.
- The same pushes on a stack would remove C then B.
Your turn: A queue starts empty, receives 7 items and removes 4. Find the number remaining.
A queue starts empty, receives 7 items and removes 4. Find the number remaining.
Сложность 2/5 · 140 монет + небольшой бонус за первое выполнение сегодня
The result is 3 items. Known: empty queue; 7 enqueues; 4 dequeues. Remaining = 7 - 4 = 3 items. In arrival order, the three most recent arrivals are still waiting.
Check the conclusion and its limits
- 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.
Every queue automatically sorts items by priority.
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
An ordinary queue releases items strictly in arrival order. Serving by importance is a PRIORITY queue - a different contract that must be stated explicitly.
A last-in-first-out abstract data type: write the technical term.
Сложность 1/5 · 100 монет + небольшой бонус за первое выполнение сегодня
stack means A last-in-first-out abstract data type.