Queue using Linked List
A queue can be easily implemented as a SLL with two pointers, first and last. The trick is to remember that the arrows are kind of flipped.
last <- node <- node <- node <- first
Queue()
pushes a new last
Dequeue()
removes the first node.
Remember that if only one item is in the queue, head = tail; therefore if I dequeue(lastNode)
I must set *both* head and tail to None.
Remember that if a dequeue() the last node, first is automatically set to None but I also have to seat last to None.
class Node(object): def __init__(self, value): self.value = value self.next = None class Queue(object): first = None last = None def enqueue(self, value): new_node = Node(value) if self.first is None: self.first = self.last = new_node else: self.last.next = new_node self.last = new_node def dequeue(self): self.first = self.first.next if self.first is None: self.last = self.first print 'empty' def show(self): n = self.first while n is not None: print n.value, n = n.next q = Queue() q.enqueue('how') q.enqueue('are') q.enqueue('you') q.show() print q.dequeue() q.dequeue() q.dequeue() print q.enqueue('!') q.show()