#!/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