也談出棧序列的計(jì)算

摘要:在《數(shù)據(jù)結(jié)構(gòu)》的教學(xué)中，采用類模板作為抽象數(shù)據(jù)類型的實(shí)現(xiàn)技術(shù)，能極大地方便抽象數(shù)據(jù)類型的實(shí)現(xiàn)和應(yīng)用。通過(guò)教案設(shè)計(jì)可以為教學(xué)增添趣味，為實(shí)踐增添成果，還可以為一些經(jīng)典難題提供較好的解決方案。該文給出了《數(shù)據(jù)結(jié)構(gòu)》的一個(gè)典型教案，基于棧類模板解決了求解所有出棧序列的問(wèn)題。

關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu);抽象數(shù)據(jù)類型;棧類模板;出棧序列

中圖分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)36-10276-02

To Research How to Compute the Order of POP Stack

LI Cheng

(Taizhou College， Nanjing Normal University， Taizhou 225300， China)

Abstract: In teaching of \"Data struct\"， use class formwork to realize the category of abstract data， can enormitily realize and apply the category of abstract data. By design the lessen plan to add interest to teach， add achievements to practice， and supply solution to some classic tough questions. The paper give a classic lesson plan of \"Data struct\"， use use class formwork to solve the question of the pop stack order.

Key words: data struct; the category of abstract data; class formwork of stack; the order of pop stack

1 問(wèn)題描述與分析

實(shí)際上，棧的教學(xué)難點(diǎn)在于棧的應(yīng)用。棧結(jié)構(gòu)有許多有趣的練習(xí)，如“數(shù)值轉(zhuǎn)換”、“括號(hào)匹配”等都是一個(gè)棧的應(yīng)用，如“中綴表達(dá)式求值”等是兩個(gè)棧的應(yīng)用。

出棧序列問(wèn)題是一個(gè)有趣的經(jīng)典難題，至今還有很多文章討論。設(shè)一個(gè)棧的進(jìn)棧序列為1，2，…，N，進(jìn)棧的過(guò)程中允許出棧， 問(wèn)有哪些出棧序列。表1列出了當(dāng)N=3，4，5時(shí)，所有的出棧序列。

當(dāng)n較大時(shí)，計(jì)算所有的出棧序列就不是易事了。有文獻(xiàn)[2]總結(jié)了數(shù)種算法，驗(yàn)證某一序列是否為出棧序列;有文獻(xiàn)[3]提出先計(jì)算所有數(shù)據(jù)的全排列，再逐個(gè)加以識(shí)別其合理性，或給出遞歸算法，但語(yǔ)焉不詳、程序繁雜;還有文獻(xiàn)[4]試圖從出棧序列的公式化規(guī)則出發(fā)進(jìn)行求解。筆者認(rèn)為這些文獻(xiàn)都沒(méi)有從程序設(shè)計(jì)的角度，給出該問(wèn)題合理的、便于推廣應(yīng)用的解答。

在教學(xué)實(shí)踐的探索中，我認(rèn)為棧類模板提供了一個(gè)描述、存儲(chǔ)棧的變換過(guò)程的手段。棧不僅可以存儲(chǔ)簡(jiǎn)單數(shù)據(jù)元素(如整數(shù))，還可以存儲(chǔ)若干整數(shù)棧，每個(gè)整數(shù)棧表示了問(wèn)題中的棧在進(jìn)棧出棧過(guò)程中的一個(gè)狀態(tài)。

2 棧的類模板

以下是順序棧的類模板定義。

template

class SeqStack

{ T m_Data[StackSize];// 存放棧元素的數(shù)組

int m_Top;// 棧頂指針

public:

SeqStack( );// 構(gòu)造函數(shù)

SeqStack(SeqStack Q); // 拷貝構(gòu)造函數(shù)

~SeqStack( ); // 析構(gòu)函數(shù)

void Push(T e); // 進(jìn)棧

T Pop( ); // 出棧

T GetTop( );// 取棧頂元素(不出棧)

bool isEmpty( );// 判斷棧是否為空

};

3 核心數(shù)據(jù)結(jié)構(gòu)和算法思路

定義棧s，其中元素為整數(shù)，用于模擬整數(shù)進(jìn)棧出棧中的任意一個(gè)狀態(tài)，整數(shù)序列{1，2，…，n}將依次進(jìn)入棧s。設(shè)計(jì)棧S，其中元素為整數(shù)棧，用于模擬、記錄n個(gè)元素的進(jìn)棧出棧過(guò)程的每個(gè)棧的狀態(tài)。棧s稱為小棧，棧S稱為大棧。

算法思路是:模擬了一個(gè)小棧的狀態(tài)變換的所有可能過(guò)程。面對(duì)小棧的任何一個(gè)狀態(tài)，可以執(zhí)行兩種操作:①若小棧存在下一個(gè)未進(jìn)棧的整數(shù)，則將下一個(gè)整數(shù)進(jìn)小棧;②若小棧不為空，則將小棧的棧頂整數(shù)出棧。

當(dāng)小棧已將所有n個(gè)整數(shù)進(jìn)棧，并全部出棧之時(shí)，即得到一個(gè)合法的出棧序列;當(dāng)每個(gè)步驟中小棧的兩種操作都已完成，則獲得了所有的出棧序列。因此算法思路的本質(zhì)，相當(dāng)于對(duì)一個(gè)二叉判定樹(shù)的遍歷。

4 算法描述

以下算法窮舉了進(jìn)棧序列是{1， 2， ……， N}的所有出棧序列，將結(jié)果存于向量Outputs之中。

①初始狀態(tài):將1進(jìn)小棧s，小棧s進(jìn)大棧 S;

②若大棧S為空，則算法結(jié)束，Outputs中存儲(chǔ)了算法結(jié)果;否則，循環(huán)執(zhí)行以下步驟:

③大棧S出棧，得到原棧頂元素，存于變量s中;

④若s的進(jìn)棧次數(shù)等于N，且s為空， 則s的輸出序列添加到Outputs之中，轉(zhuǎn)②;

⑤若s的進(jìn)棧次數(shù)小于N，則復(fù)制s對(duì)象，對(duì)新對(duì)象進(jìn)行進(jìn)棧操作，并將新對(duì)象進(jìn)入大棧S;

⑥若s不空，則復(fù)制s對(duì)象，對(duì)新對(duì)象進(jìn)行出棧操作，并將新對(duì)象進(jìn)入大棧S。

5 算法實(shí)現(xiàn)

為便于實(shí)現(xiàn)算法，對(duì)棧類模板做了些許補(bǔ)充，增加兩個(gè)成員函數(shù)，如下所示:

template

class SeqStack

{

public:

int GetPushCount( ); // 返回已執(zhí)行進(jìn)棧操作的次數(shù)

vector Output() ; // 返回已出棧的數(shù)據(jù)序列

…

};

以下是算法實(shí)現(xiàn)，可以幫助讀者更準(zhǔn)確地理解求解過(guò)程。

vector > GetAllOutput(int n)

{vector > Outputs; // 存儲(chǔ)所有出棧序列的向量

SeqStack s;// 小棧

SeqStack > S;// 大棧

s.Push(1);S.Push(s);// 步驟①

while(!S.isEmpty())

{s=S.Pop(); // 步驟③

int k=s.GetPushCount();// k是小棧s已執(zhí)行進(jìn)棧操作的次數(shù)

if(k==n s.isEmpty()) // 步驟④

{vector v1=s.Output();Outputs.push_back(v1); continue;}

if(k

{SeqStack s1=s; s1.Push(k+1); S.Push(s1); }

if(!s.isEmpty()) // 步驟⑥

{SeqStack s2=s; s2.Pop(); S.Push(s2); }

}

return Outputs;

}

6 結(jié)束語(yǔ)

以上教學(xué)案例是在《數(shù)據(jù)結(jié)構(gòu)》精品課程建設(shè)中，與同事、學(xué)生相互切磋、相互交流的部分成果，還有待改進(jìn)，在此拋磚引玉。筆者感到《數(shù)據(jù)結(jié)構(gòu)》課程的無(wú)窮魅力在于每個(gè)章節(jié)中的抽象數(shù)據(jù)類型，這些抽象類型的定義、實(shí)現(xiàn)是《數(shù)據(jù)結(jié)構(gòu)》課程的基本目標(biāo)，而將每一個(gè)抽象數(shù)據(jù)類型擴(kuò)展，并用于解決更多的實(shí)際問(wèn)題，則是一件創(chuàng)造性的工作，需要教師們長(zhǎng)期不懈的努力。

參考文獻(xiàn):

[1] 吉根林，陳波，王瓊，等.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，2009.

[2] 李紅衛(wèi)，徐亞平，出棧序列的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007(10).

[3] 徐鳳生.出棧序列的性質(zhì)及其求解新算法[J].計(jì)算機(jī)工程與應(yīng)用，2006(5).

[4] 何坤金，陳正鳴，楊垠.基于算子的棧序列生成算法與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006(6).