使用循环队列实现上述数据进队和出队的操作,每次进队和出队操作后需要遍历队列。(附加题)
时间: 2024-02-06 07:10:08 浏览: 29
循环队列是一种非常常见的队列实现方式,其优点是可以充分利用数组空间,避免了数组元素浪费的问题。下面是使用循环队列实现进队和出队操作的示例代码:
```python
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.front = 0
self.rear = 0
self.data = [None] * capacity
def enqueue(self, value):
if (self.rear + 1) % self.capacity == self.front:
print("Queue is full")
else:
self.data[self.rear] = value
self.rear = (self.rear + 1) % self.capacity
def dequeue(self):
if self.front == self.rear:
print("Queue is empty")
else:
value = self.data[self.front]
self.front = (self.front + 1) % self.capacity
return value
def traverse(self):
if self.front == self.rear:
print("Queue is empty")
else:
i = self.front
while i != self.rear:
print(self.data[i], end=" ")
i = (i + 1) % self.capacity
print()
```
在这个实现中,我们使用了一个数组 `data` 来存储队列中的元素。其中 `front` 和 `rear` 分别表示队头和队尾的位置,它们的初始值都为 0。当队列为空时,它们的值相等;当队列满时,`rear` 的下一个位置就是 `front`。
进队操作时,首先判断队列是否已满。如果队列已满,则输出提示信息;否则,将元素插入到队尾,并将 `rear` 指针向后移动一位。
出队操作时,首先判断队列是否为空。如果队列为空,则输出提示信息;否则,取出队头元素并将 `front` 指针向后移动一位。
遍历队列时,首先判断队列是否为空。如果队列为空,则输出提示信息;否则,从队头开始遍历整个队列,并输出每个元素的值。
下面是一个使用循环队列的示例程序:
```python
if __name__ == '__main__':
queue = CircularQueue(5)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
queue.traverse()
queue.enqueue(6)
queue.traverse()
queue.dequeue()
queue.dequeue()
queue.traverse()
queue.enqueue(7)
queue.traverse()
```
输出结果为:
```
1 2 3 4 5
Queue is full
1 2 3 4 5
3 4 5
3 4 5 7
```