Suppose tasks arrive as A, B, C and D. Which should leave next: A, D, or an item at a specified position? Choose that behaviour before selecting storage.
Reading route¶
ADTs and contracts: operations, returned results and rejected requests.
Sequences: get, set, insert, append and remove by position.
Stacks: push, peek and pop at the newest end.
Queues: enqueue, front and dequeue in arrival order.
Deques: add, inspect and remove at either end.
Arrays: indexed slots, replacement, shifting and locality.
Dynamic arrays: length/capacity, growth and amortised costs.
Linked structures: traversal, known-node edits and safe reference updates.
Circular-array queues: fixed capacity, wraparound and full-state rejection.
Linked queues: head/tail/size invariants and empty transitions.
Choosing an ADT and representation: compare the same operations under stated assumptions.
Each ADT reading follows purpose → operation contracts → representation and invariant → trace → implementation → implementation choices and correctness → time/space costs → suitability → self-checks. Implementation readings connect those contracts to storage mechanics rather than inventing a new ADT. Every reading starts with goals and prerequisites and ends with two open prediction checks.
Common operation families¶
| Family | What the client must know |
|---|---|
| Insert/add | Where the record goes; additions here return None |
| Inspect | Which record is returned without changing the collection |
| Remove/extract | Which record disappears; these removal methods also return it |
| Replace | Sequence set changes an existing record without changing length |
| Size/empty | size() and len agree; is_empty() tests whether that count is zero |
Empty endpoint access raises IndexError. The sequence page specifies valid indices; the fixed circular queue specifies full-state rejection. Duplicate values and None remain legitimate records. Optional search, iteration and arbitrary-value deletion need separate contracts; we do not add them indiscriminately to endpoint ADTs.
Compare implementations without changing the promise¶
| Contract | Main code here | Alternatives explained |
|---|---|---|
| Sequence | Strict-index Python-list wrapper | Array shifts, dynamic growth, linked positional access |
| Stack | Python list with top at the back | Linked head as top |
| Queue | Restricted library-deque adapter, fixed circular queue, linked head/tail queue | List front removal and its shifting cost |
| Deque | Library-deque adapter with explicit first/last names | Circular buffers and doubly linked endpoints |
The wrappers are complete implementations of their stated interfaces; they delegate underlying library storage management. Linked known-node updates are low-level examples, not a complete positional linked-list class. We do not supply a second full deque allocator. All code uses ordinary Python and the standard library, with no notebook or additional package.
Review Topic 1’s ADT introduction, objects and references, classes and invariants and algorithm analysis. Later topics develop maps, sets and priority queues as separate ADT families.
Start with contracts, or use the concept index for an individual operation.
Code listings offer Python, JavaScript and Julia tabs where a runnable example is present. Python remains the explanation and trace language; see the language guide for native conventions and runnable topic downloads.