Prev Next

Abstract Data Types

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, detailed 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.

Kinds of ADT

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

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 destructive or nondestructive ADT?)

Interface for IntStack 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.

Semantics of IntStack 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.

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 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, under classes.

Destructive ADT example

Here is a full implementation of the IntStack 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
// File: intstack.h
// 
// This file provides for stacks of integers.
// 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 instack.cpp
// File: intstack.cpp

#include "intstack.h"

///////////////////////////////////////////
// A stack is represented as follows.  
// There are three variables, top, size 
// and content.  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;
  }
}


///////////////////////////////////////
// growStack(s) makes the content
// array of s twice as large as it was.
// But do not allocate fewer than 
// four slots to the array.
///////////////////////////////////////

void growStack(IntStack& s)

  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 that is twice 
  // as large, and copy the previous 
  // content into the new array.
  //---------------------------------

  if(s.top == s.size) growStack(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
// 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 is not 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 ADT implementation. Unfortunately, the compiler will allow us to make that error. Using classes, covered later, it is possible to make such an error impossible to make.

Nondestructive ADT example

Here is another example of an abstract data type. This is a nondestructive 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
// File: istack.h
//
// This file provides for stacks of integers 
// in a nondestructive way.

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 s 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
// File: istacktest.cpp

#include <stdio.h>
#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); 
  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;
}

Prev Next