After this page, you should be able to:
Distinguish an ADT’s promises from its representation and implementation.
Read a small operation contract, including its empty-state behaviour.
Builds on: Collections and classes introduces objects, methods and valid states.
Three related questions¶
An abstract data type (ADT) describes the values being managed, the available operations and their required behaviour. It lets us reason about what a collection promises before choosing how to store it.
| Concept | Question | Stack example |
|---|---|---|
| ADT | What behaviour must operations provide? | Push adds an item; pop removes the most recently pushed item still present |
| Data structure | How are the data and relationships organised? | A dynamic array, or linked nodes with a reference to the top |
| Implementation | How do code and algorithms realise that organisation? | A class using a Python list, or a class updating node references |
A class can implement an ADT, but its method names alone do not establish the required behaviour. A queue also adds and removes items, yet removes the earliest waiting item instead of the newest one.
The same stack behaviour with different storage¶
Imagine recording shuttle-stop codes so the latest addition can be undone first. This is last in, first out (LIFO). Read the following states from bottom to top:
| Operation, starting empty | Returned result | Stack afterwards |
|---|---|---|
push("KR") | None | KR |
push("MUS") | None | KR, MUS |
push("UTN") | None | KR, MUS, UTN |
pop() | "UTN" | KR, MUS |
peek() | "MUS" | KR, MUS |
Both an array-backed stack and a linked-node stack should produce these results under the same contract. peek() observes the top; pop() also removes it. The client can use these operations without inspecting an array index or a node link.
The costs and memory layout can differ. An array may occasionally grow and copy references; a linked implementation allocates nodes and stores links. Matching behaviour does not imply identical efficiency. We will develop the implementations and their costs in Topic 5.
State the exceptional cases, too¶
An operation contract specifies valid requests, returned results and changes to the logical state. For this example, push returns None; successful pop removes and returns exactly the top item. Both empty pop and empty peek raise IndexError, leaving the stack empty. Other interfaces can choose another policy, but must state it clearly.
These promises describe externally observable behaviour. Internal details can change as long as supported operations continue to satisfy the contract. This separation will help us compare several implementations of the same ADT throughout the book.
Read a contract without exposing the storage¶
For each supported operation, ask what inputs are valid, what it returns, what logical state changes, and what happens at boundaries or on failure. An observer such as peek leaves the logical stack unchanged; a mutator such as pop changes it. Internal bookkeeping can change without changing the abstract value, provided the promised behaviour remains the same.
| Question | Stack contract here | A different requirement |
|---|---|---|
| Which waiting item is selected? | Most recently pushed | A queue selects the earliest waiting item |
| Does observation remove it? | No; use peek | pop removes and returns it |
| Can equal values appear twice? | Yes; each push adds one entry | A set keeps distinct values |
| What happens when empty? | peek and pop raise IndexError | Another API may choose a different stated policy |
The trace does not require the client to know an array capacity or node address. Repeated equal values are still separate stack entries. An empty error is distinguishable from a stored None: None can be a legitimate item, while empty pop raises an exception.
Implementation choices and the later reading route¶
Two implementations can satisfy the same functional contract while differing in allocation, layout, per-operation costs and worst-case guarantees. A dynamic array and linked stack therefore need both a behavioural comparison and an implementation-specific cost analysis. Those details belong with stacks, not in this brief introduction.
The rest of the book applies this distinction to sequences
Check your understanding¶
Predict the result or draw the references before opening the explanation.
1. Two classes both offer push and pop, but one removes the oldest waiting entry. Are both stacks under this contract?
Show explanation
No. The oldest-entry policy violates LIFO. It is queue-like behaviour even if its methods use stack names.
2. Starting empty, push(None) then pop(). Is the returned None proof that pop failed?
Show explanation
No. It successfully removes the stored None item. Calling pop again on the now-empty stack raises IndexError, so failure is not encoded by that payload value.
For detailed contracts, observers and mutators, and implementation comparisons, continue later with ADTs and contracts. Next in the main reading route: Analysing algorithms.
Browse: Foundations · Concept index