3.2: Activity 2 - Abstract Data Type

Last updated
Save as PDF

Page ID: 49946

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Introduction

This section introduces the learner to abstract data types (ADT). The ADT section describes the different data types behaviour from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. All in all different data structures have different operations performed on them.

Definition of ADT

In computer science, an abstract data type (ADT) is defined as a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. An abstract data type is defined only by the operations that may be performed on it and by mathematical pre-conditions and constraints on the effects (and possibly cost) of those operations.

For example,

An abstract array is defined by the following operations:

Adding elements
Sorting elements
Searching elements
Re-arranging the elements
Performing matrix operations
Pre-fix and post-fix operations

An abstract list is defined by the following:

inserting
searching
deletion

An abstract linked list has the following operations:

checking whether the list is empty;
accessing a node to modify it or to obtain the information in it;
traversing the list to access all elements (e.g., to print them, or to find some specific element);
determining the size (i.e., the number of elements) of the list;
inserting or removing a specific element (e.g., the first one, the last one, or one with a certain value);
creating a list by reading the elements from an input stream;
converting a list to and from an array, string, etc.

An abstract stack, which is a last-in-first-out structure, could be defined by three operations:

push, that inserts some data item onto the structure,
pop, that extracts an item from it, and
peek or top, which allows data on top of the structure to be examined without removal.

An abstract queue data structure, which is a first-in-first-out structure, would also have three operations,

enqueue to join the queue;
dequeue, to remove the first element from the queue; and
front, in order to access and serve the first element in the queue.

An abstract hashing has the following operations:

Add (insert)
Delete (remove)

Abstract tree has the following:

Searching
Insertion
Deletion
Traversal
Sort

Conclusion

The section introduced the learner to abstract data types, which is about logical description of how data is viewed and the operations that are allowed without regard to how they will be implemented.

Assessment

What is the definition of a data type?
Describe briefly two ADTs that we studied in this section? In each case specifying the necessary operations for each.