不可一日無煙卷

棧是一種后進(jìn)后出機(jī)制，它只允許訪問訪問一個(gè)數(shù)據(jù)項(xiàng)，即 棧頂（最后插入的數(shù)據(jù)項(xiàng)）。它有主要的三種操作：push,向棧內(nèi)壓入值；pop,彈出棧頂?shù)闹担捶祷貤ｍ數(shù)闹担阉鼜臈?nèi)刪除；peek,只返回但不刪除棧頂。 棧普遍應(yīng)用于編譯器、文本檢測(cè)、科學(xué)計(jì)算等等，在編譯器中，它用來檢測(cè)一個(gè)函數(shù)體等是否為封閉的（括號(hào)是否成對(duì)等等），在文本檢測(cè)中，想想你的vs，如果最后沒有大括號(hào)它就會(huì)檢測(cè)出來，和編譯器中一樣，在科學(xué)計(jì)算中，就像商店能買到的那些高級(jí)計(jì)算器，輸入一個(gè)算式可以直接計(jì)算出來結(jié)果，而不像普通計(jì)算器中，只能輸入數(shù)字，然后在按鍵一步一步計(jì)算，以上這些應(yīng)用場(chǎng)景，歸根結(jié)底都是對(duì)文本的檢測(cè)，現(xiàn)在知道棧的用途了吧，后面將結(jié)合隊(duì)列一起練練手............................

棧stack    
    棧是一種后進(jìn)后出機(jī)制，它只允許訪問訪問一個(gè)數(shù)據(jù)項(xiàng)，即 棧頂（最后插入的數(shù)據(jù)項(xiàng)）。它有主要的三種操作：push,向棧內(nèi)壓入值；pop,彈出棧頂?shù)闹担捶祷貤ｍ數(shù)闹担阉鼜臈?nèi)刪除；peek,只返回但不刪除棧頂。
    
    概念很容易理解，無非就像給彈匣壓子彈等等這種類比，但是像我這樣的新手在剛接觸到棧的時(shí)候總是很迷茫，認(rèn)為它很難，其實(shí)這只是錯(cuò)覺，主要是因?yàn)闆]有搞清楚棧主要用在那些場(chǎng)景。

    棧普遍應(yīng)用于編譯器、文本檢測(cè)、科學(xué)計(jì)算等等，在編譯器中，它用來檢測(cè)一個(gè)函數(shù)體等是否為封閉的（括號(hào)是否成對(duì)等等），在文本檢測(cè)中，想想你的vs，如果最后沒有大括號(hào)它就會(huì)檢測(cè)出來，和編譯器中一樣，在科學(xué)計(jì)算中，就像商店能買到的那些高級(jí)計(jì)算器，輸入一個(gè)算式可以直接計(jì)算出來結(jié)果，而不像普通計(jì)算器中，只能輸入數(shù)字，然后在按鍵一步一步計(jì)算，以上這些應(yīng)用場(chǎng)景，歸根結(jié)底都是對(duì)文本的檢測(cè)，現(xiàn)在知道棧的用途了吧，后面將結(jié)合隊(duì)列一起練練手。

隊(duì)列queue
    顧名思義，就是一堆東西成隊(duì)排列了，它是先進(jìn)先出機(jī)制(FIFO)與棧相反，棧是后進(jìn)后出(LIFO)。它的主要操作有：Enqueue,向隊(duì)尾添加值；Dequeue,返回并移除對(duì)頭的值；peek,返回但不移除對(duì)頭的值。

    隊(duì)列很容易理解，它主要應(yīng)用在網(wǎng)絡(luò)通信、系統(tǒng)等。windows的所有事件都是放在隊(duì)列里面的。

    最典型的，就是系統(tǒng)的任務(wù)分配了，每個(gè)進(jìn)程或線程都分配在某些隊(duì)列里，方便cpu時(shí)間片的分配調(diào)度，任務(wù)的運(yùn)行不可能是你最后打開的程序先運(yùn)行吧，當(dāng)然它有優(yōu)先級(jí)，這個(gè)排除在外。

棧的應(yīng)用
    現(xiàn)在搞清楚了棧和隊(duì)列的應(yīng)用場(chǎng)景，那就趁熱打鐵，練練手。

    現(xiàn)在，按部就班的實(shí)現(xiàn)一個(gè)科學(xué)表達(dá)式的計(jì)算。

    首先了解一下計(jì)算機(jī)是怎么計(jì)算類似于 1*(2+3)+4/2 這樣的計(jì)算。對(duì)于大腦來說，這個(gè)算式簡(jiǎn)單到不能再簡(jiǎn)單了，但是電腦卻不是如此，得讓它明白那個(gè)先算，那個(gè)后算，以及哪些是操作符（運(yùn)算符）哪些不是（例如括號(hào)）。

    像我們經(jīng)常使用的這種算式稱為 中綴式 ，就是運(yùn)算符都在兩個(gè)操作符中間了，這種中綴式對(duì)于我們?nèi)四X來說，并不是順序執(zhí)行的，它可以從中間先開始，比如1+2*3 ，這正是電腦很難理解中綴式的原因，因?yàn)樗偸琼樞驁?zhí)行的。那么，我們就得把中綴式換成 后綴式(postfix)  或稱作 逆波蘭記法(reverse Polish notation)。

    中綴式就是把運(yùn)算符放到兩個(gè)操作數(shù)后邊，讓算式保持順序計(jì)算（對(duì)于我們?nèi)四X也是如此）。具體怎么放，大家看看下面的例子就明白了。
     
     示例 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 * +

    結(jié)合上邊的示例，會(huì)發(fā)現(xiàn)后綴式并沒有描述優(yōu)先級(jí)的括號(hào)，這是因?yàn)槔ㄌ?hào)并不是運(yùn)算符。大家在自己動(dòng)手做兩個(gè)，就掌握這種方法了。
    
    程序中如何實(shí)現(xiàn)這種轉(zhuǎn)換呢？那就要依靠強(qiáng)大的棧了。

中追到后綴的轉(zhuǎn)換 
   

當(dāng)讀到一個(gè)操作數(shù)時(shí)，立即把它放到輸出中，即顯示出來。操作符不立即輸出，從而必須先存在某個(gè)地方，例如棧或變量。當(dāng)遇到一個(gè)左括號(hào)時(shí)也把它放入棧中。計(jì)算是從一個(gè)初始化為空的棧開始。

如果棧為空，則將符號(hào)入棧。

如果遇見一個(gè)右括號(hào)，那么就將棧元素彈出并輸出，直到遇到一個(gè)（相對(duì)應(yīng)的）左括號(hào)，但是這個(gè)左括號(hào)只彈出，并不輸出。

如果遇見優(yōu)先級(jí)與棧首元素相同或比較低的符號(hào)，則將棧的所有元素彈出并輸出，直到遇見一個(gè)左括號(hào)為止，這個(gè)左括號(hào)只彈出，并不輸出，最后，將遇到的那個(gè)符號(hào)入棧。

如果遇見優(yōu)先級(jí)與棧首元素高的符號(hào)（右括號(hào)除外），則把它入棧。

如果遇見右括號(hào)，則彈出并輸出所有元素，直到遇到一個(gè)與之相對(duì)應(yīng)的左括號(hào)，這個(gè)左括號(hào)只彈出不輸出。

如果讀到末尾了，則將棧中元素彈出并輸出，直到棧為空，左括號(hào)只彈出不顯示

    以上，是我結(jié)合《數(shù)據(jù)結(jié)構(gòu)與算法分析C++描述》相應(yīng)段落和我的實(shí)際經(jīng)驗(yàn)（經(jīng)驗(yàn)并不多）總結(jié)出來的，原書的內(nèi)容很難理解，像我這樣的人，只看書，兩天才明白過來，主要是方法容易，做起來難，尤其是第一次寫這樣的程序，如有什么紕漏或錯(cuò)誤，還請(qǐng)指出。

    下面是實(shí)現(xiàn)中綴轉(zhuǎn)后綴的程序：
    示例 2：

       private void stack()
        {
            Dictionary<char, int> opreater = new Dictionary<char, int>();  //這個(gè)用來存放操作符和他們的優(yōu)先級(jí)

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


            string m = Console.ReadLine(); //讀取一個(gè)算式

            Stack<char> opreaters = new Stack<char>(); //這個(gè)棧用來存放操作符
            Queue<char> mq = new Queue<char>(); //這個(gè)隊(duì)列存放算式
            //將算式字符串的字符一個(gè)個(gè)插入隊(duì)列
            for (int i = 0; i < m.Length; i++)
            {
                mq.Enqueue(m[i]);
            }


            //開始將中綴轉(zhuǎn)換為后綴算式
            Console.WriteLine("開始轉(zhuǎn)換");
            while (mq.Count > 0) //當(dāng)算式隊(duì)列沒用完則執(zhí)行
            {
                if (opreater.ContainsKey(mq.Peek()) == true) //如果下一個(gè)字符是操作符的話執(zhí)行
                {
                    if (mq.Peek() == ')') //如果為右括號(hào)，則彈出所有元素，直到遇到一個(gè)與之相對(duì)應(yīng)的左括號(hào)
                    {
                        mq.Dequeue(); //讓右括號(hào)彈出，它已經(jīng)沒什么用了

                        while (opreaters.Count > 0)
                        {
                            if (opreaters.Peek() == '(') //如果遇到了左括號(hào)，則不打印，直接彈出
                            {
                                opreaters.Pop();

                                break;
                            }
                            else
                            {
                                Console.Out.Write(opreaters.Pop() + " "); //不是左括號(hào)則繼續(xù)彈出打印
                            }
                        }
                    }
                    else if (opreaters.Count == 0 || opreater[mq.Peek()] > opreater[opreaters.Peek()] || mq.Peek() == '(') //如果棧為空或者操作符優(yōu)先級(jí)高，則入棧
                    {
                        opreaters.Push(mq.Dequeue());
                        continue;
                    }
                    else //如果操作符優(yōu)先級(jí)相等或者比較低，則輸出所有操作符知道遇到左括號(hào)
                    {
                        if (opreaters.Peek() != '(') //這個(gè)程序?qū)懙倪壿嬓圆惶茫瑢懲炅说胶茈y在回頭分析了，大家不要學(xué)我，最忌諱這樣了
                        {
                            Console.Out.Write(opreaters.Pop() + " ");
                        }
                        while (opreaters.Count != 0 && opreater[mq.Peek()] >= opreater[opreaters.Peek()]) //如果遇見其他操作符時(shí)則彈出打印，直到遇見更低的操作符
                        {
                            if (opreaters.Peek() == '(') //如果為左括號(hào)則直接彈出不打印
                            {
                                opreaters.Pop();
                                break;
                            }
                            else //打印直到遇到左括號(hào)
                            {
                                Console.Out.Write(opreaters.Pop() + " ");
                                if (opreaters.Count != 0 && opreater[mq.Peek()] < opreater[opreaters.Peek()])
                                {
                                    Console.Out.Write(opreaters.Pop() + " ");
                                }
                            }
                        }


                        opreaters.Push(mq.Dequeue()); //最后，將當(dāng)前操作符入棧
                    }
                }
                else
                {
                    Console.Write(mq.Dequeue() + " ");
                }
            }

            //讀完數(shù)據(jù)，則將棧內(nèi)元素全部彈出
            while (opreaters.Count != 0)
            {
                Console.Write(opreaters.Pop() + " ");
            }
        }

    上面這段代碼按照總結(jié)的那些方法寫出來的，注意，它并沒有錯(cuò)誤檢測(cè)，如果括號(hào)不成對(duì)，就會(huì)出錯(cuò)，假設(shè)所有的輸入均合法，則所有右括號(hào)遇完之后，棧中也就沒有左括號(hào)了，所以最后一個(gè)輸出循環(huán)并沒有檢測(cè)左括號(hào)。

    程序首先用一個(gè)字典（鍵值對(duì)集合）來存放四個(gè)運(yùn)算符的優(yōu)先級(jí)，而輸入的字符串則轉(zhuǎn)儲(chǔ)到隊(duì)列，方便while循環(huán)進(jìn)行比對(duì)，當(dāng)然，不用隊(duì)列而用for循環(huán)也可以，這里主要考慮給隊(duì)列也練練。

    程序?qū)懙牟皇呛芎茫膊灰?guī)范，大家只要自己動(dòng)手寫一下就明白了。

    現(xiàn)在我們已經(jīng)實(shí)現(xiàn)了從中綴式轉(zhuǎn)為后綴式了，緊接著來實(shí)現(xiàn)計(jì)算部分。
示例 3：     

private void stack()
{
    Dictionary<char, int> opreater = new Dictionary<char, int>();  //這個(gè)用來存放操作符和他們的優(yōu)先級(jí)

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


    string m = Console.ReadLine(); //讀取一個(gè)算式

    Stack<char> opreaters = new Stack<char>(); //這個(gè)棧用來存放操作符
    Stack<int> numStack = new Stack<int>(); //這個(gè)棧又來存放算數(shù)
    Queue<char> mq = new Queue<char>(); //這個(gè)隊(duì)列存放算式
    //將算式字符串的字符一個(gè)個(gè)插入隊(duì)列
    for (int i = 0; i < m.Length; i++)
    {
        mq.Enqueue(m[i]);
    }


    //開始將中綴轉(zhuǎn)換為后綴算式
    Console.WriteLine("開始轉(zhuǎn)換");
    string nums = ""; //存放數(shù)字的字符串

    while (mq.Count > 0) //當(dāng)算式隊(duì)列沒用完則執(zhí)行
    {               
        

        if (opreater.ContainsKey(mq.Peek()) == true) //如果下一個(gè)字符是操作符的話執(zhí)行
        {
            if (nums != "")
            {
                int num = int.Parse(nums); //將數(shù)字字符串轉(zhuǎn)為整形
                nums = "";
                numStack.Push(num); //將這個(gè)數(shù)字入棧
            }
            if (mq.Peek() == ')') //如果為右括號(hào)，則彈出所有元素，直到遇到一個(gè)與之相對(duì)應(yīng)的左括號(hào)
            {
                mq.Dequeue(); //讓右括號(hào)彈出，它已經(jīng)沒什么用了

                while (opreaters.Count > 0)
                {
                    if (opreaters.Peek() == '(') //如果遇到了左括號(hào)，則不打印，直接彈出
                    {                                
                        opreaters.Pop();
                        break;
                    }
                    else
                        suan(opreaters.Pop(), ref numStack);
                }
            }
            else if (opreaters.Count == 0 || opreater[mq.Peek()] > opreater[opreaters.Peek()] || mq.Peek() == '(') //如果棧為空或者操作符優(yōu)先級(jí)高，則入棧
            {
                opreaters.Push(mq.Dequeue());
                continue;
            }
            else //如果操作符優(yōu)先級(jí)相等或者比較低，則輸出所有操作符直到遇到左括號(hào)
            {
                if (opreaters.Peek() != '(') //這個(gè)程序?qū)懙倪壿嬓圆惶茫瑢懲炅说胶茈y在回頭分析了，大家不要學(xué)我，最忌諱這樣了
                    suan(opreaters.Pop(), ref numStack);

                while (opreaters.Count != 0 && opreater[mq.Peek()] >= opreater[opreaters.Peek()]) //如果遇見其他操作符時(shí)則彈出打印，直到遇見更低的操作符
                {
                    if (opreaters.Peek() == '(') //如果為左括號(hào)則直接彈出不打印
                    {
                        opreaters.Pop();
                        break;
                    }
                    else //打印直到遇到左括號(hào)
                    {
                        suan(opreaters.Pop(), ref numStack);

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

                        }
                    }
                }


                opreaters.Push(mq.Dequeue()); //最后，將當(dāng)前操作符入棧
            }
        }
        else                    
            nums += mq.Dequeue(); //提取字符
    }


    while (opreaters.Count != 0)
    {
        if (nums != "") //判斷算數(shù)字符串是否為空
        {
            int num = int.Parse(nums); //將數(shù)字字符串轉(zhuǎn)為整形
            nums = "";
            numStack.Push(num);
        }
        suan (opreaters.Pop(),ref numStack);                

    }
    //讀完數(shù)據(jù)，則將棧內(nèi)元素全部彈出
    Console.Write(numStack.Pop());
}

/// <summary>
/// 按照運(yùn)算符運(yùn)算兩個(gè)操作數(shù)
/// </summary>
/// <param name="opt">運(yùn)算符</param>
/// <param name="numStack">算數(shù)棧</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); //將運(yùn)算結(jié)果入棧
            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 多了個(gè)計(jì)算工能，其他代碼完全一樣。

    在 示例2 原有的基礎(chǔ)上，多了一個(gè)棧，這個(gè)棧是用來存放操作數(shù)的。將示例二中所有輸出操作數(shù)的地方，全部換成了計(jì)算操作數(shù)，每次計(jì)算的時(shí)候，都是對(duì)兩個(gè)操作數(shù)進(jìn)行計(jì)算的，函數(shù)suan就是負(fù)責(zé)計(jì)算的，把它給單獨(dú)提出來了。

    大家動(dòng)手寫后，就掌握了科學(xué)計(jì)算式的方法了，順便也搞清楚棧的用途了。

補(bǔ)充：
     其實(shí)，棧最普遍最重要的作用還是體現(xiàn)在函數(shù)調(diào)用中，這就是為什么每次調(diào)試程序的時(shí)候，總有個(gè)“調(diào)用堆棧”的窗口顯示一些不知所云的東東。

    在運(yùn)行一個(gè)函數(shù)的時(shí)候，其局部變量都會(huì)被寄存在cpu的寄存器中（計(jì)算是在cpu中完成，而cpu是對(duì)它的那些寄存器進(jìn)行操作，而不是直接在內(nèi)存中），當(dāng)這個(gè)函數(shù)內(nèi)又調(diào)用另外一個(gè)函數(shù)時(shí)，它的局部變量會(huì)在寄存器中把外部函數(shù)的局部變量給占據(jù)，當(dāng)這個(gè)函數(shù)調(diào)用完畢，主函數(shù)的局部變量豈不是完蛋了。這個(gè)時(shí)候棧就起到大作用了。

    棧內(nèi)每個(gè)元素均為已經(jīng)調(diào)用但并沒有返回函數(shù)的描述（就假當(dāng)一個(gè)元素是一個(gè)函數(shù)的所有局部變量吧，具體情況我也不太清楚），而棧頂（活動(dòng)記錄(activation record) 或稱為 棧幀(stack frame)）即為當(dāng)前環(huán)境，即當(dāng)前的函數(shù)描述。這樣，在層層調(diào)用函數(shù)并返回后，函數(shù)調(diào)用者的變量就都又恢復(fù)了，這點(diǎn)在遞歸中尤為明顯，遞歸就是一層又一層的跟洋蔥皮似的，一直剝洋蔥皮，剝完后，還得再把剛才剝掉的那些從里往外再數(shù)一便。

    調(diào)用堆棧現(xiàn)在大概的知道是怎么一回事了，現(xiàn)在說說尾遞歸，什么是尾遞歸，跟名字一樣，就是函數(shù)的那個(gè)調(diào)用自己的遞歸語句在函數(shù)體的末尾，也就是這個(gè)遞歸語句最終走完，緊接著下一步就是函數(shù)體的結(jié)束了。

    尾遞歸是種極差的遞歸，因?yàn)槊看螌⒁獔?zhí)行遞歸語句的時(shí)候，前面的變量可以說是已經(jīng)用不著了，但是按照調(diào)用堆棧的原則，它們還會(huì)被存在調(diào)用堆棧里，如果遞歸足夠多的話，棧說不定就會(huì)溢出，程序就崩潰了。

ps:這篇文章寫的累死了，基本上都是我所理解的全部，哪位高手發(fā)現(xiàn)錯(cuò)誤請(qǐng)盡快指正。