Week 7: Abstract Data Types

An abstract data type (ADT) is a functional model of a specific data structure. Example ADTs are Stacks and Queues. It can be said that the implementation of an ADT does not define it, but rather the data held inside it and its associated operations. For example, inside a Stack, one can store sets of objects and push() and pop() items out. As such, abstract data types explicitly have two parts:
(1) a set of operations that can be performed on the specific ADT (2) a name to specify a set of data.

There is also an underlying principle regarding abstract data types, in that they hide information. For example, if I wanted to implement an ADT in the form of a Queue. I can do so by writing:

class Queue:
    ''' Represent a FIFO queue.
    '''

    def __init__(self):
        ''' (Queue) -> NoneType
        '''
        self._data = []

    def enqueue(self, o):
        ''' (Queue, object) -> NoneType
        '''
        self._data.append(o)

    def dequeue(self):
        ''' (Queue) -> object
        '''
        return self._data.pop(0)

    def is_empty(self):
        ''' (Queue) -> bool
        '''
        return self._data == []

And thus I have implemented a Queue for anyone to use. However, when I allow someone to use my implementation of this Queue, I only need to provide the operations and the name so that someone may utilize this fully. In other words, I do not need to let them know the implementation information, but they are still able to use the Queue if I give them the operations like: enqueue, dequeue, and is_empty.


As such, some information is abstracted to the user and hidden (the actual code), but the user is still able to fully utilize the ADT knowing its methods.