Java用队列实现杨辉三角(解析+完整实现源码)
杨辉三角是一个由数字排列成的三角形数表,一个 8 阶的杨辉三角图形如下图所示。

图 1 8 阶的杨辉三角
从上图可以看出,杨辉三角具有以下性质:
可以把杨辉三角分为 2 个部分来构造队列:所有的两端元素 1 作为已知部分,剩下的元素作为要构造的部分。
我们可以通过循环队列来实现杨辉三角的打印,在循环队列中依次存入第 i-1 行元素,再利用第 i-1 行元素得到第 i 行元素,然后依次入队,同时第 i-1 行元素出队并打印输出。
从整体来考虑,利用队列构造杨辉三角的过程,其实就是利用上一层元素序列产生下一层元素序列并入队,然后将上一层元素出队并输出,接着由队列中的元素生成下一层元素,以此类推,直到生成最后一层元素并输出。
我们以第 8 行元素为例来理解杨辉三角的具体构造过程:
1) 在第 8 行中,第一个元素先入队。假设队列为 Q:
2) 第 8 行的中间 6 个元素通过第 7 行元素(已经入队)得到并入队:
3) 第 7 行最后一个元素出队:
4) 第 8 行最后一个元素入队:
至此,第 8 行的所有元素都已经入队。其他行的入队操作类似。
【实例】打印杨辉三角。

图 1 8 阶的杨辉三角
从上图可以看出,杨辉三角具有以下性质:
- 第一行只有一个元素;
- 第 i 行有 i 个元素;
- 第 i 行最左端和最右端的元素为 1;
- 第 i 行中间的元素是它上一行 i-1 行对应位置的元素与对应位置的前一个元素之和。
队列实现杨辉三角
杨辉三角的第 i 行元素是根据第 i-1 行元素得到的,杨辉三角的形成序列是具有先后顺序的,因此杨辉三角可以通过队列来构造。可以把杨辉三角分为 2 个部分来构造队列:所有的两端元素 1 作为已知部分,剩下的元素作为要构造的部分。
我们可以通过循环队列来实现杨辉三角的打印,在循环队列中依次存入第 i-1 行元素,再利用第 i-1 行元素得到第 i 行元素,然后依次入队,同时第 i-1 行元素出队并打印输出。
从整体来考虑,利用队列构造杨辉三角的过程,其实就是利用上一层元素序列产生下一层元素序列并入队,然后将上一层元素出队并输出,接着由队列中的元素生成下一层元素,以此类推,直到生成最后一层元素并输出。
我们以第 8 行元素为例来理解杨辉三角的具体构造过程:
1) 在第 8 行中,第一个元素先入队。假设队列为 Q:
Q.queue[rear]=1 Q.rear=(Q.rear+1)%QUEUESIZE
2) 第 8 行的中间 6 个元素通过第 7 行元素(已经入队)得到并入队:
Q.queue[rear]=Q.queue[front]+Q.queue[front+1] Q.rear=(Q.rear+1)% QUEUESIZ Q.front=(Q.front+1)% QUEUESIZE
3) 第 7 行最后一个元素出队:
Q.front=(Q.front+1)% QUEUESIZE
4) 第 8 行最后一个元素入队:
Q.queue[rear]=1 Q.rear=(Q.rear+1)% QUEUESIZE
至此,第 8 行的所有元素都已经入队。其他行的入队操作类似。
杨辉三角队列的实现
打印杨辉三角可以使用顺序队列或链式队列的基本算法实现,也可以直接使用数组模拟队列实现。下面只给出打印杨辉三角的顺序队列实现,使用数组模拟队列实现留给读者自行完成。【实例】打印杨辉三角。
public class YangHuiTriangleTest { int count; // 记录输出的行 public void YangHuiTriangle(int N) throws Exception { // 顺序队列实现打印杨辉三角 int QUEUESIZE = 20; Integer temp[] = new Integer[QUEUESIZE]; // 用于存放每一行的元素 int k = 0; SeqQueue Q = new SeqQueue(); // 初始化顺序队列 Q.EnQueue(1); // 第一行元素入队 for (int i = 2; i < N + 1; i++) { // 产生第 i 行元素并入队,同时将第 i-1 行元素保存在临时数组中 k = 0; Q.EnQueue(1); // 第 i 行的第一个元素入队 for (int j = 1; j < i - 1; j++) { // 利用队列