(c#)数据结构与算法分析 --栈与队列

时间:2020-12-04 17:36:56
栈stack    
    栈是一种后进后出机制,它只允许访问访问一个数据项,即 栈顶(最后插入的数据项)。它有主要的三种操作: push,向栈内压入值; pop,弹出栈顶的值,即返回栈顶的值,并把它从栈内删除; peek,只返回但不删除栈顶。
    
    概念很容易理解,无非就像给弹匣压子弹等等这种类比,但是像我这样的新手在刚接触到栈的时候总是很迷茫,认为它很难,其实这只是错觉,主要是因为没有搞清楚栈主要用在那些场景。

    栈普遍应用于编译器、文本检测、科学计算等等,在编译器中,它用来检测一个函数体等是否为封闭的(括号是否成对等等),在文本检测中,想想你的vs,如果最后没有大括号它就会检测出来,和编译器中一样,在科学计算中,就像商店能买到的那些高级计算器,输入一个算式可以直接计算出来结果,而不像普通计算器中,只能输入数字,然后在按键一步一步计算,以上这些应用场景,归根结底都是对文本的检测,现在知道栈的用途了吧,后面将结合队列一起练练手。

队列queue
    顾名思义,就是一堆东西成队排列了,它是先进先出机制(FIFO)与栈相反,栈是后进后出(LIFO)。它的主要操作有: Enqueue,向队尾添加值;Dequeue,返回并移除对头的值;peek,返回但不移除对头的值。

    队列很容易理解,它主要应用在网络通信、系统等。windows的所有事件都是放在队列里面的。

    最典型的,就是系统的任务分配了,每个进程或线程都分配在某些队列里,方便cpu时间片的分配调度,任务的运行不可能是你最后打开的程序先运行吧,当然它有优先级,这个排除在外。

栈的应用
    现在搞清楚了栈和队列的应用场景,那就趁热打铁,练练手。

    现在,按部就班的实现一个科学表达式的计算。

    首先了解一下计算机是怎么计算类似于 1*(2+3)+4/2 这样的计算。对于大脑来说,这个算式简单到不能再简单了,但是电脑却不是如此,得让它明白那个先算,那个后算,以及哪些是操作符(运算符)哪些不是(例如括号)。

    像我们经常使用的这种算式称为 中缀式 ,就是运算符都在两个操作符中间了,这种中缀式对于我们人脑来说,并不是顺序执行的,它可以从中间先开始,比如1+2*3 ,这正是电脑很难理解中缀式的原因,因为他总是顺序执行的。那么,我们就得把中缀式换成 后缀式(postfix)  或称作 逆波兰记法(reverse Polish notation)。

    中缀式就是把运算符放到两个操作数后边,让算式保持顺序计算(对于我们人脑也是如此)。具体怎么放,大家看看下面的例子就明白了。
     
    
示例 1:

中缀式

后缀式

A+B+C-D A B+C+D-
A*B/C+D A B*C/D+
A*(B+C*D)+E A B C D * + * E +
(A+B)*C/(D+E-F) A B + C * D E + F - /
A+B*C+(D*E+F)*G A B C * + D E * F + G * +

    结合上边的示例,会发现后缀式并没有描述优先级的括号,这是因为括号并不是运算符。大家在自己动手做两个,就掌握这种方法了。
    
    程序中如何实现这种转换呢?那就要依靠强大的栈了。

中追到后缀的转换 
   
  • 当读到一个操作数时,立即把它放到输出中,即显示出来。操作符不立即输出,从而必须先存在某个地方,例如栈或变量。当遇到一个左括号时也把它放入栈中。计算是从一个初始化为空的栈开始。
  • 如果栈为空,则将符号入栈。
  • 如果遇见一个右括号,那么就将栈元素弹出并输出,直到遇到一个(相对应的)左括号,但是这个左括号只弹出,并不输出。
  • 如果遇见优先级与栈首元素相同或比较低的符号,则将栈的所有元素弹出并输出,直到遇见一个左括号为止,这个左括号只弹出,并不输出,最后,将遇到的那个符号入栈。
  • 如果遇见优先级与栈首元素高的符号(右括号除外),则把它入栈。
  • 如果遇见右括号,则弹出并输出所有元素,直到遇到一个与之相对应的左括号,这个左括号只弹出不输出。
  • 如果读到末尾了,则将栈中元素弹出并输出,直到栈为空,左括号只弹出不显示
  •     以上,是我结合《数据结构与算法分析C++描述》相应段落和我的实际经验(经验并不多)总结出来的,原书的内容很难理解,像我这样的人,只看书,两天才明白过来,主要是方法容易,做起来难,尤其是第一次写这样的程序,如有什么纰漏或错误,还请指出。

        下面是实现中缀转后缀的程序:
        示例 2:

  •         private   void  stack()
            {
                Dictionary
    < char int >  opreater  =   new  Dictionary < char int > ();   // 这个用来存放操作符和他们的优先级

                
    // 3最高
                opreater.Add( ' + ' 1 ); 
                opreater.Add(
    ' - ' 1 );
                opreater.Add(
    ' * ' 2 );
                opreater.Add(
    ' / ' 2 );
                opreater.Add(
    ' ( ' 3 );
                opreater.Add(
    ' ) ' 3 );


                
    string  m  =  Console.ReadLine();  // 读取一个算式

                Stack
    < char >  opreaters  =   new  Stack < char > ();  // 这个栈用来存放操作符
                Queue < char >  mq  =   new  Queue < char > ();  // 这个队列存放算式
                
    // 将算式字符串的字符一个个插入队列
                 for  ( int  i  =   0 ; i  <  m.Length; i ++ )
                {
                    mq.Enqueue(m[i]);
                }


                
    // 开始将中缀转换为后缀算式
                Console.WriteLine( " 开始转换 " );
                
    while  (mq.Count  >   0 // 当算式队列没用完则执行
                {
                    
    if  (opreater.ContainsKey(mq.Peek())  ==   true // 如果下一个字符是操作符的话执行
                    {
                        
    if  (mq.Peek()  ==   ' ) ' // 如果为右括号,则弹出所有元素,直到遇到一个与之相对应的左括号
                        {
                            mq.Dequeue(); 
    // 让右括号弹出,它已经没什么用了

                            
    while  (opreaters.Count  >   0 )
                            {
                                
    if  (opreaters.Peek()  ==   ' ( ' // 如果遇到了左括号,则不打印,直接弹出
                                {
                                    opreaters.Pop();

                                    
    break ;
                                }
                                
    else
                                {
                                    Console.Out.Write(opreaters.Pop() 
    +   "   " );  // 不是左括号则继续弹出打印
                                }
                            }
                        }
                        
    else   if  (opreaters.Count  ==   0   ||  opreater[mq.Peek()]  >  opreater[opreaters.Peek()]  ||  mq.Peek()  ==   ' ( ' // 如果栈为空或者操作符优先级高,则入栈
                        {
                            opreaters.Push(mq.Dequeue());
                            
    continue ;
                        }
                        
    else   // 如果操作符优先级相等或者比较低,则输出所有操作符知道遇到左括号
                        {
                            
    if  (opreaters.Peek()  !=   ' ( ' // 这个程序写的逻辑性不太好,写完了到很难在回头分析了,大家不要学我,最忌讳这样了
                            {
                                Console.Out.Write(opreaters.Pop() 
    +   "   " );
                            }
                            
    while  (opreaters.Count  !=   0   &&  opreater[mq.Peek()]  >=  opreater[opreaters.Peek()])  // 如果遇见其他操作符时则弹出打印,直到遇见更低的操作符
                            {
                                
    if  (opreaters.Peek()  ==   ' ( ' // 如果为左括号则直接弹出不打印
                                {
                                    opreaters.Pop();
                                    
    break ;
                                }
                                
    else   // 打印直到遇到左括号
                                {
                                    Console.Out.Write(opreaters.Pop() 
    +   "   " );
                                    
    if  (opreaters.Count  !=   0   &&  opreater[mq.Peek()]  <  opreater[opreaters.Peek()])
                                    {
                                        Console.Out.Write(opreaters.Pop() 
    +   "   " );
                                    }
                                }
                            }


                            opreaters.Push(mq.Dequeue()); 
    // 最后,将当前操作符入栈
                        }
                    }
                    
    else
                    {
                        Console.Write(mq.Dequeue() 
    +   "   " );
                    }
                }

                
    // 读完数据,则将栈内元素全部弹出
                 while  (opreaters.Count  !=   0 )
                {
                    Console.Write(opreaters.Pop() 
    +   "   " );
                }
            }

        上面这段代码按照总结的那些方法写出来的,注意,它并没有错误检测,如果括号不成对,就会出错,假设所有的输入均合法,则所有右括号遇完之后,栈中也就没有左括号了,所以最后一个输出循环并没有检测左括号。

        程序首先用一个字典(键值对集合)来存放四个运算符的优先级,而输入的字符串则转储到队列,方便while循环进行比对,当然,不用队列而用for循环也可以,这里主要考虑给队列也练练。

        程序写的不是很好,也不规范,大家只要自己动手写一下就明白了。

        现在我们已经实现了从中缀式转为后缀式了,紧接着来实现计算部分。
    示例 3:     

    private   void  stack()
    {
        Dictionary
    < char int >  opreater  =   new  Dictionary < char int > ();   // 这个用来存放操作符和他们的优先级

        
    // 3最高
        opreater.Add( ' + ' 1 );
        opreater.Add(
    ' - ' 1 );
        opreater.Add(
    ' * ' 2 );
        opreater.Add(
    ' / ' 2 );
        opreater.Add(
    ' ( ' 3 );
        opreater.Add(
    ' ) ' 3 );


        
    string  m  =  Console.ReadLine();  // 读取一个算式

        Stack
    < char >  opreaters  =   new  Stack < char > ();  // 这个栈用来存放操作符
        Stack < int >  numStack  =   new  Stack < int > ();  // 这个栈又来存放算数
        Queue < char >  mq  =   new  Queue < char > ();  // 这个队列存放算式
        
    // 将算式字符串的字符一个个插入队列
         for  ( int  i  =   0 ; i  <  m.Length; i ++ )
        {
            mq.Enqueue(m[i]);
        }


        
    // 开始将中缀转换为后缀算式
        Console.WriteLine( " 开始转换 " );
        
    string  nums  =   "" // 存放数字的字符串

        
    while  (mq.Count  >   0 // 当算式队列没用完则执行
        {               
            

            
    if  (opreater.ContainsKey(mq.Peek())  ==   true // 如果下一个字符是操作符的话执行
            {
                
    if  (nums  !=   "" )
                {
                    
    int  num  =   int .Parse(nums);  // 将数字字符串转为整形
                    nums  =   "" ;
                    numStack.Push(num); 
    // 将这个数字入栈
                }
                
    if  (mq.Peek()  ==   ' ) ' // 如果为右括号,则弹出所有元素,直到遇到一个与之相对应的左括号
                {
                    mq.Dequeue(); 
    // 让右括号弹出,它已经没什么用了

                    
    while  (opreaters.Count  >   0 )
                    {
                        
    if  (opreaters.Peek()  ==   ' ( ' // 如果遇到了左括号,则不打印,直接弹出
                        {                                
                            opreaters.Pop();
                            
    break ;
                        }
                        
    else
                            suan(opreaters.Pop(), 
    ref  numStack);
                    }
                }
                
    else   if  (opreaters.Count  ==   0   ||  opreater[mq.Peek()]  >  opreater[opreaters.Peek()]  ||  mq.Peek()  ==   ' ( ' // 如果栈为空或者操作符优先级高,则入栈
                {
                    opreaters.Push(mq.Dequeue());
                    
    continue ;
                }
                
    else   // 如果操作符优先级相等或者比较低,则输出所有操作符直到遇到左括号
                {
                    
    if  (opreaters.Peek()  !=   ' ( ' // 这个程序写的逻辑性不太好,写完了到很难在回头分析了,大家不要学我,最忌讳这样了
                        suan(opreaters.Pop(),  ref  numStack);

                    
    while  (opreaters.Count  !=   0   &&  opreater[mq.Peek()]  >=  opreater[opreaters.Peek()])  // 如果遇见其他操作符时则弹出打印,直到遇见更低的操作符
                    {
                        
    if  (opreaters.Peek()  ==   ' ( ' // 如果为左括号则直接弹出不打印
                        {
                            opreaters.Pop();
                            
    break ;
                        }
                        
    else   // 打印直到遇到左括号
                        {
                            suan(opreaters.Pop(), 
    ref  numStack);

                            
    if  (opreaters.Count  !=   0   &&  opreater[mq.Peek()]  <  opreater[opreaters.Peek()])
                            {
                                suan(opreaters.Pop(), 
    ref  numStack);

                            }
                        }
                    }


                    opreaters.Push(mq.Dequeue()); 
    // 最后,将当前操作符入栈
                }
            }
            
    else                     
                nums 
    +=  mq.Dequeue();  // 提取字符
        }


        
    while  (opreaters.Count  !=   0 )
        {
            
    if  (nums  !=   "" // 判断算数字符串是否为空
            {
                
    int  num  =   int .Parse(nums);  // 将数字字符串转为整形
                nums  =   "" ;
                numStack.Push(num);
            }
            suan (opreaters.Pop(),
    ref  numStack);                

        }
        
    // 读完数据,则将栈内元素全部弹出
        Console.Write(numStack.Pop());
    }

    ///   <summary>
    ///  按照运算符运算两个操作数
    ///   </summary>
    ///   <param name="opt"> 运算符 </param>
    ///   <param name="numStack"> 算数栈 </param>
    private   void  suan( char  opt, ref  Stack < int >  numStack)
    {
        
    int  i  =   0 ;
        
    int  j  =   0 ;
        
    switch  (opt)
        {
            
    case   ' + ' :
                i 
    =  numStack.Pop();
                j 
    =  numStack.Pop(); 
                numStack.Push(j 
    +  i);  // 将运算结果入栈
                 break ;
            
    case   ' - ' :
                i 
    =  numStack.Pop();
                j 
    =  numStack.Pop();
                numStack.Push(j 
    -  i);
                
    break ;
            
    case   ' * ' :
                i 
    =  numStack.Pop();
                j 
    =  numStack.Pop();
                numStack.Push(j 
    *  i);
                
    break ;
            
    case   ' / ' :
                i 
    =  numStack.Pop();
                j 
    =  numStack.Pop();
                numStack.Push(j 
    /  i);
                
    break ;
        }
    }

        这段代码只不过比 示例2 多了个计算工能,其他代码完全一样。

        在 示例2 原有的基础上,多了一个栈,这个栈是用来存放操作数的。将示例二中所有输出操作数的地方,全部换成了计算操作数,每次计算的时候,都是对两个操作数进行计算的,函数suan就是负责计算的,把它给单独提出来了。

        大家动手写后,就掌握了科学计算式的方法了,顺便也搞清楚栈的用途了。

    补充:
         其实,栈最普遍最重要的作用还是体现在函数调用中,这就是为什么每次调试程序的时候,总有个“调用堆栈”的窗口显示一些不知所云的东东。
  •     在运行一个函数的时候,其局部变量都会被寄存在cpu的寄存器中(计算是在cpu中完成,而cpu是对它的那些寄存器进行操作,而不是直接在内存中),当这个函数内又调用另外一个函数时,它的局部变量会在寄存器中把外部函数的局部变量给占据,当这个函数调用完毕,主函数的局部变量岂不是完蛋了。这个时候栈就起到大作用了。

        栈内每个元素均为已经调用但并没有返回函数的描述(就假当一个元素是一个函数的所有局部变量吧,具体情况我也不太清楚),而栈顶(活动记录(activation record) 或称为 栈帧(stack frame))即为当前环境,即当前的函数描述。这样,在层层调用函数并返回后,函数调用者的变量就都又恢复了,这点在递归中尤为明显,递归就是一层又一层的跟洋葱皮似的,一直剥洋葱皮,剥完后,还得再把刚才剥掉的那些从里往外再数一便。

        调用堆栈现在大概的知道是怎么一回事了,现在说说尾递归,什么是尾递归,跟名字一样,就是函数的那个调用自己的递归语句在函数体的末尾,也就是这个递归语句最终走完,紧接着下一步就是函数体的结束了。

        尾递归是种极差的递归,因为每次将要执行递归语句的时候,前面的变量可以说是已经用不着了,但是按照调用堆栈的原则,它们还会被存在调用堆栈里,如果递归足够多的话,栈说不定就会溢出,程序就崩溃了。

    ps:这篇文章写的累死了,基本上都是我所理解的全部,哪位高手发现错误请尽快指正。