43. implementing stack

Problem

Implement a stack that has the following method.

• push(val), which pushes an element onto the stack
• pop(), which pops off and returns the topmost element of the stack. If there are no elements in the stack, then it should throw an error or return null.
• max(), which returns the maximum value in the stack currently. If there are no elements in the stack, then it should throw an error or return null.

Each method should run in constant time.

How

We define Stack class and prepare max_val, top and prev as the class variable.

• prev represents the previous class instance.
• top represents the top value of a Stack.
• max_val represents the maximum value of a current stack instance

Implement

I have implemented by python

class Stack():
    class Node():
        def __init__(self, data, max_val=None):
            self.data = data
            self.prev = None
            self.max_val = max_val

    def __init__(self, top=None, prev=None):
        """
        node class
        """
        self.node = None

    def push(self, val):
        """
        Noting that updating max_val in this method
        """
        t = self.Node(val)
        t.prev = self.node
        if self.node != None:
            t.max_val = self.node.max_val
        if t.max_val == None:
            t.max_val = val
        else:
            t.max_val = val  if t.max_val < val else t.max_val
        self.node = t

    def pop(self):
        assert self.node != None, "Error. top value is empty"
        top = self.node
        self.node = top.prev
        return top.data

    def max(self):
        assert self.node.max_val != None, "Error. max value is empty"
        return self.node.max_val

if __name__ == "__main__":
    S = Stack()
    for i in range(10):
        S.push(i%4)
    # pop
    for i in range(10):
        print("max is", S.max())
        print("pop is", S.pop())