

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

Implementing a Stack Class

First, we define an empty class Stack.



In [ ]:

    
class Stack:
    pass

Next we define a constructor to this class. The function $\texttt{stack}(S)$ takes an uninitialized object $S$ and initializes its member variable mStackElements. This member variable is a list containing the data stored in the stack.



In [ ]:

    
def stack(S):
    S.mStackElements = []

We add this method to the class Stack. Since we add it under the name __init__, this method will be the constructor.



In [ ]:

    
Stack.__init__ = stack
del stack

Next, we add the method push to the class Stack. The method $\texttt{push}(S, e)$ pushes $e$ onto the stack $S$.



In [ ]:

    
def push(S, e):
    S.mStackElements += [e]

We add this method to the class Stack.



In [ ]:

    
Stack.push = push
del push

The method pop removes the topmost element from a stack.



In [ ]:

    
def pop(S):
    assert len(S.mStackElements) > 0, "popping empty stack"
    S.mStackElements = S.mStackElements[:-1]

Stack.pop = pop
del pop

The method top returns the element that is on top of the stack.



In [ ]:

    
def top(S):
    assert len(S.mStackElements) > 0, "top of empty stack"
    return S.mStackElements[-1]

Stack.top = top
del top

The method isEmpty checks whether the stack is empty.



In [ ]:

    
def isEmpty(S):
    return S.mStackElements == []

Stack.isEmpty = isEmpty
del isEmpty

The method copy creates a shallow copy of the given stack.



In [ ]:

    
def copy(S):
    C = Stack()
    C.mStackElements = S.mStackElements[:]
    return C

Stack.copy = copy
del copy

The method toStr converts a stack into a string.



In [ ]:

    
def toStr(S):
    C = S.copy()
    result = C._convert()
    dashes = "-" * len(result)
    return '\n'.join([dashes, result, dashes])

Stack.__str__ = toStr
del toStr

The method convert converts a stack into a string.



In [ ]:

    
def convert(S):
    if S.isEmpty():
        return '|'
    top = S.top()
    S.pop()
    return S._convert() + ' ' + str(top) + ' |'

Stack._convert = convert
del convert

Testing



In [ ]:

    
def createStack(L):
    S = Stack()
    for x in L:
        S.push(x)
        print(S)
    return S



In [ ]:

    
S = createStack(range(10))



In [ ]:

    
S



In [ ]:

    
Stack.__repr__ = Stack.__str__



In [ ]:

    
print(S)



In [ ]:

    
for i in range(10):
    print(S.top())
    S.pop()
    print(S)



In [ ]: