IMPLEMENTING ADTS IN THE BASE LANGUAGE.
1. Simple ADTs
Many programming languages already define some simple ADTs as integral parts of the language. For example, the C language defines a simple ADT as an integer. The type of this ADT is an integer with predefined ranges. C also defines several operations that can be applied to this data type (addition, subtraction, multiplication, division and so on). C explicitly defines these operations on integers and what we expect as the results. A programmer who writes a C program to add two integers should know about the integer ADT and the operations that can be applied to it.
2. Complex ADTs
Although several simple ADTs, such as integer, real, character, pointer and so on, have been implemented and are available for use in most languages, many useful complex ADTs are not. As we will see in this chapter, we need a list ADT, a stack ADT, a queue ADT and so on. To be efficient, these ADTs should be created and stored in the library of the computer to be used.
Model for an abstract data type
The ADT model is shown in Figure 12.1. Inside the ADT are two different parts of the model: data structure and operations (public and private).
Computer languages do not provide complex ADT packages. To create a complex ADT, it is first implemented and kept in a library. The main purpose of this chapter is to introduce some common user-defined ADTs and their applications. However, we also give a brief discussion of each ADT implementation for the interested reader. We offer the pseudocode algorithms of the implementations as challenging exercises.
A stack is a restricted linear list in which all additions and deletions are made at one end, the top. If we insert a series of data items into a stack and then remove them, the order of the data is reversed. This reversing attribute is why stacks are known as last in, first out (LIFO) data structures.
Operations on stacks
The pop operation deletes the item at the top of the stack. The following shows the format.
The empty operation
The empty operation checks the status of the stack. The following shows the format