2014年，CCF推出CSP認(rèn)證 （Certified Softwmare Professional， 軟件能力認(rèn)證），以評(píng)價(jià)計(jì)算機(jī)專業(yè)人士或準(zhǔn)專業(yè)人士計(jì)算機(jī)科學(xué)的基礎(chǔ)能力——算法和編程能力。CSP每年舉辦3次，現(xiàn)已成為一些企業(yè)及許多大學(xué)評(píng)價(jià)計(jì)算機(jī)專業(yè)大學(xué)生專業(yè)能力的重要工具。

這是CSP2021初賽的一道選擇題：

對(duì)于入棧順序?yàn)閍， b， c， d， e的序列，下列（）不是合法的出棧序列。

A. a，b，c，d，e

B.e，d，c，b，a

C.b，a，c，d，e

D.c，d，a，e，b

棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱為棧頂，相對(duì)的，把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素;從一個(gè)棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素。

進(jìn)棧出棧就像一個(gè)盒子，先一個(gè)個(gè)放入盒內(nèi)，而拿出的時(shí)候只有先從上面拿，才能再拿下面。入棧的順序規(guī)律是排在前面的先進(jìn)，排在后面的后進(jìn)。出棧所遵循的原則是“先進(jìn)后出”，基于這個(gè)原則可以引出一類問題，即出棧序列問題。

解析順序的問題，如果學(xué)過編譯原理，比較容易理解，解析格式的時(shí)候，是用堆棧的，遇到一個(gè)格式描述符，就壓棧，遇到一個(gè)變量，就出棧，就有了這樣的表現(xiàn)。

同線性表一樣，也有兩種方式來(lái)存儲(chǔ)棧，一是順序存儲(chǔ)，二是鏈?zhǔn)酱鎯?chǔ)。對(duì)于順序存儲(chǔ)，大家自然能想到的是利用數(shù)組。但數(shù)組的容量不易擴(kuò)張，加上棧在使用過程中所需的最大空間大小很難估計(jì)，因此，合理的做法是：先為棧分配一個(gè)基本容量，然后在應(yīng)用過程中，當(dāng)棧的空間不夠時(shí)，再逐段擴(kuò)大。因此需要為棧尋找一個(gè)地址標(biāo)志來(lái)定位，即棧尾指針，同時(shí)用棧頂指針來(lái)表示棧元素的存取情況。

回到這個(gè)問題，依據(jù)“先進(jìn)后出”的規(guī)則，需要出棧元素的要最后進(jìn)棧。

選項(xiàng)A合法，a入棧a出棧;b入棧b出棧;c入棧c出棧的順序依次進(jìn)行。

選項(xiàng)B合法，a，b，c，d，e依次入棧;e，d，c，b，a依次出棧。

選項(xiàng)C合法，a，b入棧，b，a出棧;c入棧c出棧;d入棧d出棧;e入棧e出棧。

選項(xiàng)D不合法，根據(jù)要求c要出棧，那么就需要a，b，c入棧，c出棧，此時(shí)棧中剩b，a;d入棧d出棧，此時(shí)棧中剩b，a;接下來(lái)需要a出棧，但是現(xiàn)在a上面還有b，所以D不合法。

選D。