本关任务:编写一个循环队列,实现入队、出队操作,判断队空、队满等特殊情况
时间: 2024-01-29 17:02:00 浏览: 146
循环队列是一种特殊的队列,它的队尾可以指向队列开头,形成一个环形结构。循环队列的实现需要使用数组,并记录队头和队尾指针。
下面是一个简单的循环队列实现,包含入队、出队操作和判断队空、队满等特殊情况的函数:
```python
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.head = 0
self.tail = 0
def is_empty(self):
return self.head == self.tail
def is_full(self):
return (self.tail + 1) % self.capacity == self.head
def enqueue(self, item):
if self.is_full():
raise ValueError("Queue is full")
self.queue[self.tail] = item
self.tail = (self.tail + 1) % self.capacity
def dequeue(self):
if self.is_empty():
raise ValueError("Queue is empty")
item = self.queue[self.head]
self.queue[self.head] = None
self.head = (self.head + 1) % self.capacity
return item
```
在上面的实现中,我们使用了一个数组来存储队列元素,同时记录队头和队尾指针。当队列为空时,队头和队尾指针相等;当队列满时,队尾指针指向数组的最后一个元素,队头指针指向数组的第一个元素。
为了实现循环队列,我们需要使用取模运算来计算队尾指针的位置,这样当队尾指针到达数组的末尾时,它会回到数组的开头。
我们还实现了一些特殊情况的处理。当队列已满时,插入操作会抛出一个异常;当队列为空时,删除操作也会抛出一个异常。
阅读全文