c++循环队列实现杨辉三角
时间: 2024-10-22 14:18:49 浏览: 28
在C++中,我们可以使用数组来实现循环队列,并利用动态内存分配和索引来创建一个模拟循环结构的队列。对于杨辉三角,这是一个经典的递归和动态规划问题,它的每一行都是前一行的数字之和,通常用二维数组表示。下面是使用循环队列实现杨辉三角的一个简单示例:
```cpp
#include <iostream>
#include <vector>
class CircularQueue {
private:
int capacity;
std::vector<int> queue;
int front, rear;
public:
CircularQueue(int size) : capacity(size), front(-1), rear(-1) {}
void enqueue(int value) {
if ((rear + 1) % capacity == front) {
// 队满,扩大容量
expand();
}
queue[rear % capacity] = value;
rear = (rear + 1) % capacity;
}
int dequeue() {
if (isEmpty()) {
throw std::runtime_error("Queue is empty");
}
int value = queue[front];
queue[front] = 0; // Mark as removed for next iteration
front = (front + 1) % capacity;
return value;
}
bool isEmpty() const {
return front == rear;
}
private:
void expand() {
capacity *= 2;
std::vector<int> temp(capacity);
for (int i = front; i <= rear; ++i) {
temp[i] = queue[(i + capacity / 2 - front) % capacity]; // Shift elements
}
queue.swap(temp);
front = rear = 0;
}
};
// 杨辉三角函数
void printPascalTriangle(CircularQueue& cq) {
int n = 5; // 示例层数,可以根据需要修改
for (int row = 0; row < n; ++row) {
for (int col = 0; col <= row; ++col) {
cq.enqueue(col == 0 || col == row ? 1 : cq.dequeue() + cq.dequeue());
std::cout << cq.dequeue() << " ";
}
std::cout << "\n";
}
}
int main() {
CircularQueue pq(10); // 初始化一个大小为10的队列
printPascalTriangle(pq);
return 0;
}
```
在这个例子中,我们首先定义了一个`CircularQueue`类,它有一个内部循环队列用于存储三角形的元素。然后`printPascalTriangle`函数利用这个队列构建杨辉三角。每次添加或删除元素时,我们都确保队列保持循环结构。
运行这个程序将打印出前5层的杨辉三角。
阅读全文