python-034-实现队列-使用链表

对于队列的介绍在之前的文章一节写过了——https://www.jianshu.com/p/41dc9265109a
这篇我是用的python内置的列表，是使用适配器设计模式，实现了我们的队列结构。
缺点就是我们需要不断地更新底层数组的大小，这会让某次操作的时间复杂度上升。虽然我们利用边界摊销，可以将平均下来的操作视为O(1)。

今天我们用链表来实现队列，让每一个操作真正的达到O(1)。

链表动态的增删，代替了之前改变数组大小的操作，但是值得注意的是，链表在删除尾结点的操作上，并不高效，因为他需要遍历链表拿到倒数第二个节点。
更通俗的说法：如果只给定尾结点的引用 ，我们很难有效地删除该节点。因为我们没法拿到他的前驱节点的引用。

根据队列先进先出的特点，它只能在队尾添加元素，在队头删除元素，所以我们把链表容易删除的一端——链表头作为队头，把链表尾作为队尾，为了我们添加元素方便，我们还需要维护一个_tail引用来指向链表尾元素，这样我们在添加一个新的元素的时候，就不用遍历链表来拿到尾结点的引用了。

这次的实现与昨大前天的实现栈——https://www.jianshu.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方法，当然遍历链表也可以实现查看队列的内容，但是我觉得数据结构应该具有封装性，用户不应该访问数据结构的内部情况。