Abstract data types: an operation contract
| English | 中文 | Pinyin |
|---|---|---|
| stack/stæk/ | 栈 | zhàn |
| queue/kjuː/ | 队列 | duì liè |
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.
- Start with a prediction. State the quantities or features you would compare, then decide what evidence could distinguish two explanations.
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?
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.
Match each technical term to its precise meaning.
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.
- 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?
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.
Work from known quantities
- State the known values and their units. Choose the relation because its assumptions fit this case, then rearrange before substitution.
- 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.
A queue starts empty, receives 7 items and removes 4. Find the number remaining. Use the same sequence: known quantities → model → relation → substitution → unit and interpretation.
A queue starts empty, receives 7 items and removes 4. Find the number remaining.
The result is 3 items. 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.
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.
- Return to the original observation. Explain what the result supports, which conditions it assumes, and one way to test a competing explanation.
Every queue automatically sorts items by priority. This claim is false: An ADT is not a specific memory layout. A queue does not sort by priority unless its contract defines a priority queue.
Abstract data types: an operation contract: 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.
Every queue automatically sorts items by priority.
An ADT is not a specific memory layout. A queue does not sort by priority unless its contract defines a priority queue.
A last-in-first-out abstract data type: write the technical term.
stack means A last-in-first-out abstract data type.