Sunday, April 22, 2012

How to Implement Queue in Python

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

class Queue(object):
    def __init__(self):
        self.head = 0
        self.tail = 0
        self.n = 0
        self.l = []
    
    def enqueue(self, element):
        # this will create a lot of wasted space. Use something like
        # linked list
        self.l.append(element)
        self.tail += 1
        self.n += 1
    
    def dequeue(self):
        if self.n == 0: return None
        e = self.l[self.head]
        self.head += 1
        self.n -= 1
        return e
        
    def size(self):
        return self.n
    
    def elements(self):
        return [self.l[i] for i in xrange(self.head, self.tail)]

class LinkedQueue(object):
    def __init__(self):
        import linkedlist
        self.l = linkedlist.LinkedList()
    
    def enqueue(self, element):
        self.l.append(element)
    
    def dequeue(self):
        return self.l.front()
        
    def size(self):
        return self.l.size()
    
    def elements(self):
        return [x for x in self.l.elements()]
    
if __name__ == "__main__":
    q = Queue()
    
    assert None == q.dequeue()
    
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)

    assert 1 == q.dequeue()
    assert 2 == q.dequeue()
    assert 3 == q.dequeue()

    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)
    
    assert 1 == q.dequeue()
    assert 2 == q.dequeue()
    assert 3 == q.dequeue()
    assert 4 == q.dequeue()
    assert 5 == q.dequeue()
    
    lq = LinkedQueue()
    
    assert None == lq.dequeue()
    
    lq.enqueue(1)
    lq.enqueue(2)
    lq.enqueue(3)

    assert 1 == lq.dequeue()
    assert 2 == lq.dequeue()
    assert 3 == lq.dequeue()

    lq.enqueue(1)
    lq.enqueue(2)
    lq.enqueue(3)
    lq.enqueue(4)
    lq.enqueue(5)
    
    assert 1 == lq.dequeue()
    assert 2 == lq.dequeue()
    assert 3 == lq.dequeue()
    assert 4 == lq.dequeue()
    assert 5 == lq.dequeue()

No comments:

Post a Comment