编写一个链队列,实现入队、出队操作,判断队空等特殊情况
时间: 2024-05-14 16:14:42 浏览: 113
链式队列的实现,出队,入队等各种基本操作
4星 · 用户满意度95%
链队列是一种基于链表实现的队列,具有动态性和灵活性,可以根据实际情况进行动态调整。下面是一个简单的链队列的实现,包括入队、出队和判断队空等基本操作。
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def is_empty(self):
return self.front is None
def enqueue(self, data):
node = Node(data)
if self.rear is None:
self.front = node
self.rear = node
else:
self.rear.next = node
self.rear = node
def dequeue(self):
if self.is_empty():
return None
node = self.front
self.front = node.next
if self.front is None:
self.rear = None
return node.data
```
在上面的代码中,我们定义了一个`Node`类来表示队列中的节点,包含了节点数据和指向下一个节点的指针。队列本身是由`front`和`rear`两个指针组成的,分别指向队列的头部和尾部;当队列为空时,两个指针都为`None`。
`is_empty`方法用来判断队列是否为空,只需判断`front`是否为`None`即可。
`enqueue`方法用来将数据入队,首先创建一个新节点,然后判断队列是否为空,如果是空队列,则将`front`和`rear`均指向新节点;否则,将`rear`节点的`next`指针指向新节点,然后将`rear`指针指向新节点。
`dequeue`方法用来将数据出队,首先判断队列是否为空,如果是空队列,则直接返回`None`;否则,将`front`指针指向队列的下一个节点,然后判断`front`是否为`None`,如果是,则说明队列已经空了,需要将`rear`指针也置为`None`;最后返回被出队的节点数据。
阅读全文