杨辉三角
杨辉三角的特点是，两腰都是1，中间的数=上面两个数之和。
使用队列思想实现杨辉三角的流程
- 首先，需要初始化一个队列。
- 将第一行的元素1入队，接着操作第二行（第一二行不需要求和操作，直接将元素入队即可）
- 从第三行开始，现在的队首指向N-1行，先将每行的固定元素1入队，然后循环操作求和过程：
将队首元素出队并保存其值tmp；
获取当前队首的元素x，并进行tmp=tmp+x，且将tmp入队； - 循环结束后，队首在N-1行的最后一个元素处，现在将其出队，然后在每行最后的固定元素1入队;
- 循环3、4步，最后打印最后一行的元素就可以输出杨辉三角了。
实现
Node
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkQueue
{
class Node<T>
{
T data;
Node<T> next;
/// <summary>
/// 构造器
/// </summary>
public Node()
{
this.Data = default(T);
this.Next = null;
}
/// <summary>
/// 构造器
/// </summary>
/// <param name="data"></param>
public Node(T data)
{
this.Data = data;
this.Next = null;
}
public T Data { get => data; set => data = value; }
internal Node<T> Next { get => next; set => next = value; }
}
}
LQueue
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkQueue
{
class LQueue<T>
{
Node<T> font; // 队首
Node<T> rear; // 队尾
/// <summary>
/// 构造器
/// </summary>
public LQueue()
{
font = new Node<T>();
rear = font;
font.Next = null;
}
/// <summary>
/// 在表尾入队
/// </summary>
/// <param name="data"></param>
public void Put(T data)
{
//新建节点
Node<T> tmp = new Node<T>(data);
//挂载节点到队尾
rear.Next = tmp;
//更新队尾
rear = tmp;
}
/// <summary>
/// 在表头出队
/// </summary>
public T Get()
{
if (font.Next == null) return default(T);
//保存队首元素
Node<T> tmp = font.Next;
//悬空队首元素
font.Next = font.Next.Next;
return tmp.Data;
}
/// <summary>
/// 判空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return font.Next == null;
}
/// <summary>
/// 读队列头元素
/// </summary>
/// <returns></returns>
public T GetHead()
{
return font.Next.Data;
}
}
}
Program
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkQueue
{
class Program
{
static void Main(string[] args)
{
LQueue<int> lq = new LQueue<int>();
int N = 5; //行数
int x;
lq.Put(1); //第一行元素入队
//从第二行元素开始
for (int n = 2; n <= N; n++)
{
lq.Put(1); //第n行第一个元素入队
//处理第1到n-1个元素
for (int j = 1; j <= n-2; j++)
{
int tmp = lq.Get(); //栈顶元素出队
Console.Write(tmp); //打印第n-1行的元素
x = lq.GetHead();
tmp = tmp + x; //利用队中第n-1行元素产生第n行元素
lq.Put(tmp);
}
x =lq.Get();
Console.WriteLine(x);
lq.Put(1); //将第n行尾的1入队
}
//打印最后一行的元素
while (!lq.IsEmpty())
{
Console.Write(lq.Get());
}
}
}
}
