栈和队列的实际应用

布满荆棘的人生 2022-02-01 15:19 303阅读 0赞

**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();

![20190514212231975.png][]

**2.杨辉三角问题**

![20190514214552268.png][]

我们观察可知，该三角除了每一行的第一个元素和最后一个元素是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("请正确输入...");
                }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2huem1kbGhj_size_16_color_FFFFFF_t_70]: /images/20220201/d52941f265064aae8920a481a2e83d69.png
[20190514212231975.png]: /images/20220201/5de136aa209c4748a5c4509180c93695.png
[20190514214552268.png]: /images/20220201/4408ca5b8dfa4f22bac3cde39044e732.png