StacksQueues/Python/ArrayStack

Array-Based Stack Implementation.

This utilizes the built-in Python list type, and wraps it with a Stack ADT interface.

Class description

Recap: Definition of stack abstract data type (Stack ADT):

A stack is an abstract data type (ADT) such that an instance S supports the following two methods:

• S.push(e): add element e to the top of the stack S
• S.pop: remove and return the top element from the stack S; an error occurs if the stack is empty.

Additionally, accessor methods for convenience:

• S.peek(): get reference to top element without removing it; an error occurs if the stack is empty.
• S.is_empty(): return True if stack S contains no elements
• len(S): implemented via builtin __len__

The ArrayStack class implements the above abstraction using an array-based structure (a list).

Link: https://git.charlesreid1.com/cs/python/src/master/stacks-queues-deques/stacks/ArrayStack.py

Class test

Taking a look first at our test, we should be able to run the following code after implementing the above methods:

if __name__=="__main__":
    a = ArrayStack()
    a.push(5)
    a.push(15)
    a.push(17)
    a.push(28)
    print("Peeking: {0}".format(a.peek()))
    print("Length of stack: {0}".format(len(a)))
    a.pop()
    a.pop()
    a.push(100)
    a.push(200)
    a.push(300)
    a.push(400)
    while(not a.is_empty()):
        a.pop()
        print("Popping... {0}".format(len(a)))
    print("Done testing ArrayStack.")

Exceptions and error handling

The specification of the ADT mentions two cases where errors should be thrown - both occurring if the stack is empty.

Create our own Empty exception:

class Empty(Exception):
    pass

Class implementation

"""
Stack ADT: ArrayStack

This class implements the following methods:
    S.push(e)
    S.pop()
    S.peek()
    S.is_empty()
    len(S)

This class utilizes an array-based data structure,
a list, to store its data under the hood.
It only needs to keep track of that list.

This makes it an adapter class for the list,
since it adheres to the Stack ADT but does not change
the implementation of the underlying list type.
"""

class ArrayStack:
    """
    Implement the Stack ADT using an array-based data structure (list).
    """
    def __init__(self):
        self._data = []

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

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

    def is_empty(self):
        """
        Check if empty. Don't bother calling our own __len__.
        Just do what is sensible.
        """
        return (len(self._data)==0)

    def push(self,o):
        """
        Add an element to the top of the stack
        """
        self._data.append(o)

    def pop(self):
        """
        Pop the next item.
        This should handle an empty stack.
        """
        if( self.is_empty() ):
            raise Empty("Stack is empty")
        return self._data.pop()

    def peek(self):
        """
        Peek at the next item.
        This should handle an empty stack.
        """
        if( self.is_empty() ):
            raise Empty("Stack is empty")
        return self._data[-1]

This is an adapter pattern for the list class.