class Queue (object):
"A Queue using an iterator"
# 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
for item in iterable:
self.enqueue(item)
def __iter__ (self):
return QueueIterator(self)
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
class QueueIterator (object):
__slots__ = ["current_node"]
def __init__ (self, queue):
if len(queue) == 0:
self.current_node = None
else:
self.current_node = queue._head
def __iter__ (self):
return self
def next (self):
if self.current_node is None:
raise StopIteration
else:
item = self.current_node[0]
self.current_node = self.current_node[1]
return item