队列杨辉三角

杨辉三角

杨辉三角的特点是，两腰都是1，中间的数=上面两个数之和。

使用队列思想实现杨辉三角的流程

1. 首先，需要初始化一个队列。
2. 将第一行的元素1入队，接着操作第二行（第一二行不需要求和操作，直接将元素入队即可）
3. 从第三行开始，现在的队首指向N-1行，先将每行的固定元素1入队，然后循环操作求和过程：
   将队首元素出队并保存其值tmp；
   获取当前队首的元素x，并进行tmp=tmp+x，且将tmp入队；
4. 循环结束后，队首在N-1行的最后一个元素处，现在将其出队，然后在每行最后的固定元素1入队;
5. 循环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());
            }
        }
    }
}