Abstract Data Types using Python Lists

Introduction

This writing covers the implementation of abstract data types using Python Lists. Before getting into their implementation, let's examine what an abstract data type is and how it differs from a data structure.

Abstract Data Types

An Abstract Data Type (ADT) is an abstraction of a Data Type 😅. In the first part of this series, I mentioned that what defines a data structure is mainly its interfaces and their internal implementation. However, what differentiates one ADT from another is the set of interfaces provided by the ADT. An abstract data type defines the interfaces of a data type but provides no implementation of those interfaces.

Another way to put it is that abstract data types are theoretical concepts describing a data structure but without its implementation. Examples are Queues, Stacks, Lists, etc.

Across various languages, there are different implementations of abstract data types.

Another important phenomenon is the Adapter Design Pattern. The adapter design pattern works just like real-world adapters. It allows you to define new classes of objects with interfaces that leverage the interfaces of existing classes. It takes away the worry of implementation logic since all you have to do is ride on the existing interface of another class. I have some reservations about the adapter design and it lies in the fact that if you are not confident about the logic of the leveraged interface, you may be writing or duplicating inefficient code. Putting that aside, to achieve the Adapter design pattern, we can do the following

• initialize a private instance of the underlying class whose interface is to be leveraged.

• define methods that leverage existing methods of the underlying class

In this writing, I implement the Stack and the Queue abstract datatypes using the adapter design pattern.

Stack Abstract Data Type.

The Stack ADT models an object that stores a sequence of objects. Elements of the sequence are accessed in a last-in-first-out or first-in-last-out order. A real-world example of a stack is a pile of trays, the last added tray is the first accessible tray. Another relatable example of a stack is a

Only elements at the end of the stack can be accessed. This data type can be implemented using a Python list. Although elements of a list at any index can be accessed, storing the underlying list containing the stack in a private variable and defining interfaces that are needed to complete the functionalities/festues of our list as a stack helps us build

The table below shows the different interfaces we would be implementing, their description and their return value

The implementation is given below

class Stack:

    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def is_empty(self):
        if len(self._data)==0:
            return True
        return False

    def push(self, element):
        self._data.append(element)

    def pop(self):
        if self.is_empty():
            raise EmptyError(f"Empty Stack. Cannot perform operation")
        return self._data.pop()

    def __str__(self):
        return str(self._data)

s = Stack()
s.push('a')
print(s)
# returns ['a']

s.push('b')
print(s)
#returns['a', 'b']

s.push('c')
s.push('d')
print(s)
#returns ['a', 'b', 'c', 'd']

s.pop()
#returns 'd'

len(s)
#returns 3

Queue Abstract Data Type

To be continued...

The Queue ADT also models an object that stores a sequence of objects. However, in the Queue ADT, elements of the sequence are accessed in the first-in-first-out order.