cc 3.1

stack.py

#stack structure in python 

class Node:
    
    def __init__(self,item):
        self.item = item
        self.next = None


class Stack:     
    
    def __init__(self):
        self.top = None
        self.size = 0

    def pop(self):
        if self.top is not None:
            new = self.top.item
            top = self.top.next
            self.size -= 1
            return new 


    def push(self,item):
        new = Node(item)
        if self.top is not None: 
            new.next = self.top
            self.top = new
        else:
            self.top = new
        self.size += 1
    

    def printStack(self):
        if self.top is not None:
            node = self.top
            while node is not None:
                print node.item,
                if node.next is not None:
                    print  '-->',
                node = node.next
        else:
            print 'null'
       

stackarray.py

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

from stack import Stack, Node

class stackarray:

    def __init__(self):
        self.array = ['one', 'two', 'three']
        self.start2 = self.array.index('two')
        self.size = len(self.array)
        self.stack1 = Stack()
        self.stack2 = Stack()
        self.stack3 = Stack()

    def addItem(self, stack_no, item):
        if stack_no == 1:
            self.push1(item)
        elif stack_no == 2:
            self.push2(item)
        elif stack_no == 3:
            self.push3(item)
        else:
            print 'invalid stack no.'

    def push1(self, item):
        new = item
        self.array.insert(0, new)
        self.size += 1
        self.start2 += 1
        self.stack1.push(item)
        return self.stack1.size
        
    def push2(self, item):
        new = item
        self.array.insert(self.start2, new)
        self.size += 1
        self.stack2.push(item)
        return self.stack2.size


    def push3(self, item):
        new = item
        self.array.insert(self.size - 1, new)
        self.size += 1
        self.stack3.push(item)
        return self.stack3.size

    def pop(self, stack_no):
        if stack_no == 1:
            self.stack1.pop
            del self.array[0]
            self.size -= 1

        if stack_no == 2:
            self.stack2.pop
            del self.array[self.stack1.size + self.stack1.size]
            self.size -= 1

        if stack_no == 3:
            self.stack3.pop
            del self.array[self.size - 2]
            self.size -= 1

        else:
            print 'invalid stack no.'        

    def printArr(self):
        print 'the array is:'
        for i in range(self.size):
            print self.array[i],


        
#test
arr = stackarray()
arr.addItem(1,5)
arr.addItem(2,3)
arr.addItem(1,8)
arr.addItem(3,6)
arr.addItem(2,14)
arr.addItem(3,20)
print 'stack1: ',
arr.stack1.printStack()
print 'stack2: ',
arr.stack2.printStack()
print 'stack3: ',
arr.stack3.printStack()
arr.printArr()
arr.pop(2)
arr.printArr()