#Class invariant for SimpleQueue, a queue based on a linked list # 1. The queue is a linked list of ListNode objects. # 2. A SimpleQueue object has instance variables self.head, a reference to the node at the front of the queue, self.tail, a reference # to the node at the end of the queue, and self.size, the number of nodes in the queue. # 3. If self.size = 0, then self.head and self.tail are None. # 4. The ListNode object at the end (referred to by self.tail) has link None. For all other ListNode objects, # the link refers to the next ListNode in the queue. # 5. The new item is enqueued at the tail of the SimpleQueue. # 6. An item is dequeued from the head or front of the SimpleQueue. class SimpleQueue: '''a class for a simple queue implemented as a linked list with head and tail references''' def __init__(self): '''constructor that creates an empty queue''' def enqueue(self, item): '''post: ListNode with item as its data has been inserted at the tail of the queue''' def dequeue(self): '''post: The ListNode at the head of the Queue has been removed from the queue and its item has been returned.''' def front(self): '''post: Returns the item at the front of the queue. The ListNode at the front is not removed. ''' def length(self): '''post: Returns the number of items in the queue''' class ListNode(object): def __init__(self, item = None, link = None): '''post: creates a ListNode with the specified data value and link''' self.item = item self.link = link