使用链表实现队列有几种类型?python
时间: 2023-11-18 07:06:26 浏览: 45
使用链表实现队列主要有两种类型:单向链表和循环链表。
1. 单向链表:单向链表是一种基本的链式结构,每个节点只包含一个指向下一个节点的指针。使用单向链表实现队列时,入队操作是在链表尾部添加一个节点,出队操作是从链表头部删除一个节点。
2. 循环链表:循环链表在单向链表的基础上,将链表的尾节点指向了头节点,形成了一个环形结构。使用循环链表实现队列时,入队操作同样是在链表尾部添加一个节点,但是出队操作是从链表头部删除一个节点,并将头节点的指针指向下一个节点。如果队列为空,头节点和尾节点指向同一个节点。
下面是使用Python实现单向链表和循环链表队列的代码示例:
单向链表队列:
```python
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next
class Queue:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return not bool(self.head)
def enqueue(self, value):
node = Node(value)
if not self.head:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def dequeue(self):
if self.is_empty():
return None
node = self.head
self.head = self.head.next
if not self.head:
self.tail = None
return node.value
```
循环链表队列:
```python
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next
class Queue:
def __init__(self):
self.tail = None
def is_empty(self):
return not bool(self.tail)
def enqueue(self, value):
node = Node(value)
if self.is_empty():
node.next = node
else:
node.next = self.tail.next
self.tail.next = node
self.tail = node
def dequeue(self):
if self.is_empty():
return None
node = self.tail.next
if node == self.tail:
self.tail = None
else:
self.tail.next = node.next
return node.value
```
需要注意的是,由于循环链表队列的存在,当队列为空时,头节点和尾节点指向同一个节点。