What is the best queue implemetation in Python?

[Szabolcs Nagy]

> For that purpose I have used the good deque that you can find in
> collections in the standard library. It's very good for queues, and
> it's a bit faster than regular lists for stacks too.

you mean *much* faster (since a list is a reference array so pop(0) is
O(n) operation)

never use a list as queue if len(queue) > 10000

=== benchmark

$ time ./deque_queue.py
34359607296

real	0m0.286s
user	0m0.264s
sys	0m0.016s

$ time ./list_queue.py
34359607296

real	1m20.915s
user	1m18.649s
sys	0m0.396s


=== the sources

--- deque_queue.py:
#!/usr/bin/python2.5

from collections import deque

def f(n):
	sum = 0
	queue = deque()
	for i in range(n):
		queue.append(i)
	while queue:
		sum += queue.popleft()
	print sum

if __name__=='__main__':
	f(1<<18)

--- list_queue.py:
#!/usr/bin/python2.5

def f(n):
	sum = 0
	queue = list()
	for i in range(n):
		queue.append(i)
	while queue:
		sum += queue.pop(0)
	print sum

if __name__=='__main__':
	f(1<<18)