用python编写结点类和一个用带有尾部指针的单链表实现的队列类LinkQueue,基本操作包括:初始化队列,判断队列是否为空,求队列长度,查看队头元素,将元素入队,将队头元素出队并返回其值.通过以下步骤测试基本操作的实现是否正确:创建一个链式队列,队列名称为yangkaidong=LinkQueue(),将值为19,190,1900的元素依次入队,将元素依次出队
时间: 2023-06-10 20:04:28 浏览: 102
。好的,根据你的要求,我已经创建了结点类和用带有尾部指针的单链表实现的队列类LinkQueue,并实现了基本的操作。下面是代码实现:
```
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
class LinkQueue:
def __init__(self):
self.head = ListNode(None)
self.tail = self.head
def is_empty(self):
return self.head == self.tail
def get_length(self):
p = self.head.next
length = 0
while p:
length += 1
p = p.next
return length
def get_head(self):
if self.is_empty():
return None
return self.head.next.val
def enqueue(self, val):
new_node = ListNode(val)
self.tail.next = new_node
self.tail = new_node
def dequeue(self):
if self.is_empty():
return None
p = self.head.next # 获得队头节点
self.head.next = p.next # 队头指向下一个节点
if self.tail == p: # 如果是最后一个节点出队,注意更新队尾
self.tail = self.head
return p.val
```
通过上述代码,我们已经完成了创建结点类和用带有尾部指针的单链表实现的队列类LinkQueue。接下来,我已经创建了一个名叫`yangkaidong`的链式队列,并依次将元素19、190、1900入队,然后再依次将元素出队并返回其值,这样就可以测试基本操作是否正确:
```
yangkaidong = LinkQueue()
yangkaidong.enqueue(19)
yangkaidong.enqueue(190)
yangkaidong.enqueue(1900)
print(yangkaidong.get_head()) # 19
print(yangkaidong.get_length()) # 3
print(yangkaidong.dequeue()) # 19
print(yangkaidong.dequeue()) # 190
print(yangkaidong.dequeue()) # 1900
print(yangkaidong.dequeue()) # None
```
可以看到,在上述测试中,我们先查看了队头元素,得到的值为19,然后获取队列长度,得到的值为3。接着依次出队,并返回其值,得到的值依次为19、190、1900。最后再次出队,得到的值为None,说明队列已经为空。 因此,可以通过上述代码测试看出,LinkQueue的基本操作是正确的。
阅读全文