//用队列打印杨辉三角
//算法：n=1 or 2 简单输出，n>=3-用队列实现（把杨辉三角按行入队，再出队）
//利用队列 FIFO性质

 
#include<stdio.h>
//范型 
typedef int ElementType;
//节点 
typedef struct {
ElementType data;
struct Node* next;
}Node;
//队头 
typedef struct {
  struct Node* front;
struct Node* rear; 
}Q;//queue 


//函数原型声明
Q* queueBuild();
int isEmpty(Q* queue);
void enQueue(Q* queue,ElementType enter);
ElementType deQueue(Q* queue);


int main()
{
int row;
char ans='y';
while(ans=='y'||ans=='Y')
{
printf("please input the row of this pascal's triangle,row=");
scanf("%d",&row);
getchar();


if(1==row) printf("1\n");
else if(2==row) printf("1\n1   1\n");
else{
Q* queue1=queueBuild();
//一二行入队 
enQueue(queue1,1); 
enQueue(queue1,1);
enQueue(queue1,1);
//3~n行入队 
int i,j;
//p，q起始位置 
Node* p=queue1->front;p=p->next;
Node* q=p->next;
for(i=3;i<=row;i++)//第i行 
{    
   enQueue(queue1,1);//此行第一个数 入队 
for(j=2;j<=i-1;)//2~倒二号数 入队 
 {     
  enQueue(queue1,p->data+q->data);
  j++;//这也说明了for的灵活性不够 
  if(j<=i-1)//没这块-p，q此后就报废掉了 
  {
  p=p->next;
  q=q->next;
  }
 } 
enQueue(queue1,1);//最后一个数入队 

p=q->next;
q=p->next;
}
 
//出队
//算法：第i行打印i个元素后，换行 
int count=1;
while(!isEmpty(queue1))
{
for(i=1;i<=count;i++)
{
printf("%5d",deQueue(queue1));
}printf("\n");
count++;
 } 
}//else


//继续操作选项
A1:printf("do you wanna continue print the Pascal's Triangle,ans=");
   scanf("%c",&ans);
   getchar();


  if(ans=='n'||ans=='N') break;
  if(ans!='y'&& ans!='Y'&&ans!='n'&&ans!='N')
    {
  printf("input error!again!\n");
  goto A1;
    } 
}

getchar();
return 0;
 } 
 
 //函数原型
 //建队/初始化 
 Q* queueBuild()
 {
  Q* p=(Q*)malloc(sizeof(Q));
if(p==NULL) exit(-1);

p->front=NULL;
p->rear=NULL;
return p; 
 } 
 
 int isEmpty(Q* queue)
 {
  return queue->front==NULL;
 }
 
 void enQueue(Q* queue,ElementType enter)
 {
  Node* p=(Node*)malloc(sizeof(Node));
  if(p==NULL) exit(-1);
  
  p->data=enter;
  p->next=NULL;
  //如果入队的作为第一个节点-front变动 
if(isEmpty(queue))
{
  queue->front=p;
  queue->rear=p;
} else{
Node* record_rear=queue->rear;
record_rear->next=p;
queue->rear=p;
}
 }
 
 ElementType deQueue(Q* queue)
 {
  //如果是空队，无法出队
if(isEmpty(queue)) return NULL; 
  //如果只用一个节点fear-变动 
if(queue->front==queue->rear)
{  
 Node* record_front=queue->front;
 ElementType de=record_front->data; 
 //ElementType de=(queue->front)->data; 
 free(record_front);
 queue->front=NULL;
 queue->rear=NULL;
 return de; 
}else{
Node* record_front=queue->front;//记录第一个节点
ElementType de=record_front->data;//记录出队的值 
queue->front=record_front->next;
   free(record_front);
return de; 
} 
//
 }

 //goto A1