#!/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()
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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment