說在前面

隊列和棧是非常重要的兩種數據結構，教材也安排了大量的篇幅來介紹這兩種數據結構的基本特征和基本操作，因此它們的基本特征和操作肯定是要考的。

但是如何在編程題中考查隊列和棧的應用？它會考到何種難度？我們該教到何種程度？這就讓老師們犯了難。因為涉及到隊列和棧的算法題都不簡單，一不小心就會進入到廣搜和深搜等較為復雜的領域。

【資料圖】

命題老師們一直在模糊的邊界摸索，試圖找到一些既能考查隊列和棧的基本操作，又不涉及復雜算法的案例，絞盡腦汁、用心良苦，為大家在前方趟雷，逐步拓展命題的邊界。

2022年11月溫州一模第15題

一題目二考查知識點

數組、字典、棧的基本操作，自定義函數和查找最值算法。要求學生理解字典的表示方法，熟練掌握棧的基本操作。

三解析本題考查了數組、字典和棧等數據結構、查找最值算法，綜合性相當強，難度較大。

題目的問題是計算拿走幾片圓盤后，能看到的圓盤顏色種數最多？但程序實現并沒有模擬拿走圓盤的過程，而是逆向思維，觀察從下往上逐漸堆疊圓盤時，最多能看到幾種顏色。

為了找到最優(yōu)解，程序構造了一個棧，用來存儲能夠被看到的圓盤編號，因為圓盤入棧的順序是從下往上，為了確保棧中圓盤都能被看到，則其半徑值必須是一個遞減序列。所以每次將編號為i的圓盤入棧時，必須先將半徑小于r[i]的元素退棧。

此外，因為題目要求的不是最多能看到的圓盤數量，而是最多能看到的顏色種類，故相同顏色的圓盤只能算1個。為此程序創(chuàng)建了一個字典f，用來存儲某種顏色對應的圓盤數量。當有元素退棧時，當前可見顏色數量cnum不一定會減少，只有當某種顏色的圓盤數量為0時，才將cnum的值減1。這就是第①空的算法原理。

新圓盤入棧后，cnum的值不一定會加1，只有當f中不包含棧頂圓盤顏色時，才將cnum的值加1，否則只讓該顏色對應的圓盤數量加1。接下來判斷cnum是否為最優(yōu)解，若為最優(yōu)解，則更新存儲最優(yōu)解的變量cmax、res和m——它們分別存儲了最大可見顏色數量、可見顏色種類及其對應圓盤數量（注意不能寫作res=f，否則res與f會指向同一對象）和拿走圓盤的數量。

搞清楚算法原理以后，各問題的答案就呼之欲出了：

圓盤i入棧前，先要將半徑小于r[i]的圓盤出棧，以保持棧中元素的遞減特性。故函數pop()的作用是將半徑小于rad的圓盤出棧，返回新的棧頂指針(top)和可見的顏色數量(cnum)。

color[z[top]]表示棧頂圓盤的顏色，圓盤出棧后，其所屬顏色的圓盤數量要減1，即f[color[z[top]]] -= 1。當該種顏色的圓盤數量為0時，需要將cnum的值減1。由此得到第①空的答案f[color[z[top]]] == 0。

第②空語句的功能是將編號為i的圓盤入棧，即z[top] = i。

第③空是計算被拿走圓盤的數量，因為此時疊放的圓盤數量為(i+1)，故m=n-(i+1)。

為代碼添加注釋如下圖所示：

四答案

（1）將半徑小于rad的圓盤出棧，返回新的棧頂指針(top)和可見的顏色數量(cnum)。

（2）① f[color[z[top]]] == 0

② z[top] = i

③ m=n-(i+1)

五拓展思考

此題程序采用逆序思維，逐個疊加圓盤數量，并通過維護一個遞減棧來記錄可見圓盤編號，以便快速計算可見顏色數量，使用字典f來記錄當前可見顏色種類及其對應圓盤數量信息，構思非常巧妙。

正因為程序的技巧性太強，引入了較多的變量，代碼實現蜿蜒曲折，不夠直觀，增加了閱讀難度，學生得分率很低。

我們也可以采用正向思維，直接模擬拿走圓盤的過程。計算有哪些圓盤可以看到，就好比尋找一個遞增序列。我們通過遍歷r[i:]，尋找以r[i]為首元素的遞增序列；并創(chuàng)建列表c，用c[i]存儲以圓盤i為頂盤時的可見顏色字符串，每當遞增序列中出現一種新顏色的圓盤，將該顏色添加到c[i]中。

當出現最優(yōu)解時，可設置m = i，則不僅可以用m表示拿走圓盤的數量，還可以用c[m]表示最大可見顏色字符串。

實現相關功能的程序代碼如下，請將缺失的代碼補充完整：

r = [5, 8, 4, 6, 3, 9] # 從上向下依次給圓盤編號0,1,2,...

color = ["紅", "橙", "綠", "藍", "紫", "紅"]

n = len(r)

print("序號\t半徑\t顏色\t")

for i in range(1, n+1):

print(f"{i}\t{r[i-1]}\t{color[i-1]}\t")

c = []# c[i]是一個字符串，記錄了以盤子i為頂盤時的可見顏色

m = 0

for i in range(n):

c.append(color[i]) # 記錄能看見的盤子顏色

p = i # 當前能看見的盤子下標

for j in range(i+1, n):# 尋找以r[i]為首元素的遞增序列

if r[j] > r[p]:

p =①

if②:

c[i] += color[j]

if len(c[i]) > len(c[m]):

m = ③

print("拿走", m, "片后,可看到圓盤的顏色種數最多，分別為: ", c[m])

六拓展思考答案

①j

② color[j] not in c[i]

③ m = i

寫在后面

為了保證解析的原創(chuàng)性和思維的獨特性，我都是獨立解題后，先不看答案(除非題目不會做)，直接把解析寫好，再去看答案。

當然，如果發(fā)現參考答案有更好的思路，我還是很樂于學習和借鑒的。同時，由于本人水平有限，解析中難免出現疏漏甚至錯誤之處，敬請諒解。

無論是贊同還是反對我的看法，都請你給我留言。如果你有新的想法，千萬不要憋在心里，請發(fā)出來大家一起討論。讓我們相互學習，共同進步！

需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學習方式

Python算法之旅文章分類

關鍵詞： 基本操作 數據結構