3.1 Describe how you could use a single array to implement three stacks.

ArrayStack.py

# idea: evenly divide an array into 3 parts to implement stacks separately. 
#       use 3 flags to indicate the top index of each stack. check before operation if current stack is full or empty
#       this solution only works for constant length of array
# time complexity: O(1)
# space complexity: O(1) for constant length of array

class myStack:
    def __init__(self):
        self.__array = [-1 for n in range(30)]
        self.__top = [-1, 9, 19]

    def pop(self, order):
        if self.__top[order] == 10 * order - 1:
            print 'no element to pop'
            return -1

        ret = self.__array[self.__top[order]]
        self.__array[self.__top[order]]  = -1
        self.__top[order] -= 1
        return ret

    def push(self, order, element):
        if self.__top[order] == 10 * (order + 1) - 1:
            print 'stack overflow'
            return

        self.__top[order] += 1
        self.__array[self.__top[order]] = element

    def top(self, order):
        if self.__top[order] == 10 * order - 1:
            print 'stack is null'
            return -1

        return self.__array[self.__top[order]]