Java用队列实现杨辉三角（解析+完整实现源码）

杨辉三角是一个由数字排列成的三角形数表，一个 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++) { // 利用队列