Question

What do you understand by abstract data type or ADT? Provide examples and discuss implementation mechanisms in C++ and in object-oriented programming languages in general.

Answer 1

An abstract data type is a class or type which only exposes the the compatible operations that can be performed by the object of that type without providing any details of the implementation. It is called “abstract” because it gives an implementation-independent view.

For example, a Stack ADT can have the following functionalities:

• push() – Insert an element at one end of the stack called top.
• pop() – Remove and return the element at the top of the stack, if it is not empty.
• peek() – Return the element at the top of the stack without removing it, if the stack is not empty.
• size() – Return the number of elements in the stack.
• isEmpty() – Return true if the stack is empty, otherwise return false.
• isFull() – Return true if the stack is full, otherwise return false.

Below is a sample code for the same:

CODE

#include <bits/stdc++.h>

using namespace std;

#define MAX 1000

class Stack {

  int top;

public:

  int a[MAX];

  Stack() { top = -1; }

  bool push(int x);

  int pop();

  int peek();

  bool isEmpty();

int size();

bool isFull();

};

bool Stack::push(int x)

{

  if (top >= (MAX - 1)) {

    cout << "Stack Overflow";

    return false;

  }

  else {

    a[++top] = x;

    cout << x << " pushed into stack\n";

    return true;

  }

}

int Stack::pop()

{

  if (top < 0) {

    cout << "Stack Underflow";

    return 0;

  }

  else {

    int x = a[top--];

    return x;

  }

}

int Stack::peek()

{

  if (top < 0) {

    cout << "Stack is Empty";

    return 0;

  }

  else {

    int x = a[top];

    return x;

  }

}

bool Stack::isEmpty()

{

  return (top < 0);

}

bool Stack::isFull()

{

  return (top >= MAX);

}

int Stack::size() {

return top;

}