Python-数据结构与算法（八、带有尾指针的链表队列及性能比较）
保证一周更两篇吧，以此来督促自己好好的学习！代码的很多地方我都给予了详细的解释，帮助理解。好了，干就完了～加油！
声明：本python数据结构与算法是imooc上liuyubobobo老师java数据结构的python改写，并添加了一些自己的理解和新的东西，liuyubobobo老师真的是一位很棒的老师！超级喜欢他～
如有错误，还请小伙伴们不吝指出，一起学习～
No fears, No distractions.
一、为什么要带尾指针来实现链表队列？
因为队列的操作实在两端进行的，而且凡是在链表进行的操作的时间复杂度一定是O(n)的！所以在尾部添加一个尾指针，时时刻刻都指向链表的最后一个元素，其下一个元素为None。此时添加元素的时间复杂度为O(1)，但是入队的话还是要从前往后撸到这里，所以还是O(n)的，但是我们可以把链表尾当做是队尾呀。链表头当做队首，此时入队与出队的操作的时间复杂度就都是O(1)的了！所以说要带一个尾指针！
声明：上图源自liuyubobobo老师上课的PPT，如有侵权请联系，立刻删除～
由于仅仅涉及到链表两端的操作，所以在这里我们就不用dummyhead啦，只需要维护两个成员变量：head和tail就好了！当然你也可以实现一个带dummyhead的队列，代码需要做出相应的调整。
二、带有尾指针的链表队列的实现
# -*- coding: utf-8 -*-
# Author: Annihilation7
# Data: 2018-09-28
# Python version: 3.6
from linklist.linkedlist import Node # 载入节点类
class LinkedListQueue:
def __init__(self):
"""构造函数，注意无capacity的概念"""
self._head = None # 首节点，初始化为None
self._tail = None # 尾节点，初始化为None
self._size = 0 # 有效元素的个数，初始化为0
def getSize(self):
"""
获取队列中有效元素的个数
:return: 元素个数
"""
return self._size
def isEmpty(self):
"""
判断队列是否为空
:return: Bool值，空为True
"""
return self._size == 0
def enqueue(self, elem):
"""
将元素elem入队，注意是在self._tail处进行入队操作
时间复杂度：O(1)
:param elem: 将要入队的元素，需要用一个Node来装载它
"""
if self.isEmpty(): # 控队列需要特殊处理
# 此时队列为空，则self._tail为None，此时self._head一定也是None
# 因为绝对不存在self._tail为None，而self._head不是空的情况
self._tail = Node(elem) # 将self._tail设为携带elem，且下一个元素为None的一个节点
self._head = self._tail # 将self._head置为self._tail，即self._head和self._tail标签同时贴在了这一个Node上，这样就把self._head和self._tail关联起来了
else:
self._tail.next = Node(elem) # 如果不为空正常在self._tail的后面添加Node
self._tail = self._tail.next # self._tail移动到队列的最后一个位置，即维护一下self._tail
self._size += 1 # 不论如何，入队了肯定要对self._size进行维护
def dequeue(self):
"""
队首元素出队，注意是在self._head处进行出队操作
时间复杂度：O(1)
:return: 队首元素所携带的值
"""
if self.isEmpty(): # 判空操作
raise Exception('Dequeue failed, please check out the size.')
retNode = self._head # 记录一下待出队元素，便于返回其值
self._head = self._head.next # self._head移动到下一个元素
retNode.next = None # 将retNode从队列中彻底断绝联系，使回收器能够将retNode回收
if self.isEmpty(): # 如果队列中只有一个元素，出队后空了，需要同时对self._tail做相应的处理
self._tail = None # 将self._tail设为None
self._size -= 1 # 维护self._size
return retNode.elem # 返回出队元素的值
def getFront(self):
"""
看一下队首元素的值
时间复杂度：O(1)
:return: 队首元素的值
"""
return self._head.elem
def printLinkedListQueue(self):
"""打印队列"""
print('Queue: Head---', end='')
cur = self._head # 从头开始
while cur != None: # 只要cur不是None，就打印并且往后撸
cur.printNode() # 调用Node的打印函数
cur = cur.next
print('---Tail')
print('Size: %d' % (self.getSize()))
三、测试
from linklist.linkedlistQueue import LinkedListQueue
import numpy as np
np.random.seed(7)
test = LinkedListQueue()
print(test.getSize())
print(test.isEmpty())
for i in range(15): # 入队15次
test.enqueue(np.random.randint(10))
test.printLinkedListQueue()
for i in range(12):
test.dequeue() # 出队12次，不用返回值了
test.printLinkedListQueue()
四、输出
0
True
Queue: Head---4 9 6 3 3 7 7 9 7 8 9 8 7 6 4 ---Tail
Size: 15
Queue: Head---7 6 4 ---Tail
Size: 3
五、性能比较
由于之前的代码可维护性还算可以，在这里我就把普通数组队列、循环队列和带有尾指针的链表队列的性能一起比较啦～
测试代码
from queue.general_queue import Queue # 普通队列在这个Py文件中
from queue.loopqueue import LoopQueue # 循环队列在这个Py文件中
from linklist.linkedlistQueue import LinkedListQueue # 带尾指针的链表实现的队列
import numpy as np
import datetime
np.random.seed(7)
def count_time(func):
def int_time(*args, **kwargs):
start_time = datetime.datetime.now() # 程序开始时间
func()
over_time = datetime.datetime.now() # 程序结束时间
total_time = (over_time - start_time).total_seconds()
print('共用时： %s 秒' % total_time)
return int_time
generalQueue = Queue() # 普通数组队列对象
loopQueue = LoopQueue() # 循环队列对象
linkedlistQueue = LinkedListQueue() # 带有尾指针的链表队列对象
nums = 30000 # 操作数为30000次
@count_time
def compute_generalQueue():
global nums, generalQueue
for i in range(nums): # 入队30000次
generalQueue.enqueue(np.random.randint(10))
for i in range(nums): # 出队30000次
generalQueue.dequeue()
@count_time
def compute_loopQueue():
global nums, loopQueue
for i in range(nums): # 同样的操作
loopQueue.enqueue(np.random.randint(10))
for i in range(nums):
loopQueue.dequeue()
@count_time
def compute_linkedlistQueue():
global nums, linkedlistQueue
for i in range(nums): # 同样的操作
loopQueue.enqueue(np.random.randint(10))
for i in range(nums):
loopQueue.dequeue()
if __name__ == '__main__':
print('普通队列：')
compute_generalQueue()
print('循环队列：')
compute_loopQueue()
print('带尾指针的链表队列：')
compute_linkedlistQueue()
测试结果
普通队列：
共用时： 53.576464 秒
循环队列：
共用时： 0.10933 秒
带尾指针的链表队列：
共用时： 0.113004 秒
总结
可以看出，普通数组队列还是那么奇慢无比，循环队列和带有尾指针的链表队列的性能是相当的呢～
若有还可以改进、优化的地方，还请小伙伴们批评指正！