ABSTRACT DATA TYPES

The concept of abstraction , abstraction is a viow or representation of an entity that includes only the most significant attributes. The concept is fundamental in programing. Almost all programming language support process abstraction with subprogram and support data abstraction.

Introduction to data abstraction , abstract data type is a user-defined data type that statisfies  this condition:

• 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
• The declarations of the type and the protocols of the operations on objects of the type are contained in a single syntactic unit. Other program units are allowed to create variables of the defined type.

Language examples C++ ,

• Based on C struct type and Simula 67 classes
• The class is the encapsulation device
• A class is a type
• 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
• Information Hiding
  • Private clause for hidden entities
  • Public clause for interface entities
  • Protected clause for inheritance
• 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
• 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 (~)

 

 

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 number) {

if (topSub == maxLen)

cerr << ″Error in push – stack is full\n″;

else stackPtr[++topSub] = number;

};

void pop () {…};

int top () {…};

int empty () {…};

 

 

Parameterized abstract data types, classes can be somewhat generic by writing parameterized constructor functions

               Stack (int size) {

stk_ptr = new int [size];

max_len = size – 1;

top = -1;

};

 

A declaration of a stack object:

               Stack stk(150);

 

• 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() {  // Constructor for 100 elements
  stackPtr = new Type[100];
  maxLen = 99;
  topPtr = -1;
  }

Stack(int size) {  // Constructor for a given number

stackPtr = new Type[size];

maxLen = size – 1;

                topSub = -1;

       }
…
}

    – Instantiation: Stack<int> myIntStack;

 

 

Encapsulation constructs,

• Large programs have two special needs:
  • Some means of organization, other than simply division into subprograms
  • Some means of partial compilation (compilation units that are smaller than the whole program)
• Obvious solution: a grouping of subprograms that are logically related into a unit that can be separately compiled (compilation units)
• Such collections are called encapsulation

 

Naming encapsulation, Organizing programs by nesting subprogram definitions inside the logically larger subprograms that use them. Nested subprograms are supported in Ada, Fortran 95+, Python, JavaScript, and Ruby