[已解决]测验1: 实现队列

KeyError

定义Myduilie类，有以下函数:
        def push(x: int) -> None:将x添加到队列的末尾
        def pop() -> int:从队列的开头移除并返回元素
        def peek() -> int:返回队列开头的元素
        def empty() -> bool:返回队列是否为空

最佳答案

月排行榜 / 总排行榜

Brick_Porter

2022-10-21 18:48:38

类名有所修改，此外还使用了typing库中的Any和Optional这两个类来注释返回值类型。

1. from typing import Any, Optional
   
2. 
   
3. 
   
4. class _Node:
   
5.     """节点类"""
   
6. 
   
7.     def __init__(self, v: Any) -> None:
   
8.         self.__value = v
   
9.         self.__next = None
   
10. 
    
11.     def get_value(self) -> Any:
    
12.         """获取节点保存的值"""
    
13.         return self.__value
    
14. 
    
15.     def get_next(self) -> Optional['_Node']:
    
16.         """获取下一个节点"""
    
17.         return self.__next
    
18. 
    
19.     def set_next(self, n: Optional['_Node']) -> None:
    
20.         """设置下一个节点"""
    
21.         self.__next = n
    
22. 
    
23. 
    
24. class QueueError(Exception):
    
25.     """自定义队列异常"""
    
26. 
    
27.     def __init__(self, msg: str) -> None:
    
28.         """使用提示信息实例化一个队列异常对象"""
    
29.         self.val = msg
    
30. 
    
31.     def __str__(self) -> str:
    
32.         return self.val
    
33. 
    
34. 
    
35. class MyQueue:
    
36.     """自定义队列"""
    
37. 
    
38.     def __init__(self) -> None:
    
39.         """实例化自定义队列，使用队首、队尾、长度三个属性记录队列信息"""
    
40.         self.__head: Optional[_Node] = None  # 队首，_Node类型或者为None
    
41.         self.__tail: Optional[_Node] = None  # 队尾，_Node类型或者为None
    
42.         self.__len: int = 0  # 队列长度
    
43. 
    
44.     def push(self, x: int) -> None:
    
45.         """将x添加到队列末尾"""
    
46.         node = _Node(x)
    
47.         if self.__len <= 0:
    
48.             self.__head = self.__tail = node
    
49.         else:
    
50.             self.__tail.set_next(node)
    
51.             self.__tail = node
    
52.         self.__len += 1
    
53. 
    
54.     def pop(self) -> int:
    
55.         """从队列开头移除并返回元素"""
    
56.         if self.__len > 0:
    
57.             node = self.__head
    
58.             self.__head = node.get_next()
    
59.             self.__len -= 1
    
60.             return node.get_value()
    
61.         raise QueueError('队列为空')
    
62. 
    
63.     def peek(self) -> Optional[int]:
    
64.         """查看队列开头的元素，如果队列为空则返回None"""
    
65.         if self.__len <= 0:
    
66.             return self.__head.get_value()
    
67.         return None
    
68. 
    
69.     def empty(self) -> bool:
    
70.         """返回队列是否为空"""
    
71.         return self.__len == 0
    
72. 
    
73. 
    
74. if __name__ == '__main__':
    
75.     q = MyQueue()
    
76.     for i in range(5):
    
77.         q.push(i)
    
78.     print(q.empty())
    
79.     for i in range(5):
    
80.         print(q.pop())
    
81.     q.pop()  # 抛出异常

复制代码

跳转到最佳答案楼层

Brick_Porter

类名有所修改，此外还使用了typing库中的Any和Optional这两个类来注释返回值类型。

1. from typing import Any, Optional
   
2. 
   
3. 
   
4. class _Node:
   
5.     """节点类"""
   
6. 
   
7.     def __init__(self, v: Any) -> None:
   
8.         self.__value = v
   
9.         self.__next = None
   
10. 
    
11.     def get_value(self) -> Any:
    
12.         """获取节点保存的值"""
    
13.         return self.__value
    
14. 
    
15.     def get_next(self) -> Optional['_Node']:
    
16.         """获取下一个节点"""
    
17.         return self.__next
    
18. 
    
19.     def set_next(self, n: Optional['_Node']) -> None:
    
20.         """设置下一个节点"""
    
21.         self.__next = n
    
22. 
    
23. 
    
24. class QueueError(Exception):
    
25.     """自定义队列异常"""
    
26. 
    
27.     def __init__(self, msg: str) -> None:
    
28.         """使用提示信息实例化一个队列异常对象"""
    
29.         self.val = msg
    
30. 
    
31.     def __str__(self) -> str:
    
32.         return self.val
    
33. 
    
34. 
    
35. class MyQueue:
    
36.     """自定义队列"""
    
37. 
    
38.     def __init__(self) -> None:
    
39.         """实例化自定义队列，使用队首、队尾、长度三个属性记录队列信息"""
    
40.         self.__head: Optional[_Node] = None  # 队首，_Node类型或者为None
    
41.         self.__tail: Optional[_Node] = None  # 队尾，_Node类型或者为None
    
42.         self.__len: int = 0  # 队列长度
    
43. 
    
44.     def push(self, x: int) -> None:
    
45.         """将x添加到队列末尾"""
    
46.         node = _Node(x)
    
47.         if self.__len <= 0:
    
48.             self.__head = self.__tail = node
    
49.         else:
    
50.             self.__tail.set_next(node)
    
51.             self.__tail = node
    
52.         self.__len += 1
    
53. 
    
54.     def pop(self) -> int:
    
55.         """从队列开头移除并返回元素"""
    
56.         if self.__len > 0:
    
57.             node = self.__head
    
58.             self.__head = node.get_next()
    
59.             self.__len -= 1
    
60.             return node.get_value()
    
61.         raise QueueError('队列为空')
    
62. 
    
63.     def peek(self) -> Optional[int]:
    
64.         """查看队列开头的元素，如果队列为空则返回None"""
    
65.         if self.__len <= 0:
    
66.             return self.__head.get_value()
    
67.         return None
    
68. 
    
69.     def empty(self) -> bool:
    
70.         """返回队列是否为空"""
    
71.         return self.__len == 0
    
72. 
    
73. 
    
74. if __name__ == '__main__':
    
75.     q = MyQueue()
    
76.     for i in range(5):
    
77.         q.push(i)
    
78.     print(q.empty())
    
79.     for i in range(5):
    
80.         print(q.pop())
    
81.     q.pop()  # 抛出异常

复制代码

KeyError

Brick_Porter 发表于 2022-10-21 21:24
类名有所修改，此外还使用了typing库中的Any和Optional这两个类来注释返回值类型。

还可以这么搞:

1. class Myduilie:
   
2.     def __init__(self):
   
3.          self.duilie=[]
   
4.     def push(self,x:int) -> None:
   
5.          self.duilie.append(x)
   
6.     def pop(self) -> int:
   
7.           return self.duilie.pop(0)
   
8.      def peek(self) -> int:
   
9.           return self.duilie[0]
   
10.       def empty() -> bool:
    
11.           return not self.duilie
    
12. 
    

复制代码