Abstract Data Types

An abstract data type (ADT) is a name (the type-name) and a list of the actions that can be performed on it.

For example, consider the INTEGER_STACK ADT. The actions on it are:

• PUSH(INTEGER): add an integer to the top of the stack.
• INTEGER ::= TOP(): returns the integer from the top of the stack.
• POP(): remove an integer from the top of the stack.
• IS_EMPTY(): check to see if the stack is empty.

In C, the ADT type-name is defined using typedef. The actions are implemented as functions. The actions and the type-name are grouped together in a single .h header file.

	/* integer stack ADT */
	typedef struct int_stack * int_stack;

	int_stack make_int_stack(void);
	void      destroy_int_stack(int_stack);
	void      push_int_stack(int_stack, int);
	int       top_int_stack(const int_stack);
	void      pop_int_stack(int_stack);
	int       is_empty_int_stack(const int_stack);

We are assuming that this ADT (and, in general all ADTs) will be heap allocated. Therefore, in C:

• The type of the ADT (int_stack) will be a pointer to some structure.
• There will always be functions to make and destroy the ADT. By convention, I always prefix these with make_ and destroy_; that way I know that:
  • If I see a make_T(), I know it returns an instance of ADT T.
  • If I see a destroy_T(), I know it is destroying an instance of T.
  • If I want to make/destroy an instance of type T, chances are that the functions I want to use are make_T() and destroy_T().

We have also used some other conventions.

• The type-name of the ADT will be part of the name of all functions that are part of the ADT (eg. top_int_stack). Using the type-name as part of the function name has two benefits:
  • It lets us avoid collisions between functions in different ADTs. For instance, a large project might have many different kinds of collections, many of which will have a LENGTH action. People would go off and develop their piece of code, each using length(). At some point they would try to integrate. The length() functions would be multiply defined and the integration would fail until the names were changed.
  • It lets someone who comes in later to maintain the code know exactly what kind of object is being operated on; if they see the call length_T_list(names), they immediately knows what is happening, even without knowing the type of names.
• The ADT will be the first argument to the ADT functions (wherever it makes sense). This convention, like many others, is to benefit the user of the ADT, and a later maintainer. If he/she sees push_int_stack(vals, sums), he/she knows that it is sums that is being pushed onto vals, and not the other way around.

That is all that belongs in the header file; in particular there are no implementation details.