nhtrnm's blog

Python queue-like data structure
By nhtrnm, history, 8 years ago, In English

I recently decided to work with Python 3 and I have questions regarding queues. As far as I understand the queue in the queue library is adapted for multithreaded programs. I assume that that queue is not as efficient as the simple queue (if I am wrong please correct). Therefore, I found that there is a deque from collections library which resembles deque in C++. Am I right that that's what competitive Python programmers use (for example, BFS problems)?

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I program mostly in pypy and this is what i used for bfs.

Deque with popleft can easily replace queue and is fast for unbounded queue as it require no locking.


from collections import deque
 
def bfs(g, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])

Another Alternative is to use Queue module itself

import Queue # In python 3 it is 'queue'
q = Queue() # queue object created
# use q in your bfs code

Useful Link

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    deque is the right queue for algorithms. Don't use Queue it is for communication between threads.

    → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

You can read the source code for Python 3 queue module here.

As you can see from source, Queue class adds locks for put and get methods. If you just want a simple double ended queue, you should use deque from collections module. Even Queue uses deque internally.

You are right in assuming that Queue is not as efficient as deque and deque is what Python programmers use.

→ Reply