Sunday, April 22, 2012

How to Implement Stack in Python

Below are my simple implementations of stack (LIFO) using array list (some wasted space) and linked list (no wasted space). The LinkedStack uses the linked list implementation as described here.
#!/usr/bin/env python

class Stack(object):
    def __init__(self):
        self.l = []
        self.n = 0
        
    def push(self, element):
        if len(self.l) > self.n:
            self.l[self.n] = element
        else:
            self.l.append(element)
        self.n += 1
        
    def pop(self):
        if self.n == 0: return None
        self.n -= 1
        return self.l[self.n]
    
    def size(self):
        return self.n
    
    def elements(self):
        return [self.l[i] for i in xrange(0, self.n)]

class LinkedStack(object):
    def __init__(self):
        import linkedlist
        self.l = linkedlist.LinkedList()
        
    def push(self, element):
        self.l.append(element)
        
    def pop(self):
        return self.l.back()
    
    def size(self):
        return self.l.size()
    
    def elements(self):
        return [x for x in self.l.elements()]
        
if __name__ == "__main__":
    s = Stack()

    assert None == s.pop()
    
    s.push(1)
    s.push(2)
    s.push(3)
        
    assert 3 == s.pop()
    assert 2 == s.pop()
    assert 1 == s.pop()
    
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    s.push(5)
    
    assert 5 == s.pop()
    assert 4 == s.pop()
    assert 3 == s.pop()
    assert 2 == s.pop()
    assert 1 == s.pop()
    
    ls = LinkedStack()

    assert None == ls.pop()
    
    ls.push(1)
    ls.push(2)
    ls.push(3)
        
    assert 3 == ls.pop()
    assert 2 == ls.pop()
    assert 1 == ls.pop()
    
    ls.push(1)
    ls.push(2)
    ls.push(3)
    ls.push(4)
    ls.push(5)
    
    assert 5 == ls.pop()
    assert 4 == ls.pop()
    assert 3 == ls.pop()
    assert 2 == ls.pop()
    assert 1 == ls.pop()

No comments:

Post a Comment