fifo queue

[drochom]

hi,

how would u improve this code?

class queue:
def __init__(self, size=8):
self.space = size
self.data = [None]*self.space
self.head = 0
self.tail = 0
self.len = 0
def __len__(self): return self.len
def push(self, x):
if self.len==self.space:
self.data.extend( self.data[:self.tail] )
self.data.extend( [None]* (self.space-self.tail) )
self.tail+=self.space
self.space*=2
self.data[self.tail]=x
self.tail+=1
if self.tail==self.space:
self.tail=0
self.len+=1
def pop(self):
if self.len:
elem = self.data[self.head]
self.head+=1
if self.head==self.space:
self.head=0
return elem
def top(self):
if self.len==0:
raise Exception, 'queue is empty'
return self.data[self.head]

thx in adv.

 

[Paul Rubin]

Unless the queue is really large, just use the pop operation to get
stuff off the top of the queue. That causes O(n) operations but it
should be fast if n is small.

class queue(list):
push = append
def pop(self):
return list.pop(self,0)

should do about what you wrote.

 

[Roel Schroeven]

drochom schreef:

hi,

how would u improve this code?

class queue:
> ...

I think I'd use collections.deque [1] instead of using a ring buffer as
you're doing (I think) and doing a lot of manual bookkeeping.

[1] http://docs.python.org/lib/deque-objects.html

 

[Alex Martelli]

Unless the queue is really large, just use the pop operation to get
stuff off the top of the queue. That causes O(n) operations but it
should be fast if n is small.

class queue(list):
push = append
def pop(self):
return list.pop(self,0)

should do about what you wrote.

If it IS large, then:

import collections
class queue(collections.deque):
push = collections.deque.append
pop = collections.deque.popleft

could be even better.


Alex

 

[Tim Roberts]

how would u improve this code?

I would add at least one comment...