对于队列的介绍在之前的文章一节写过了——//www.greatytc.com/p/41dc9265109a
这篇我是用的python内置的列表，是使用适配器设计模式，实现了我们的队列结构。
缺点就是我们需要不断地更新底层数组的大小，这会让某次操作的时间复杂度上升。虽然我们利用边界摊销，可以将平均下来的操作视为O(1)。
今天我们用链表来实现队列，让每一个操作真正的达到O(1)。
链表动态的增删，代替了之前改变数组大小的操作，但是值得注意的是，链表在删除尾结点的操作上，并不高效，因为他需要遍历链表拿到倒数第二个节点。
更通俗的说法：如果只给定尾结点的引用 ，我们很难有效地删除该节点。因为我们没法拿到他的前驱节点的引用。
根据队列先进先出的特点，它只能在队尾添加元素，在队头删除元素，所以我们把链表容易删除的一端——链表头作为队头，把链表尾作为队尾，为了我们添加元素方便，我们还需要维护一个_tail引用来指向链表尾元素，这样我们在添加一个新的元素的时候，就不用遍历链表来拿到尾结点的引用了。
这次的实现与昨大前天的实现栈——//www.greatytc.com/p/fe9c422db4de很像。
在实现的时候需要注意的一点是，当执行出队列的操作，而队列中只有一个元素的时候，我们在将最后一个元素出队列后，我们需要把_tail的引用改为None，因为此时的tail是指向最后一个元素，我们把头节点后移后，尾结点的引用还是在的，这样可以利于python进行垃圾回收。
源代码：
class Empty(Exception):
pass
class LinkedQueue:
class _Node:
def __init__(self, element, next):
self._element = element
self._next = next
def __init__(self):
self._head = None
self._tail = None
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def first(self):
if self.is_empty():
raise Empty("Queue is empty!")
return self._head._element
def enqueue(self, e):
newest = self._Node(e, None)
if self.is_empty():
self._head = newest
else:
self._tail._next = newest
self._tail = newest
self._size += 1
def dequeue(self):
if self.is_empty():
raise Empty("Queue is empty!")
answer = self._head
self._head = self._head._next
self._size -= 1
if self.is_empty():
self._tail = None
return answer
这次与上次一样没有实现str方法，当然遍历链表也可以实现查看队列的内容，但是我觉得数据结构应该具有封装性，用户不应该访问数据结构的内部情况。
