3.3

SetOfStack.py

# idea: use a 2-D array to mimic set of stacks. 
# use a pivot index to indicate current stack that common pop() and push() are applyed to
# time complexity: O(1)
# space complexity: O(n)

class SetOfStack:
    def __init__(self):
        self.__stack = []
        self.__top = -1

    def pop(self):
        if self.__top == -1:
            print 'no element to pop'
            return -1
        
        ret = self.__stack[self.__top].pop(-1)
        if len(self.__stack[self.__top]) == 0:
            self.__top -= 1

        return ret
        
    def push(self, element):
        STACK_LEN = 10
        if self.__top == -1 or len(self.__stack[self.__top]) == STACK_LEN:
            self.__stack.append([])
            self.__top += 1
            
        self.__stack[self.__top].append(element)

    def popAt(self, index):
        if index < 0 or index > self.__top:
            print 'invalid input'
            return -1
        
        if len(self.__stack[index]) != 0:
            return self.__stack[index].pop(-1)