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

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

對于入棧順序為a， 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）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對的，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入?；驂簵＃前研略胤诺綏ｍ斣氐纳厦?，使之成為新的棧頂元素;從一個棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素。

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

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

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

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

選項A合法，a入棧a出棧;b入棧b出棧;c入棧c出棧的順序依次進行。

選項B合法，a，b，c，d，e依次入棧;e，d，c，b，a依次出棧。

選項C合法，a，b入棧，b，a出棧;c入棧c出棧;d入棧d出棧;e入棧e出棧。

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

選D。