Abstract data types and encapsulation
The abstract data type: its operations and their properties, interface versus implementation, constructors, accessors and modifiers, the invariant, and what encapsulation protects.
- 25 cards
- 3 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
A few cards from the deck
Abstract data type: what is it?
Show the answer
A description of data by its operations and the properties they obey, without saying how the data is represented in memory.
For a stack, we say the top after
push(p, x)isx; we do not say whether an array or a linked list sits behind it.A stack obeys these properties:
top(push(p, x))isxandpop(push(p, x))isp. What istop(pop(push(push(create(), 3), 8)))?- 3
- 8
- The stack holding only 3
- An error: the stack is empty
Show the answer
3
Read from the inside:
create()is empty, then 3, then 8 on top.popremoves the 8 and gives back the stack[3];topreturns its item, 3, not the stack. No representation was needed: only the properties matter.Client code should depend only on a type's …, never on its ….
Show the answer
Client code should depend only on a type's interface, never on its implementation.
That way the representation can change without any caller being rewritten.
Interface of a type: what is it?
Show the answer
The set of operations a user of the type is allowed to call, with their parameters and results.
It is the contract: as long as it does not change, the code that uses it keeps working, whatever is changed behind it.
A queue obeys:
head(enqueue(create(), x))isx, and dequeue removes the oldest. What ishead(dequeue(enqueue(enqueue(create(), 5), 9)))?- 5
- 9
- The queue holding only 9
- An error: the queue is empty
Show the answer
9
The queue holds 5 then 9.
dequeueremoves the oldest, 5, leaving 9 at the head. With a stack, the same sequence would have given 5.