Abstract Data Types

The ability to define abstractions is an important skill for programmers. Many students have difficulty understanding exactly what is meant by abstraction and how it applies to programming.

We use abstractions all the time. When we get in the car, we turn the key in the ignition and the car starts. We shift into gear and drive. We don't need to know anything about what actually happens when we turn the key to be able to drive the car.

When we use a vending machine, we insert coins into a slot, push a button, and reach into a window to take the item we selected. We don't know how the vending machine calculates that we've given it the correct change, or how pressing a button causes an item to be made available to us.

Both the user of the car and the user of the vending machine need to know very little about how the car or vending machine work. Details of the inner workings are hidden from the user. Also, the machines themselves are broken into modules. For example, the vending machine has a mechanism that counts the money that has been inserted and communicates with the item selection mechanism when enough coins have been inserted to pay for an item.

Abstract data types serve the same function in programs: they hide unnecessary details from the user (called information hiding), and they allow the program designer to break up the problem into smaller more manageable pieces. [Should get in the idea of reuse.]

Main ideas behind abstract data types are information hiding, modularity, generality, and reuse.

What does abstract mean?

Webster's gives the following definitions of abstract that are useful for our purposes:

Okay, but what does it really mean?

When we use the ideas of abstraction to design programs using abstract data types we have some specific things in mind:

A programming example --- Queues

The vending machine analogy is a good one because it is easy to see exactly what the user of the vending machine needs to know about it. It's hard to translate the vending machine example into a programming example, so we will use an abstract data type that appears in many different kinds of programs, namely a queue.

We are all too familiar with standing in lines. We stand in line to buy tickets to a movie, we stand in line to buy groceries. The properties of a lineup or queue are simple: a person (or object) enters the queue from the back, and leaves the queue from the front.

Queues exist in many places in a computer system too. When you submit a job to a printer, it is put in a queue until all the jobs that were submitted before yours have been printed. When messages are sent on the network, they first go into a queue to wait until the network is able to send the message.


The interface to an ADT tells the user how to use the ADT.

The interface to a vending machine can be defined as follows:

The interface says what the allowed operations are. Note that the interface says nothing about how the operations are implemented.

The interface for a Queue ADT are even simpler:

Using a class to implement an ADT

Classes and other object-oriented programming language features help the programmer implement abstract data types. Classes have several features that fit nicely with the properties of ADTs:

How to implement an ADT in Java

We will use the queue ADT as an example of how to implement an ADT.

Step 1: Designing the Interface

The first thing we need to do is to determine what operations the user will use to interact with the ADT. We have already described the two main operations on the queue: insert and remove. Another operation that is part of a queue ADT is to determine if the queue is empty. We will call this method isEmpty.

What access control should be given to these three methods?

Next we need to decide what the parameters of insert, delete, and isEmpty should be. But this brings up another question. What type of object should the queue hold?

We have two options at this point. The first option is to decide what we want to store in the queue (e.g., integers, Strings, person objects) and declare queue items to be that type. The second option is to declare queue items to be of type Object.

If the queue holds items of type Object, any type of object may be stored in the queue. This makes the queue ADT more useful because is can be used in many different kinds of programs.

This approach has two disadvantages, however:

Back to the question of what the parameters and return values of the three methods of the interface should be.

Choose the method signature that best fits the requirements for insert.

Choose the methd signature that best fits the requirements for remove.

Choose the methd signature that best fits the requirements for isEmpty.

With all this information we have a complete interface for a queue ADT. All we need to do is express it in Java. Note that the class constructor is also part of the interface.

         public class Queue {
            public Queue() {}  
            public void insert(Object item) {}
            public Ojbect remove() {}
            public boolean isEmpty() {}