08_队列的实现-基于单链表

2.4.2 单向队列功能的定义方法说明size()返回队列中元素个数is_empty()判断队列是否为空push(item)向队尾添加元素pop()从队首取出元素peek()访问队首元素classEmptyQueueError(Exception):passclassNode:def__init__(self,item,nextNone):self.itemitem self.nextnextclassQueue:def__init__(self):self.__headNoneself.__size0propertydefsize(self):returnself.__sizedefis_empty(self):returnself.__size0# 定义以单链表的头为队头以单链表的尾为队尾defpush(self,item):# 第一步创建新结点new_nodeNode(item)# 第二步添加元素# 2.1 队列为空ifself.__headNone:self.__headnew_nodeelse:# 2.2 队列不为空# 查询队尾nodeself.__headwhilenode.next!None:nodenode.next# 循环出来node.next None,此时node为队列的最后一个结点node.nextnew_node# 第三步个数1self.__size1defpop(self):ifself.is_empty():raiseEmptyQueueError(队列已空)itemself.__head.item self.__headself.__head.nextself.__size-1returnitem# 队头出列defpeek(self):ifself.is_empty():raiseEmptyQueueError(队列已空)returnself.__head.itemdef__str__(self):result# 遍历nodeself.__headwhilenodeisnotNone:resultstr(node.item)result-ifnode.nextelsenodenode.nextreturn队头:result:队尾if__name____main__:qQueue()print(初始size:,q.size)print(是否为空:,q.is_empty())q.push(a)q.push(b)q.push(c)print(q,q)try:print(peek:,q.peek())q.pop()print(q,q)print(peek:,q.peek())q.pop()print(q,q)print(peek:,q.peek())q.pop()print(q,q)print(peek:,q.peek())q.pop()print(q,q)q.pop()print(q,q)q.peek()exceptEmptyQueueErrorase:print(e)