Intermediate Business Programming with C++

Introduction to Abstract Data Types (ADTs)

This lecture covers an introduction to a construct called: Abstract Data Types (or ADTs). What will be done is to build these ADTs with C++ classes. However what should be observed is that in general ADTs could be encountered in any language. The purpose of this lecture is not to just study the C++ implementations of these ADTs but in addition to study the constructs themselves. In this case, should it be necessary to use these ADTs in another language like Java or C#, all that would need to be done is to implement their concepts into the syntax of that language.

There are several useful ADTs but as an introduction to this subject only the following will be considered in this lecture:

• Stacks

• Queues

• Lists

In some respects each of these constructs are special types of lists but they will be considered independently.

The first thing to be considered is what is meant by saying that these constructs are ADTs? By an Abstract Data Type is meant that it contains three things:

• a name

• a set of attributes

• a set of properties on this attributes.

Does this sound like a C++ class is an example of an ADT? It is but this lecture will add a few additional properties to distinguish ADTs from classes in general. That is stacks, queues and lists will be implemented using classes but they each have some additional properties as will be discussed in the remaining sections.