在上一次，我们通过取余等数学方法实现了顺序存储的循环队列。由于我们使用的是Python内置的列表类型作为底层，实际上我们的存储空间并不是首尾相连的。下面，我们使用链式存储结构来实现一个真正首尾相连的循环队列：
class Node(object):'定义节点。'def __init__(self):'初始化：数据域与指针域。'self.data = Noneself.next = Noneclass Queue(object):'定义循环链表。'def __init__(self,MaxSize):'初始化：建立链式存储空间。'self.MaxSize = MaxSizeself.size = 0self.front = Noneself.rear = Noneself.OpenSpace()def OpenSpace(self):'方法：用于初始化。'node = Node()self.front = nodeself.rear = node #创建第一个节点，将队头指针与队尾指针指向它。for i in range(self.MaxSize - 1):node = Node()self.front.next = nodeself.front = node #通过移动队头指针将剩下的节点依次创建并连接。self.front.next = self.rearself.front = self.rear #利用队头指针与队尾指针将所有节点连接成环。def IsEmpty(self):'方法：判断是否为空队列。'if self.size == 0:return Trueelse:return Falsedef IsFull(self):'方法：判断是否为满队列。'if self.size == self.MaxSize:return Trueelse:return Falsedef GetSize(self):'方法：得到队列长度。'return self.sizedef push(self,data):'方法：进队。'if self.IsFull():raise IndexError('队列已满，无法入队。')else:self.rear.next.data = dataself.rear = self.rear.nextself.size += 1def pop(self):'方法：出队。'if self.IsEmpty():raise IndexError('队列已空，无法出队。')else:self.front.data = Noneself.front = self.front.nextself.size -= 1def GetFrontData(self):'方法：得到队首元素。'return self.front.datadef GetRearData(self):'方法：得到队尾元素。'return self.rear.data
测试：
my_queue = Queue(10)for i in range(5):my_queue.push(i + 1)print('队首元素：{}'.format(my_queue.GetFrontData()))print('队尾元素：{}'.format(my_queue.GetRearData()))print('\n')for i in range(3):my_queue.pop()print('队首元素：{}'.format(my_queue.GetFrontData()))print('队尾元素：{}'.format(my_queue.GetRearData()))print('\n')for i in range(5,5 + 8):my_queue.push(i + 1)print('队首元素：{}'.format(my_queue.GetFrontData()))print('队尾元素：{}'.format(my_queue.GetRearData()))my_queue.push(0)
结果:
队首元素：1队尾元素：1队首元素：1队尾元素：2队首元素：1队尾元素：3队首元素：1队尾元素：4队首元素：1队尾元素：5队首元素：2队尾元素：5队首元素：3队尾元素：5队首元素：4队尾元素：5队首元素：4队尾元素：6队首元素：4队尾元素：7队首元素：4队尾元素：8队首元素：4队尾元素：9队首元素：4队尾元素：10队首元素：4队尾元素：11队首元素：4队尾元素：12队首元素：4队尾元素：13Traceback (most recent call last):File "带链的队列.py", line 112, in <module>my_queue.push(0)File "带链的队列.py", line 63, in pushraise IndexError('队列已满，无法入队。')IndexError: 队列已满，无法入队。
