循环队列实现打印杨辉三角
时间: 2023-10-28 09:07:04 浏览: 160
循环队列是一种用数组实现的队列,通过循环利用数组的空间来解决队列元素的溢出问题。而杨辉三角是一个数学中的经典图形,它的每个数是由上方两数相加而得到的。下面是使用循环队列来实现打印杨辉三角的步骤:
1. 创建一个循环队列,用于存储每一行的数值。
2. 将第一行的数值1入队列。
3. 使用一个循环,每次迭代时从队列中取出一个数值,并打印。
4. 将当前数值与上一行的相邻两个数值相加,得到下一行的数值,并入队列。
5. 重复步骤3和步骤4,直到打印出指定行数的杨辉三角。
以下是一个示例的循环队列实现打印杨辉三角的代码:
```python
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.front = 0
self.rear = 0
def enqueue(self, item):
self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.capacity
def dequeue(self):
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
return item
def is_empty(self):
return self.front == self.rear
def print_yanghui_triangle(num_rows):
queue = CircularQueue(100)
queue.enqueue(1)
for i in range(1, num_rows+1):
prev = 0
for j in range(i):
curr = queue.dequeue()
print(curr, end=' ')
queue.enqueue(prev + curr)
prev = curr
print()
# 调用示例
print_yanghui_triangle(5)
```