掌握队列顺序存储上的初始化、入队、出队、取队头元素、判空基本操作的使用。 掌握使用队列实现杨辉三角的算法思想及代码实现

1. 队列顺序存储基本操作

初始化：

#define MaxSize 100
typedef struct {
    int data[MaxSize];
    int front, rear;
} SqQueue;
void InitQueue(SqQueue &Q) {
    Q.front = Q.rear = 0;
}

入队：

bool EnQueue(SqQueue &Q, int x) {
    if ((Q.rear + 1) % MaxSize == Q.front) { //队列满
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}

出队：

bool DeQueue(SqQueue &Q, int &x) {
    if (Q.front == Q.rear) { //队列空
        return false;
    }
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

取队头元素：

bool GetHead(SqQueue Q, int &x) {
    if (Q.front == Q.rear) { //队列空
        return false;
    }
    x = Q.data[Q.front];
    return true;
}

判空：

bool QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

2. 队列实现杨辉三角

杨辉三角是指如下图所示的一个数字三角形：

      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
 1 5 10 10 5 1

每个数等于它上方两数之和。请使用队列实现杨辉三角的代码如下：

void YangHui(int n) {
    SqQueue Q;
    InitQueue(Q);
    EnQueue(Q, 1); // 第一行只有一个1
    for (int i = 1; i <= n; i++) {
        int pre = 0; // 上一行的元素
        for (int j = 0; j < i; j++) {
            int x;
            DeQueue(Q, x);
            printf("%d ", x + pre);
            EnQueue(Q, x + pre); // 入队
            pre = x; // 保存当前元素，以便下次使用
        }
        printf("\n");
        EnQueue(Q, 1); // 每行最后一个元素为1
    }
}

调用示例：

YangHui(6);

输出：

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1