数据结构 队列的应用之输出杨辉三角

队列的应用主要体现在四个方面，1解决计算机主机与外设不匹配的问题，2解决由多用户引起的资源竞争问题，3离散事件的模拟，模拟实际应用中各种排队问题，4用于处理具有先进先出的过程问题。

利用队列同时引入行界值0放在两行数据之间。最开始输出杨辉三角的最顶端 1 ，然后建立队列并将数据 0 1 1 一次插入到队列之中。其中 1 1是第一行的元素（三角的最顶端1不算行数），0就是行界值。行数k=1表示即将输出第一行（即 1 1）。进入while循环，while循环的目的是输出前n-1行的数据元素。首先输入空格，然后将行界值0插入进队列。再进入do while小循环，该小循环的作用就是输出第k行的数据并计算第k+1行的数据插入到队列中。do while 小循环中的操作首先是删除队头元素用 s 返回，其次是读取并用 e 返回当前的队头元素，这两步之后就判断 e 的值，如果非零即非行界值就输出，否则换行，最后计算 s+e 的值并插入。跳出do while循环后k++，再次循环处理下一行的数据。最后跳出大whlie循环，单独输出第n行的数据。执行程序如下：

#include
#define TRUE 1
#define FALSE 0

const int QUEUE_INIT_SIZE = 100;    //循环队列默认的初始分配最大空间量
const int QUEUEINCREMENT = 10;      //默认的增补空间量

typedef struct {
	int *elem;             //存储队列元素的数组
	int front;             //头指针，若队列不空，指向队列头元素
	int rear;              //尾指针，若队列不空，指向队列尾元素的下一个位置
	int queuesize;         //循环队列当前的最大容量
	int incrementsize;     //约定的扩容增量
}SqQueue;


void InitQueue_Sq(SqQueue &Q, int maxsize = QUEUE_INIT_SIZE, int incresize = QUEUEINCREMENT)
{
	//构造一个空队列Q
	Q.elem = new int[maxsize + 1];     //为循环队列分配（比实际能用多一个元素的）内存空间
	Q.queuesize = maxsize;
	Q.incrementsize = incresize;
	Q.front = Q.rear = 0;
}


int QueueLength_Sq(SqQueue Q)
{
	//返回Q的元素个数，即队列长度
	return (Q.rear - Q.front + Q.queuesize) % Q.queuesize;
}


bool DeQueue_Sq(SqQueue &Q, int &e)
{
	//若队列不空，则删除Q的队头元素，用e返回其值，并返回TRUE，否则返回FALSE
	if (Q.front == Q.rear)
		return FALSE;      //空队列
	e = Q.elem[Q.front];
	Q.front = (Q.front + 1) % Q.queuesize;
	return TRUE;
}


void incrementQueuesize(SqQueue &Q)
{
	//为循环队列Q增加Q.incrementsize个元素空间
	int *a;
	int k;
	a = new int[Q.queuesize + Q.incrementsize];
	for (k = 0; k < Q.queuesize - 1; k++)
		a[k] = Q.elem[(Q.front + k) % Q.queuesize];     //转移原循环队列中的数据元素
	delete[] Q.elem;                                    //释放原数组空间
	Q.elem = a;									        //为Q.elem设置新的数组位置
	Q.front = 0;									    
	Q.rear = Q.queuesize - 1;                           //设置新的头尾指针
	Q.queuesize += Q.incrementsize;             
}
void EnQueue_Sq(SqQueue &Q, int e)
{
	//插入元素e为Q的新的队尾元素
	if ((Q.rear + 1) % Q.queuesize == Q.front)
		incrementQueuesize(Q);
	Q.elem[Q.rear] = e;
	Q.rear = (Q.rear + 1) % Q.queuesize;
}


bool GetHead_Sq(SqQueue &Q, int &e)
{
	//若队列不空，则用e返回队头的元素，并返回TRUE，否则返回FALSE
	if (Q.front == Q.rear)
		return FALSE;      //空队列
	e = Q.elem[Q.front];
	return TRUE;
}

bool QueueEmpty(SqQueue Q)
{
	//若是一个空队列，则返回TRUE，否则返回FALSE
	if (Q.front == Q.rear)
		return TRUE;
	else
		return FALSE;
}

void Yanghui(int n)
{
	//打印输出杨辉三角的前n(n>0)行
	SqQueue Q;
	int i;
	int k;
	int s, e;                           //s用于存储删除队头元素后返回的数据，e用于读取当前的队头元素
	for (i = 1; i <= n; i++)
		printf(" ");
	printf("1n");                      //在最中心处输出杨辉三角的最顶端1
	InitQueue_Sq(Q, n + 2);             //设置最大容量为n+2的空队列
	EnQueue_Sq(Q, 0);                   //添加行界值
	EnQueue_Sq(Q, 1);
	EnQueue_Sq(Q, 1);                   //将第一行的 1 1 插入近队列
	k = 1;
	while (k < n)                       //通过循环输出前 n-1 行的值
	{
		for (i = 1; i <= n - k; i++)    //输出 n-k 个空格以保持三角形
			printf(" ");
		EnQueue_Sq(Q, 0);               //插入行界值
		do {                            //输出第k行同时计算并将第k+1行数据插入近队列
			DeQueue_Sq(Q, s);           
			GetHead_Sq(Q, e);
			if (e)
				printf("%d ", e);        //若e为非行界值，则打印输出 否则换行为下一行输出做准备
			else
				printf("n");
			EnQueue_Sq(Q, s + e);
		} while (e != 0);
		k++;                    
	}
	DeQueue_Sq(Q, e);
	while (!QueueEmpty(Q))               //单独处理第n行的输出
	{
		DeQueue_Sq(Q, e);
		printf("%d ", e);
	}
}

void main()
{
	int n;
	printf("请输入要打印的行数：");
	scanf("%d", &n);
	if (n == 1)
		printf(" 1 ");
	else
	Yanghui(n - 1);
}

本笔记所依据的教材为严薇敏版的《数据结构及应用算法教程》

所有代码在Visual Studio 2017上均可正常运行

如有错误欢迎指出