Queues in python using collections deque

Queues in python

The collections module provides us with a deque() function, that can be thought of like a list() but with some queue functionality. There are ways to build a queue from a list, but in this post I will cover how to use queue using the collections module’s deque().

from collections import deque
q = deque()
q.appendleft("apple")
q.appendleft("banana")
print(q)

deque(['banana', 'apple'])

print(type(q))

<class 'collections.deque'>

We will make use of deque() to insert and delete elements which in the parlance of our time are referred to as enque and deque operations. We also have a fancy __repr__ to represent our Queue object when it is printed.

from collections import deque
class Queue():
    def __init__(self):
        self.q = deque()

    def enq(self,value):
        self.q.appendleft(value)

    def deq(self):
        if len(self.q) > 0:
            return self.q.pop()
        else:
            return None

    def __len__(self):
        return len(self.q)

    def __repr__(self):
        if len(self.q) > 0:
            s = "<enqueue here>\n_________________\n"
            s += "\n_________________\n".join([str(item) for item in self.q])
            s += "\n_________________\n<dequeue here>"
            return s
        else:
            return "<queue is empty>"

Let’s make use of this now:

q = Queue()
q.enq("apple")
q.enq("banana")
q.enq("cherry")
print(q)

<enqueue here>
_________________
cherry
_________________
banana
_________________
apple
_________________
<dequeue here>

q.deq()

'apple'

First in was apple, First out is apple

q.deq()
q.deq()

'cherry'

q

<queue is empty>

Queue usage in BFS

Without a Queue, level-order traversal or Breadth First Search is not possible. Read my BFS.

Help on deque object

help(q)

Help on deque object:

class deque(builtins.object)
 |  deque([iterable[, maxlen]]) --> deque object
 |  
 |  A list-like sequence optimized for data accesses near its endpoints.
 |  
 |  Methods defined here:
 |  
 |  __add__(self, value, /)
 |      Return self+value.
 |  
 |  __bool__(self, /)
 |      self != 0
 |  
 |  __contains__(self, key, /)
 |      Return key in self.
 |  
 |  __copy__(...)
 |      Return a shallow copy of a deque.
 |  
 |  __delitem__(self, key, /)
 |      Delete self[key].
 |  
 |  __eq__(self, value, /)
 |      Return self==value.
 |  
 |  __ge__(self, value, /)
 |      Return self>=value.
 |  
 |  __getattribute__(self, name, /)
 |      Return getattr(self, name).
 |  
 |  __getitem__(self, key, /)
 |      Return self[key].
 |  
 |  __gt__(self, value, /)
 |      Return self>value.
 |  
 |  __iadd__(self, value, /)
 |      Implement self+=value.
 |  
 |  __imul__(self, value, /)
 |      Implement self*=value.
 |  
 |  __init__(self, /, *args, **kwargs)
 |      Initialize self.  See help(type(self)) for accurate signature.
 |  
 |  __iter__(self, /)
 |      Implement iter(self).
 |  
 |  __le__(self, value, /)
 |      Return self<=value.
 |  
 |  __len__(self, /)
 |      Return len(self).
 |  
 |  __lt__(self, value, /)
 |      Return self<value.
 |  
 |  __mul__(self, value, /)
 |      Return self*value.
 |  
 |  __ne__(self, value, /)
 |      Return self!=value.
 |  
 |  __reduce__(...)
 |      Return state information for pickling.
 |  
 |  __repr__(self, /)
 |      Return repr(self).
 |  
 |  __reversed__(...)
 |      D.__reversed__() -- return a reverse iterator over the deque
 |  
 |  __rmul__(self, value, /)
 |      Return value*self.
 |  
 |  __setitem__(self, key, value, /)
 |      Set self[key] to value.
 |  
 |  __sizeof__(...)
 |      D.__sizeof__() -- size of D in memory, in bytes
 |  
 |  append(...)
 |      Add an element to the right side of the deque.
 |  
 |  appendleft(...)
 |      Add an element to the left side of the deque.
 |  
 |  clear(...)
 |      Remove all elements from the deque.
 |  
 |  copy(...)
 |      Return a shallow copy of a deque.
 |  
 |  count(...)
 |      D.count(value) -> integer -- return number of occurrences of value
 |  
 |  extend(...)
 |      Extend the right side of the deque with elements from the iterable
 |  
 |  extendleft(...)
 |      Extend the left side of the deque with elements from the iterable
 |  
 |  index(...)
 |      D.index(value, [start, [stop]]) -> integer -- return first index of value.
 |      Raises ValueError if the value is not present.
 |  
 |  insert(...)
 |      D.insert(index, object) -- insert object before index
 |  
 |  pop(...)
 |      Remove and return the rightmost element.
 |  
 |  popleft(...)
 |      Remove and return the leftmost element.
 |  
 |  remove(...)
 |      D.remove(value) -- remove first occurrence of value.
 |  
 |  reverse(...)
 |      D.reverse() -- reverse *IN PLACE*
 |  
 |  rotate(...)
 |      Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left.
 |  
 |  ----------------------------------------------------------------------
 |  Static methods defined here:
 |  
 |  __new__(*args, **kwargs) from builtins.type
 |      Create and return a new object.  See help(type) for accurate signature.
 |  
 |  ----------------------------------------------------------------------
 |  Data descriptors defined here:
 |  
 |  maxlen
 |      maximum size of a deque or None if unbounded
 |  
 |  ----------------------------------------------------------------------
 |  Data and other attributes defined here:
 |  
 |  __hash__ = None