class Queue (object):
"A Queue using a generator"
# We need to keep a pointer to the head and tail of the queue. As
# long as the queue is not empty, head is the first node and tail
# the last. Of course, if the queue is of length 1, head
# and tail are the same node. Both for efficiency reasons (len() in
# constant time) and to be able to determine when the queue is
# empty, we will also keep track of the queue's length
__slots__ = ["_head", "_tail", "_length"]
# Note: each queue node is a 2-element list: [item, next_node]. If
# the node is the last in the list, next_node is None.
def __init__ (self, iterable=[]):
self._length = 0
self._head = None
for item in iterable:
self.enqueue(item)
def __iter__ (self):
current_node = self._head
while current_node is not None:
item = current_node[0]
yield item
current_node = current_node[1]
def __len__ (self):
return self._length
def enqueue (self, item):
new_node = [item, None]
if self._length == 0:
self._head = new_node
self._tail = new_node
self._length = 1
else:
self._tail[1] = new_node
self._tail = new_node
self._length += 1
def dequeue (self):
if self._length == 0:
raise IndexError
else:
item = self._head[0]
self._head = self._head[1]
self._length -= 1
return item