OO Encapsulation  «Prev  Next»
Lesson 10 The ADT's interface
Objective Understand what belongs in an ADT's interface.

(ADT) Abstract Data Type

Interfaces of the Abstract Data Type

Black Box
The struct ch_stack has a private part that contains its data description, and a public part that contains member functions to implement ch_stack operations. It is useful to think of the private part as restricted to the implementor's use, and the public part as a specification that clients may use.
These public members are also called the type's interface.
The implementor could change the private part without affecting the correctness of a client's use of the ch_stack type.
Here is an example of how we might test ch_stack's operations. An abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects of those operations.

For example, an abstract stack could be defined by three operations:
  1. push, that inserts some data item onto the structure,
  2. pop, that extracts an item from it (with the constraint that each pop always returns the most recently pushed item that has not been popped yet), and
  3. peek, that allows data on top of the structure to be examined without removal.
When analyzing the efficiency of algorithms that use stacks, one may also specify that all operations take the same time no matter how many items have been pushed into the stack.
In addition, the stack uses a constant amount of storage for each element.
Abstract data types are purely theoretical entities, used (among other things) to simplify the description of abstract algorithms, to classify and evaluate data structures, and to formally describe the type systems of programming languages.
However, an ADT may be implemented by specific data types or data structures. ADTs are often implemented as modules: the module's interface declares procedures that correspond to the ADT operations, sometimes with comments that describe the constraints.
This information hiding strategy allows the implementation of the module to be changed without disturbing the client programs.
The term abstract data type can also be regarded as a generalized approach to a number of algebraic structures, such as lattices, groups, and rings. This can be treated as part of the subject area of artificial intelligence. The notion of abstract data types is related to the concept of data abstraction, which is important in object-oriented programming and design.

The C++ Programming Language