由于队列的动态由队头指针与队尾指针共同反映，所以我们在实现先入后出的同时还要实现队头元素与队尾元素的访问。对于普通的队列，我们使用列表实现其顺序存储，使用其它方法实现其链式存储。
顺序存储
由于我们使用list作为queue的底层、用Queue类对list进行了简单封装，所以在顺序存储结构中我们可以方便的利用列表的方法。具体代码：
class Queue(object):'定义队列。'def __init__(self):'初始化一个空列表。'self.items = []def IsEmpty(self):'方法：判断队列是否为空。'return self.items == []def get_size(self):'方法：求队列长度。'return len(self.items)def get_TopValue(self):'方法：访问队头元素。'if self.IsEmpty():return Noneelse:return self.items[0]def get_BottomValue(self):'方法：访问队尾元素。'if self.IsEmpty():return Noneelse:return self.items[-1]def push(self,data):'方法：进队。'self.items.append(data)def pop(self):'方法：出队。'if self.IsEmpty():raise IndexError('队列为空。')else:self.items.pop(0)
简单测试：
my_queue = Queue()print('Is my queue empty?\n{}'.format(my_queue.IsEmpty()))[my_queue.push(i + 1) for i in range(10)] print('The top value is {}'.format(my_queue.get_TopValue()))print('The bottom value is {}'.format(my_queue.get_BottomValue()))for i in range(11):print('第{}次：'.format(i + 1))my_queue.pop()print('The top value is {}'.format(my_queue.get_TopValue()))print('The bottom value is {}'.format(my_queue.get_BottomValue()))
测试结果：
Is my queue empty?TrueThe top value is 1The bottom value is 10第1次：The top value is 2The bottom value is 10第2次：The top value is 3The bottom value is 10第3次：The top value is 4The bottom value is 10第4次：The top value is 5The bottom value is 10第5次：The top value is 6The bottom value is 10第6次：The top value is 7The bottom value is 10第7次：The top value is 8The bottom value is 10第8次：The top value is 9The bottom value is 10第9次：The top value is 10The bottom value is 10第10次：The top value is NoneThe bottom value is None第11次：Traceback (most recent call last):File "带链的队列.py", line 58, in <module>my_queue.pop()File "带链的队列.py", line 44, in popraise IndexError('队列为空。')IndexError: 队列为空。
链式存储
我们通过实例化一个Node类来表示节点，其中存储有数据值data和后件next，具体代码为
class Node(object):'定义节点。'def __init__(self):'初始化数据域和指针域。'self.data = Noneself.next = Noneclass Queue(object):'定义队列。'def __init__(self):'初始化队头top与队尾bottom。'self.top = Noneself.bottom = Noneself.size = 0def IsEmpty(self):'方法：判断是否为空队。'if self.size == 0:return Trueelse:return Falsedef get_size(self):'方法：得到队列大小。'return self.sizedef get_TopValue(self):'方法：访问队头元素。'if self.IsEmpty():return Noneelse:return self.top.datadef get_BottomValue(self):'方法：访问队尾元素。'if self.IsEmpty():return Noneelse:return self.bottom.datadef push(self,data):'方法：入队。'node = Node()node.data = dataif self.IsEmpty():self.top = nodeself.bottom = nodeelse:self.bottom.next = nodeself.bottom = nodeself.size += 1def pop(self):'方法：出队。'if not self.IsEmpty():self.top = self.top.nextelse:raise IndexError('队列为空。')self.size -= 1
简单测试：
my_queue = Queue()print('Is my queue empty?\n{}'.format(my_queue.IsEmpty()))[my_queue.push(i + 1) for i in range(10)] print('The top value is {}'.format(my_queue.get_TopValue()))print('The bottom value is {}'.format(my_queue.get_BottomValue()))print('The size of my queue is {}'.format(my_queue.get_size()))for i in range(11):print('第{}次：'.format(i + 1))my_queue.pop()print('The top value is {}'.format(my_queue.get_TopValue()))print('The bottom value is {}'.format(my_queue.get_BottomValue()))print('The size of my queue is {}'.format(my_queue.get_size()))
测试结果：
Is my queue empty?TrueThe top value is 1The bottom value is 10The size of my queue is 10第1次：The top value is 2The bottom value is 10The size of my queue is 9第2次：The top value is 3The bottom value is 10The size of my queue is 8第3次：The top value is 4The bottom value is 10The size of my queue is 7第4次：The top value is 5The bottom value is 10The size of my queue is 6第5次：The top value is 6The bottom value is 10The size of my queue is 5第6次：The top value is 7The bottom value is 10The size of my queue is 4第7次：The top value is 8The bottom value is 10The size of my queue is 3第8次：The top value is 9The bottom value is 10The size of my queue is 2第9次：The top value is 10The bottom value is 10The size of my queue is 1第10次：The top value is NoneThe bottom value is NoneThe size of my queue is 0第11次：Traceback (most recent call last):File "带链的队列.py", line 84, in <module>my_queue.pop()File "带链的队列.py", line 70, in popraise IndexError('队列为空。')IndexError: 队列为空。
