4 Abstract Data Types (ADTs)

4.1 Introduction to Abstract Data Types

Abstraction is a suppression of detail. You can think of a function as abstracting a task or algorithm. The interface provides only the abstract view, telling what the function accomplishes. The implementation provides the concrete view, showing the details.

Functions abstract computation. But what about the data on which computation is performed? If you have only functions as an abstraction tool, then your data is always concrete. There are good reasons for wanting to abstract away details of the data as well as to abstract details of computation.

  1. What you care about in data is what is stored, not how the data is stored. A programmer does not want to be burdened with unnecessary details.

  2. Often, you find it desirable to change the representation of data. For example, a new, very clever implementation of some of the operations that you need might come along, but it might require that data be stored in a particular way. (Efficient algorithms usually have strict requirements on how data is stored.) You might want to remove a more naive implementation of those operations, and plug in a more efficient one, without disrupting the rest of your program. You can only do that if your program is insensitive to the representation of the data.

You cannot hide the details of the representation from all functions. Some, of course, must deal with the data at a very concrete level. So how can the details be hidden? The answer is that those functions that need to see the details are part of the abstract data type.

An abstract data type is a type together with some functions that work on that type. The representation of the type is visible only to the functions that are part of the abstract data type. When you change the implementation of an abstract data type, you only need to change those functions that are part of the abstract data type.

4.2 Kinds of ADT

There are two major kinds of ADT: persistent and nonpersistent. Nonpersistent ADTs are characterized by functions that change the data that is stored. The functions in a nonpersistent ADT are typically procedures or mixed functions, although some of the functions are usually pure. The functions in a persistent ADT must all be pure. They cannot change anything.

4.3 Interfaces

An interface to an ADT tells a user of the ADT everything that he or she needs to know, and no more. The interface consists of two parts: the signature and the semantics.

Signature. The signature consists of the name of the type and prototypes for the functions that are part of the ADT. For example, here is the signature for an ADT that is a stack of integers. (Is this a persistent or nonpersistent ADT?)
Type:IntStack
Functions:
void push(int x, IntStack& s);
int pop(IntStack& s);
bool isEmpty(const IntStack& s);
void Empty(IntStack& s);

Semantics. The semantics of an ADT gives meanings to the functions. It consists of a description of the data that is represented, and contracts for the functions. Here is the semantics of our integer stack ADT.

An IntStack holds a sequence of integers. The sequence is thought of as being written vertically, and having a bottom and a top. When you create a stack, it is has nothing in it. That is, it is empty.

Empty(s)
removes all integers from s, making s empty.

isEmpty(s)
returns TRUE if s is empty, and FALSE if s is not empty.

Push(x,s)
adds x to the top of stack s.

Pop(s)
removes the top number from stack s, and returns it. If s is empty, then Pop(s) returns 0, and does not modify s.

4.4 Implementation

The implementation of an ADT provides a representation of the type, and implementations of the functions. It is written in the programming language that you are using, such as C/C++.

One way to create an abstract data type is to put the type definition in the header file, along with prototypes for the functions. Doing things this way has a serious defect: it makes the representation of the type available to all functions, and so does not hide it, since that representation is in the header file. Ways to improve this are discussed later.

4.5 Nonpersistent ADT Example

Here is a full implementation of the stack ADT outlined above. In the header file, we put the signature and the type. In the implementation file, we put the implementation, along with documentation of the implementation. This implementation assumes that a function called abort is available to exit the computation at an error. 
                                                             
// File: intstack.h
// 
// This file provides for stacks of integers.

#include "bool.h"

// When you create an IntStack, it is initially empty.

struct IntStack {
  int top, size;
  int* content;
  IntStack()
  {
    top      = 0;
    size     = 0;
    contents = NULL;
  }
};

////////////////////////////////////////////
// Push(x,s) puts x onto the top of stack s.
////////////////////////////////////////////

void Push(int x, IntStack& s);

////////////////////////////////////////////
// Pop(s) removes the top of stack s, and returns it.
// If s is empty, then it returns 0, and does not 
// modifiy s.
////////////////////////////////////////////

int Pop(IntStack& s);

////////////////////////////////////////////
// isEmpty(s) returns TRUE just when s is empty.
////////////////////////////////////////////

bool isEmpty(const IntStack& s);

////////////////////////////////////////////
// Empty(s) makes stack s empty.
////////////////////////////////////////////

void Empty(IntStack& s);

                                               
// File: intstack.cpp
//

#include "intstack.h"

//////////////////////////////////////////////////////////////
// A stack is represented as follows.  There are three fields,
// top, size and content.  Field content points to an array
// of size integers.  top tells how many of those integers are
// actually in the stack, and is one greater than the index
// of the top of the stack.  (So the bottom is at index 0.)
//
// Initially, content is a null pointer, and size is 0.  When
// data is put into the stack, the array is allocated to
// hold the data.  If that array fills up, a new, larger,
// array is allocated.
//////////////////////////////////////////////////////////////


/////////////////////////////////////////////////////
// isEmpty(s) returns TRUE just when stack s is empty.
/////////////////////////////////////////////////////

bool isEmpty(const IntStack& s)
{
  return s.top == 0;
}

/////////////////////////////////////////////////////
// Empty(s) makes stack s empty.
/////////////////////////////////////////////////////

void Empty(IntStack& s)
{
  s.top  = 0;
  s.size = 0;
  if(s.content != NULL) {
    delete[] s.content;
    s.content = NULL;
  }
}

/////////////////////////////////////////////////////
// Pop(s) removes the top integer from stack s, and
// returns it.  If s is empty, then 0 is returned,
// and s is not changed.
/////////////////////////////////////////////////////

int Pop(IntStack& s)
{
  if(s.top > 0) {
    return s.content[--s.top];
  }
  else {
    return 0;
  }
}

/////////////////////////////////////////////////////
// Enlarge(s) allocates a larger array for s, leaving
// the content of stack s unchanged.
/////////////////////////////////////////////////////

void Enlarge(IntStack& s)
{

  //------------------------------------------------------
  // Allocate an array that is twice as large
  // as the current array, and copy the previous content
  // into the new array.  However, make sure that the
  // size is at least 4.  (Doubling 0 yields 0, and we
  // would never create any space if we start with none.)
  //------------------------------------------------------

  int  newsize = 2*s.size;
  if(newsize < 4) newsize = 4;
  int* newcontent = new int[newsize];
  int i;

  if(NULL == newcontent) abort("IntStack overflow");

  for(i = 0; i < s.size; i++) {
    newcontent[i] = s.content[i];
  }
  delete[] s.content;
  s.content = newcontent;
  s.size    = newsize;
}

/////////////////////////////////////////////////////
// Push(x,s) puts x onto the top of stack s.
/////////////////////////////////////////////////////

void Push(int x, IntStack& s)
{
  //------------------------------------------------------
  // If the array is too small, then allocate a new one.
  //------------------------------------------------------

  if(s.top == s.size) Enlarge(s);

  //--------------------
  // Now do the push.
  //--------------------

  s.content[s.top++] = x;
}
To use the IntStack ADT, you would include its header file, and use the type and functions. 
// File: stacktest.cpp

#include <stdio.h>
#include "intstack.h"

int main()
{
  IntStack st;

  Push(2, st);
  Push(3, st);
  int a = Pop(st);
  int b = Pop(st);
  if(isEmpty(st)) {
    printf("I got a = %d, b = %d.\n", a, b);
    printf("Should get a = 3, b = 2.\n");
  }
  else {
    printf("Hey!  The stack should be empty.\n");
    printf("By the way, I got a = %d, b = %d\n", a, b);
  }
  Empty(st);
  return 0;
}
Suppose that function main had attempted to use st.top directly. Doing so would have been a logical error, since data value st.top is part of the representation of stacks, and should not be visible outside the stack ADT implementation. Using s.top directly is called violating the abstraction of the ADT. Unfortunately, the compiler will allow us to make that error. Using classes, covered later, it is possible to prevent a program from violating an abstraction.

4.6. Persistent ADT Example

Here is another example of an abstract data type. This is a persistent stack ADT. Although it provides stacks, it is quite different from the previous ADT. This ADT does not attempt to recover memory, since doing so for this kind of data type is beyond the scope of these notes. 
                                                            
// File: istack.h
//
// This file provides for stacks of integers in a persistent way.

#include "bool.h"

struct IStackNode {
  int data;
  struct IStackNode* next;
}; 

typedef IStackNode* IStack;

struct PopResult {
  int top;
  IStack poppedStack;
}

/////////////////////////////////////////////////////////
// isEmpty(s) returns TRUE just when s is an empty stack.
/////////////////////////////////////////////////////////

bool isEmpty(IStack s);

/////////////////////////////////////////////////////////
// emptyIStack is an empty stack.
/////////////////////////////////////////////////////////

extern const IStack emptyIStack;

/////////////////////////////////////////////////////////
// push(x,s) returns a new stack that results from pushing
// x onto stack s.
/////////////////////////////////////////////////////////

IStack push(int x, IStack s);

/////////////////////////////////////////////////////////
// pop(s) returns a pair holding the top of stack s and
// the result of deleting the top of s.  If s is empty,
// then the data is 0 and the result of deleting the top
// is empty.
/////////////////////////////////////////////////////////

PopResult pop(IStack s);

// File: istack.cpp
//

#include "istack.h"

///////////////////////////////////////////////////
// emptyIStack is an empty IStack.
///////////////////////////////////////////////////

const IStack emptyIStack = NULL;

////////////////////////////////////////////////////
// isEmpty(s) returns TRUE just when stack is is empty.
////////////////////////////////////////////////////

bool isEmpty(IStack s)
{
  return (s == NULL);
}

////////////////////////////////////////////////////
// pop(s) returns the top of s and the result of
// removing the top of s, in a PopResult node.  If
// s is empty, then the result node holds top 0 and
// result of popping = empty.
////////////////////////////////////////////////////

PopResult pop(IStack s)
{
  PopResult result;

  if(isEmpty(Istack)) {
    result.top         = 0;
    result.poppedStack = emptyIStack;
  }
  else {
    result.top         = s->data;
    result.poppedStack = s->next;
  }
  return result;
}

///////////////////////////////////////////////////
// push(x,s) returns the result of pushing x onto
// stack s.
///////////////////////////////////////////////////

IStack push(int x, IStack s)
{
  IStackNode* node = new IStackNode;
  node->data = x;
  node->next = s;
  return node;
}
To use this ADT, you would include its header file, and use its type and functions. You must be sure to use them according to the signature. 
// File: istacktest.cpp

#include 
#include "istack.h"

int main()
{
  IStack st1, st2;
  PopResult pr1, pr2, pr3, pr4;

  st1 = push(2, emptyIStack);
  st2 = push(3, st1);
  pr1 = pop(st1);
  pr2 = pop(st2);
  pr3 = pop(st1);   	     // Must give same result as pr1.
  pr4 = pop(pr2.poppedStack); // Must give same result as pr1.
  if(isEmpty(st1)) {
    printf("Hey!  This stack should not be empty!\n");
  }
  else { 
    printf("I got pr1.top = %d, pr2.top = %d.\n", 
           pr1.top, pr2.top);
    printf("Should get pr1.top = 2, pr2.top = 3.\n");
  }
  return 0;
}