建立循环链队列,并在循环链队列上实现入队、出队基本操作。
时间: 2024-10-21 18:11:24 浏览: 53
循环链表是一种特殊的线性数据结构,它的头节点指向最后一个节点,形成一个环形结构,避免了传统链表需要额外空间存储头指针的问题。在循环链队列中,可以实现先进先出(FIFO)的行为,通过修改链表的头部和尾部元素来进行入队和出队操作。
**入队(Enqueue)操作:**
1. 如果队列为空,新元素直接作为头结点和尾结点;
2. 否则,找到当前尾结点,将其next指针指向新元素,然后更新尾指针指向新元素。
**出队(Dequeue)操作:**
1. 如果队列为空,返回空或者抛出异常;
2. 否则,将头结点的值赋给结果,然后将头结点指向下一个元素(即原头结点的next),如果新的头结点已经是尾结点,则头结点变为下一个节点的前一个节点(即恢复到环形链表的状态)。
**代码示例(Python):**
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class CircularQueue:
def __init__(self, capacity):
self.front = None
self.rear = None
self.capacity = capacity
self.size = 0
def is_empty(self):
return self.front is None
def enqueue(self, item):
if self.is_full():
print("Queue is full")
return
new_node = Node(item)
if self.is_empty():
self.front = self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
self.rear.next = self.front # 将尾节点连接到头节点形成环
self.size += 1
def dequeue(self):
if self.is_empty():
print("Queue is empty")
return None
removed_data = self.front.data
if self.front == self.rear:
self.front = self.rear = None
else:
self.front = self.front.next
self.size -= 1
return removed_data
def is_full(self):
return self.size >= self.capacity
```
阅读全文