栈和队列的实际应用-蒲公英云

栈和队列的实际应用

1.将一个非负的十进制整数N转换成其他D进制数。

解决思路，连续取模%和整除/。D进制各数位的产生顺序是从低位到高位，而输出顺序却是从高位到低位，刚好相反，可以考虑使用栈进行逆序输出。

public static string DecConvert(int N,int D)
        {
            if (D < 2 || D > 16) 
            {
                throw new ArgumentOutOfRangeException("二进制至十六进制之间转换");
            }
            Stack<char> stack = new Stack<char>();
            do
            {
                int res = N % D;
                char c = (res < 10) ? (char)(res + 48) : (char)(res + 55);
                stack.Push(c);
            }
            while ((N = N / D) != 0);//为0的时候，除到最后一位了
            string s = string.Empty;
            while (stack.Count > 0) 
            {
                s += stack.Pop().ToString();
            }
            return s;
        }

算法中十进制0和字符0 差48，在转换的过程中要加上48.

字母A 为65，比十大55，如下图所示：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2huem1kbGhj_size_16_color_FFFFFF_t_70

测试结果：

Console.WriteLine(StackApplication.DecConvert(13245,16)); Console.WriteLine(StackApplication.DecConvert(1238, 8));
Console.WriteLine(StackApplication.DecConvert(2263, 2));
Console.ReadKey();

2.杨辉三角问题

我们观察可知，该三角除了每一行的第一个元素和最后一个元素是1，其他元素的值是上一行与之相邻的两个元素之和。

算法思路：首先将要打印的数据依次进队，然后在打印每行除两端数据时，依据出队元素计算得出。

Queue<int> que = new Queue<int>();
            int left=0, right = 0;
            Console.Write("请输入行数");
            int n = int.Parse(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                for (int j = 1; j < n - i; j++) 
                {
                    //输出各行的空格数
                    Console.Write("  ");
                }
                //每行有i+1 个元素
                for (int k = 0; k <= i; k++) 
                {
                    int num = 1;
                    if (k != i) 
                    {
                        right = (int)que.Dequeue();
                        if (k != 0) 
                        {
                            num = left + right;
                        }
                        left = right;
                    }
                    //右对齐，四个长度
                    Console.Write(string.Format("{0,-4}", num.ToString()));
                    que.Enqueue(num);
                }
                Console.WriteLine();
            }

3.回文判断，正读和反读都相同的字符序列，如abba，abcba。设计一个算法判断输入的字符序列是否为回文。

思路：利用队列和栈的特性，一个是先进先出，一个是先进后出

Console.Write("请输入一个字符序列：");
            string str = Console.ReadLine();
            Queue<char> Que = new Queue<char>();
            Stack<char> Sta = new Stack<char>();
            for (int i = 0; i < str.Length; i++)
            {
                Que.Enqueue(str[i]);
                Sta.Push(str[i]);
            }
            if (str.Length > 1) 
            {
                if (Que.Dequeue()==Sta.Pop())
                {
                    Console.WriteLine("您输入的是回文");
                }
                else
                {
                    Console.WriteLine("您输入的不是回文");
                }
            }
            else
            {
                Console.WriteLine("请正确输入...");
            }