Chapter 11

Abstract Data
Types

ISBN 0-321-49362-1
Chapter 11 Topics

• The Concept of Abstraction

• Introduction to Data Abstraction
• Design Issues for Abstract Data Types
• Language Examples
• Parameterized Abstract Data Types

Copyright © 2009 Addison-Wesley. All rights reserved. 1-2

The Concept of Abstraction

• An abstraction is a view or representation

of an entity that includes only the most
significant attributes
• The concept of abstraction is fundamental
in programming (and computer science)
• Nearly all programming languages
support process abstraction with
subprograms
• Nearly all programming languages
designed since 1980 support data
abstraction
Copyright © 2009 Addison-Wesley. All rights reserved. 1-3
Introduction to Data Abstraction
• An abstract data type is a user-defined
data type that satisfies the following two
conditions:
– The representation of, and operations on,
objects of the type are defined in a single
syntactic unit
– The representation of objects of the type is
hidden from the program units that use
these objects, so the only operations possible
are those provided in the type's definition

Copyright © 2009 Addison-Wesley. All rights reserved. 1-4

Advantages of Data Abstraction

• Advantage of the first condition

– Program organization, modifiability
(everything associated with a data structure
is together), and separate compilation
• Advantage the second condition
– Reliability--by hiding the data
representations, user code cannot directly
access objects of the type or depend on the
representation, allowing the representation
to be changed without affecting user code

Copyright © 2009 Addison-Wesley. All rights reserved. 1-5

Language Requirements for ADTs

• A syntactic unit in which to encapsulate

the type definition
• A method of making type names and
subprogram headers visible to clients,
while hiding actual definitions

Copyright © 2009 Addison-Wesley. All rights reserved. 1-6

Design Issues

• What is the form of the container for the

interface to the type?
• Can abstract types be parameterized?
• What access controls are provided?

Copyright © 2009 Addison-Wesley. All rights reserved. 1-7

Language Examples: C++

• Based on C struct type and Simula 67

classes
• The class is the encapsulation device
• All of the class instances of a class share a
single copy of the member functions
• Each instance of a class has its own copy
of the class data members
• Instances can be static, stack dynamic, or
heap dynamic

Copyright © 2009 Addison-Wesley. All rights reserved. 1-8

Language Examples: C++ (continued)

• Information Hiding
– Private clause for hidden entities
– Public clause for interface entities
– Protected clause for inheritance (Chapter 12)

Copyright © 2009 Addison-Wesley. All rights reserved. 1-9

Language Examples: C++ (continued)

• Constructors:
– Functions to initialize the data members of
instances (they do not create the objects)
– May also allocate storage if part of the
object is heap-dynamic
– Can include parameters to provide
parameterization of the objects
– Implicitly called when an instance is created
– Can be explicitly called
– Name is the same as the class name

Copyright © 2009 Addison-Wesley. All rights reserved. 1-10

Language Examples: C++ (continued)

• Destructors
– Functions to cleanup after an instance is
destroyed; usually just to reclaim heap storage
– Implicitly called when the object’s lifetime
ends
– Can be explicitly called
– Name is the class name, preceded by a tilde
(~)

Copyright © 2009 Addison-Wesley. All rights reserved. 1-11

An Example in C++
class Stack {
private:
int *stackPtr, maxLen, topPtr;
public:
Stack() { // a constructor
stackPtr = new int [100];
maxLen = 99;
topPtr = -1;
};
~Stack () {delete [] stackPtr;};
void push (int num) {…};
void pop () {…};
int top () {…};
int empty () {…};
}
Copyright © 2009 Addison-Wesley. All rights reserved. 1-12
A Stack class header file

// Stack.h - the header file for the Stack class

#include <iostream.h>
class Stack {
private: //** These members are visible only to other
//** members and friends (see Section 11.6.4)
int *stackPtr;
int maxLen;
int topPtr;
public: //** These members are visible to clients
Stack(); //** A constructor
~Stack(); //** A destructor
void push(int);
void pop();
int top();
int empty();
}
Copyright © 2009 Addison-Wesley. All rights reserved. 1-13
The code file for Stack
// Stack.cpp - the implementation file for the Stack class
#include <iostream.h>
#include "Stack.h"
using std::cout;
Stack::Stack() { //** A constructor
stackPtr = new int [100];
maxLen = 99;
topPtr = -1;
}
Stack::~Stack() {delete [] stackPtr;}; //** A destructor
void Stack::push(int number) {
if (topPtr == maxLen)
cerr << "Error in push--stack is full\n";
else stackPtr[++topPtr] = number;
}
...

Copyright © 2009 Addison-Wesley. All rights reserved. 1-14

Language Examples: C++ (continued)

• Friend functions or classes - to provide

access to private members to some
unrelated units or functions
– Necessary in C++

Copyright © 2009 Addison-Wesley. All rights reserved. 1-15

 Language Examples: Java
• Similar to C++, except:
– All user-defined types are classes
– All objects are allocated from the heap and
accessed through reference variables
– Individual entities in classes have access
control modifiers (private or public), rather
than clauses
– Java has a second scoping mechanism,
package scope, which can be used in place
of friends
• All entities in all classes in a package that do
not have access control modifiers are visible
throughout the package

Copyright © 2009 Addison-Wesley. All rights reserved. 1-16

An Example in Java
class StackClass {
private:
private int [] stackRef;
private int [] maxLen, topIndex;
public StackClass() { // a constructor
stackRef = new int [100];
maxLen = 99;
topPtr = -1;
};
public void push (int num) {…};
public void pop () {…};
public int top () {…};
public boolean empty () {…};
}
Copyright © 2009 Addison-Wesley. All rights reserved. 1-17
Parameterized Abstract Data
Types
• Parameterized ADTs allow designing an
ADT that can store any type elements
(among other things) – only an issue for
static typed languages
• Also known as generic classes
• C++, Ada, Java 5.0, and C# 2005 provide
support for parameterized ADTs

Copyright © 2009 Addison-Wesley. All rights reserved. 1-18

 Parameterized ADTs in C++
• Classes can be somewhat generic
by writing parameterized
constructor functions
class Stack {
…
Stack (int size) {
stk_ptr = new int [size];
max_len = size - 1;
top = -1;
};
…
}

Stack stk(100);

Copyright © 2009 Addison-Wesley. All rights reserved. 1-19

Parameterized ADTs in C++
(continued)
• The stack element type can be parameterized by making
the class a templated class
template <class Type>
class Stack {
private:
Type *stackPtr;
const int maxLen;
int topPtr;
public:
Stack() {
stackPtr = new Type[100];
maxLen = 99;
topPtr = -1;
}
…
}

Copyright © 2009 Addison-Wesley. All rights reserved. 1-20

Parameterized Classes in Java 5.0

• Generic parameters must be classes

• Most common generic types are the
collection types, such as LinkedList and
ArrayList
• Eliminate the need to cast objects that are
removed
• Eliminate the problem of having multiple
types in a structure

Copyright © 2009 Addison-Wesley. All rights reserved. 1-21

Summary

• The concept of ADTs and their use in program

design was a milestone in the development of
languages
• Two primary features of ADTs are the packaging
of data with their associated operations and
information hiding
• C++ data abstraction is provided by classes
• Java’s data abstraction is similar to C++
• Ada, C++, Java 5.0, and C# 2005 support
parameterized ADTs

Copyright © 2009 Addison-Wesley. All rights reserved. 1-22