Defining __iter__

class Queue (object):

    # 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.

    # __init__, __len__, enqueue, and dequeue clipped -- see
    # the full implementation

    def __iter__ (self):
        return QueueIterator(self)

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

Weaknesses of this approach

• Labor Intensive: We had to define a completely separate class in order to implement the iterator protocol for our container class.
• Poor Encapsulation: Our iterator class required explicit knowledge of the private structure of the container that it is iterating over. A change in Queue will require a change in QueueIterator.
• Fragile Iteration: If the queue is changed during iteration, the behavior of existing iterators is undefined from Queue's standpoint (Queue would need knowledge of QueueIterator to precisely understand the behavior).