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