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?

• Thought of or stated without reference to a specific instance
• A statement summarizing the important points of a given text.
• The concentrated essence of a larger whole.

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:

• We want to break down the problem into logical chunks. If we were building a vending machine, we can design the mechanism that counts the change separately from the mechanism that delivers the selected item.
• Each chunk or ADT should have a clear, simple interface. In other words, the user of the ADT should not need to know the underlying details of the ADT. The user of the vending machine needs to know where to put coins, how to select an item, and how to retrieve it.
• We try to pick general abstractions when possible to make ADTs easier to extend and reuse. Suppose we want our vending machine to accept bills? We should not have to change the mechanism that delivers the item, to allow the machine to accept bills.

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.

Interfaces

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

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

• insert coin
• select item
• retrieve item
• retrieve change

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:

• insert an item
• remove an item

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:

• Encapsulation: a class groups the variables and methods that implement an ADT.
• Access control: a class specifies what things inside the class may be accessed from outside. This corresponds to the interface.
• Information hiding: a class prevents access to everything in the class other than the interface, thereby hiding the implementation details of the ADT.
• Instantiation: many objects can be instantiated from a single class. I.e., we can have many queues in the same program.

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:

• When a method returns a queue element, the user must first typecast it to its own type of object. This isn't a serious disadvantage because the user knows what type of objects are being put in the queue.
• The compiler cannot do type checking to ensure that only objects of the correct type are placed on the queue.

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() {}
         }