We motivated the introduction of Objects using the ADT. An Abstract Data Type, or ADT, is a collection of operations. There really isn't any data at all, none that the definition of an ADT should care about: only the suite of operations matter. How exactly the manipulations are carried out, the representation of the data in the computer's memory, are hidden behind the ADT's interface. The interface is the formal statement of the ADT's suite of operations.
The Stack ADT most notable operations are Push and Pop. The Stacks we are considering are stacks of strings, char *. At any moment in time, the Stack is a collection of previously pushed strings. A Push of a string s on the Stack updates to collection to contain s. (Two pushes of the same string are considered distinguishable, the string is in the stack twice.) A Pop on the Stack removes from the the most recently Pushed string. For this reason, Stacks are also called LIFO: Last In First Out.
We now describe the Object-paradigm to implement the Stack ADT.
A Stack class is defined, which models the Stack ADT, and the public methods are the ADT operations. The C++ syntax is as follows:
class Stack {
private:
// to be defined later
public:
Stack() ;
boolean isEmpty() ;
void push(char *) ;
char * pop() ;
} ;
The methods isEmpty, push and pop will be defined later on.
Their inclusion in the public area of the class definition indicates:
By birth, since they all follow the same blue-print, each instance of a class starts as an identical clone. But each is capable of having a separate destiny. Variables defined in a class are separate for each creaed instance. Our push and pop methods act on this instance-specific variables to modify the objects according to their own individual history. To create a class instance, the new statement, followed by the class name, is used:
Stack * myStack = new Stack ;This statement:
What does the constructor need to do? That depends on the details of the ADT implementation. We will use a linked-list of Nodes. We will implement push by adding a new Node to the head of the list, and pop by removing the head Node of the list. The Stack will save a pointer to this list in a private variable. Here's the code:
struct Node {
char * content ;
Node * next ;
}
class Stack {
private:
Node * root ;
public:
Stack() ;
boolean isEmpty() ;
void push(char *) ;
char * pop() ;
} ;
Stack::Stack() {
root = NULL ;
}
A Stack is created empty, which is signaled by a NULL value for the
variable root.
The implementation of the constructor Stack (Stack::Stack, the ::
will be explained shortly) takes care of that initialization.
The methods, including the constructor, are considered to be inside the class. This means that they are in class scope. Any variables or functions defined in the class are available to the method, as if the method body were written in between the class' curly braces. But the method is not really written inside the class's curly braces, so the compiler must be reminded of the scope which the Stack function is to be interpreted. That is the notation Stack::Stack. The first Stack recalls the Stack class as the scope in which the function is interpreted, and the second Stack is the function name.
All of our method functions will be defined using the notation Stack::xxx, where xxx is the method name. In the case of Stack::Stack, this means that the variable root in the Stack function body is the variable of the same name inside the class definition.
The completed code for this Stack ADT is found in StackADT.C. Another example implements a Queue ADT. A Queue ADT has notable two operations: insert and remove. Remove removes the oldest inserted item. A queue is for this reason also called a FIFO: First In First Out. The queue is implemented using a linked-list, with two pointers: to the head and to the tail of the list. Items are added to the tail and removed from the head. Also, a running count of the number of items is constantly updated. The completed code can be found in QueueADT.C.