Handout 4 -ADT's and Stacks*

---

Abstract Data Types

Group the data and allowable operations into one logical unit. An abstract data type is defined by the type of data to be stored (but not how it may be stored, i.e. no implementation of the storage) and the operations that will be allowed on the data. Again, the operations are defined, but not implemented. Another word for this bundling is encapsulation. Data and operations are combined in the same "capsule".

concepts:

• abstraction
  Hiding details of implementation (both for the data storage and algorithms for the operations) from the user. The only thing the user needs to know is the interface.
• interface
  The way in which the user is allowed access to the operations and data. User needs only to know how the operations may be used; he/she doesn't have to worry about implementation details.
• data type
  By encapsulating data and allowed operations, we can create our own data types having the same status as the built-in data types such as int.

Sample ADT

We wish to define a Matrix data type that stores our 2-dimensional arrays and performs the usual arithmetic operations on them. Here is the ADT definition:

Matrix ADT:

  data: 
    the size of the matrix (number of rows and columns)
    a 2-d array of entries (say of floats)

  operations:
    arithmetic operations * + - (binary subtraction)
                          - (unary minus)
    transpose
    inverse

  definition of operations:
    * (multiplication): 
      if C = A*B, then:
      
      A.cols = B.rows = N;

      C[i][k] = A[i][1]*b[1][k] + A[i][2]*B[2][k] + ...
                                + A[i][N]*B[N][k].

    + (addition):
      if C = A+B then:

      A.cols = B.cols; A.rows = B.rows;

      C[i][k] = A[i][k] + B[i][k]

    - (subtraction): defined similarly

    - (unary minus): negate all entries

    transpose:

    Transpose(A).rows = A.cols;
    Transpose(A).cols = A.rows;

    Transpose(A)[i][j] = A[j][i];

    inverse (for 2x2 only!!):

    define det(A) = A[0][0]*A[1][1] - A[0][1]*A[1][0]

    Inv(A)[0][0] = A[1][1]/det(A);
    Inv(A)[0][1] = -A[1][0]/det(A);
    Inv(A)[1][0] = -A[0][1]/det(A);
    Inv(A)[1][1] = A[0][0]/det(A);

Notice no mention is made here of implementation.We have not specified how the data is to be stored (only that it is conceptualized as a 2-dimensional array), nor have I said how to implement the operations: which algorithms to use. This is an "abstract" definition of the data and operations.

C++ Classes

C++ classes are a way to implement ADTs. A class is similar to a struct in C (or C++) with some important differences:

1. The class has private members that are accessible only to other member functions or friend functions or classes. The compiler will return an error if you try to directly access a private class member from outside the class.
2. It also has public members which may be used by anyone.
3. Class members include both data objects and functions.
4. In a C++ class, no typedef is needed. The tag word automatically becomes the name for a user-defined data type.

Thus, the class enforces abstraction by having private members that can be accessed only by other (public) member functions. And it enforces encapsulation by including both data and functions in the class declaration.

Sample C++ Class

Here is a class declaration of the Matrix ADT. For simplicity, not all of the operations are included.

class Matrix
{
   private:  // data members
     int rows, cols;   // dimensions of matrix
     double *m;        // pointer to array

   public:  // member functions and friends
     // CONSTRUCTORS
     // constructor: this one takes size parameters,
     Matrix( int r = 0, int c = 0 );

     // copy constructor: takes another Matrix as parameter
     Matrix( Matrix & );

     // DESTRUCTOR
     // destructor: free the memory, assign pointer to NULL
     ~Matrix() { delete [] m; m = NULL; }

     // overloaded assignment operator
     const Matrix & operator = ( const Matrix &M );

     // FRIENDS (non-member functions with access to private
     // data members)...
     // overloaded output operator
        friend ostream & operator << ( ostream & os, const Matrix &M );

     // arithmetic operators...
     // overloaded multiplication operator
     friend const Matrix operator * ( const Matrix &M1, const Matrix &M2 );
     // overloaded addition operator
     friend const Matrix operator + ( const Matrix &M1, const Matrix &M2 );
};

Points to note:

1. The class definition generally contains only prototypes of its member functions. Exceptions: when the code is 1 or 2 lines, as in the destructor.
2. An important group of member functions (not explicitly mentioned when the ADT was defined) is the set of constructors and the destructor.
3. Constructors
   1. constructors initialize data members of a variable of the class type. The first constructor in this example does that: it initializes the members rows cols and it also allocates an array large enough to hold them (allocates memory for the pointer m).
   2. There is also a second constructor, a deep copy constructor. This will be explained later. Notice however that the function name is the same.
   3. All constructors of a class have the same name as the class. Where these two functions differ is in their signatures, the list of parameters that they take.
4. Name overloading
   C++ allows you to have two functions with the same name. The compiler tells the difference between them by looking at their different signatures.
5. Destructors
   Destructors always have the same name as the class, with a tilde ~ prepended (to signify "negating" the class variable). C++ always supplies default destructors, which are called when a variable goes out of scope. This one, however, does more: it frees the memory allocated to the array. A default destructor would not do that.
6. Overloaded operators
   Many of the member functions are actually overloaded operators. This means they use the same symbol as a built-in operator (for example * = + - and will have the same operator precedence in an expression. But you can define them to do whatever you want.
7. Members and friends
   Two kinds of functions or operators are allowed to access the class data: member functions and friends. It is not always clear cut which way you should declare a function (as a friend or member). But here are some rules and guidelines:
   1. The overloaded assignment operator is always a member. The compiler will reject your code if you not.
   2. Often, functions should be declared as members if possible. However, this can sometimes lead to some awkwardness in their use, and may not allow for the full functionality that you want. An example is the output operator <<. When declared as a friend of the Matrix class, it can be used in the usual way:

      cout << A;
      

      If it were declared as a member, then you would have to write:

      A << cout;
      

      to get the same result. This would be confusing, to say the least! This will be explained in more detail later.

Stack ADT

Data

• A set of elements a1, a2, ..., aN.

Operations

Insertion and deletion, both at one end of the list (called the top).

• Push(X)
  Insert element with value X at top of stack.
• Pop()
  Remove top element of stack

Stacks follow LIFO order: last in, first out.

Array Implementation

Data implementation:

• The set of data elements is stored in an array.
• A variable top returns the array index of the element at top of stack. When stack is empty, set top = -1.
• Since the array size is finite, also need to know Max_Size.

Implementation of operations:

• Push(X)
  1. Check if top == Max_Size. If yes, return. Else:
  2. Array[++top] = X
• Pop()
  1. Check if top == -1. If yes, return. Else:
  2. X = Array[top--]
  3. return X

Both operations take O(1) time, obviously.