Abstract Data Types
Definition
An ADT is a "logical expression" (i.e specification) of a structure which is well-defined and has a widely recognized behaviour.
Data structures are implementations of ADTs.
Info
ADTs contain data that may only be accessed in a prescribed manner, defined by a set of operations. Each operation has:
- A signature which defines its parameters and return value
- A pre-condition (logic statement) which specifies what is assumed to be true before the operation may be applied
- A post-condition (logic statement) which describes the value/effect of the operation
Though an ADT has a spec, implementations may be different. As long as the abstracted operations perform the same way, it doesn't matter.
Examples
- Vector/list
- Stack
- Queue
- Set
- Dictionary/map
All these are ADTs. Consider a stack. We may push to
Pre and Post Conditions
- Pre-condition
- Is there anything we assume about the parameters and state of the ADT before using this operation?
- E.g does the input need to be sorted? Non-empty?
- Pre-conditions should be as logically weak as possible
- Is there anything we assume about the parameters and state of the ADT before using this operation?
- Post-condition
- Is there a relationship between the input params and the eventual return value and state of the ADT?
- Post-conditions should be as logically strong as possible
- Is there a relationship between the input params and the eventual return value and state of the ADT?