也談出棧序列的計算

摘要:在《數據結構》的教學中，采用類模板作為抽象數據類型的實現技術，能極大地方便抽象數據類型的實現和應用。通過教案設計可以為教學增添趣味，為實踐增添成果，還可以為一些經典難題提供較好的解決方案。該文給出了《數據結構》的一個典型教案，基于棧類模板解決了求解所有出棧序列的問題。

關鍵詞:數據結構;抽象數據類型;棧類模板;出棧序列

中圖分類號:TP301文獻標識碼:A文章編號: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 問題描述與分析

實際上，棧的教學難點在于棧的應用。棧結構有許多有趣的練習，如“數值轉換”、“括號匹配”等都是一個棧的應用，如“中綴表達式求值”等是兩個棧的應用。

出棧序列問題是一個有趣的經典難題，至今還有很多文章討論。設一個棧的進棧序列為1，2，…，N，進棧的過程中允許出棧， 問有哪些出棧序列。表1列出了當N=3，4，5時，所有的出棧序列。

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

在教學實踐的探索中，我認為棧類模板提供了一個描述、存儲棧的變換過程的手段。棧不僅可以存儲簡單數據元素(如整數)，還可以存儲若干整數棧，每個整數棧表示了問題中的棧在進棧出棧過程中的一個狀態。

2 棧的類模板

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

template

class SeqStack

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

int m_Top;// 棧頂指針

public:

SeqStack( );// 構造函數

SeqStack(SeqStack Q); // 拷貝構造函數

~SeqStack( ); // 析構函數

void Push(T e); // 進棧

T Pop( ); // 出棧

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

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

};

3 核心數據結構和算法思路

定義棧s，其中元素為整數，用于模擬整數進棧出棧中的任意一個狀態，整數序列{1，2，…，n}將依次進入棧s。設計棧S，其中元素為整數棧，用于模擬、記錄n個元素的進棧出棧過程的每個棧的狀態。棧s稱為小棧，棧S稱為大棧。

算法思路是:模擬了一個小棧的狀態變換的所有可能過程。面對小棧的任何一個狀態，可以執行兩種操作:①若小棧存在下一個未進棧的整數，則將下一個整數進小棧;②若小棧不為空，則將小棧的棧頂整數出棧。

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

4 算法描述

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

①初始狀態:將1進小棧s，小棧s進大棧 S;

②若大棧S為空，則算法結束，Outputs中存儲了算法結果;否則，循環執行以下步驟:

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

④若s的進棧次數等于N，且s為空， 則s的輸出序列添加到Outputs之中，轉②;

⑤若s的進棧次數小于N，則復制s對象，對新對象進行進棧操作，并將新對象進入大棧S;

⑥若s不空，則復制s對象，對新對象進行出棧操作，并將新對象進入大棧S。

5 算法實現

為便于實現算法，對棧類模板做了些許補充，增加兩個成員函數，如下所示:

template

class SeqStack

{

public:

int GetPushCount( ); // 返回已執行進棧操作的次數

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

…

};

以下是算法實現，可以幫助讀者更準確地理解求解過程。

vector > GetAllOutput(int n)

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

SeqStack s;// 小棧

SeqStack > S;// 大棧

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

while(!S.isEmpty())

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

int k=s.GetPushCount();// k是小棧s已執行進棧操作的次數

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 結束語

以上教學案例是在《數據結構》精品課程建設中，與同事、學生相互切磋、相互交流的部分成果，還有待改進，在此拋磚引玉。筆者感到《數據結構》課程的無窮魅力在于每個章節中的抽象數據類型，這些抽象類型的定義、實現是《數據結構》課程的基本目標，而將每一個抽象數據類型擴展，并用于解決更多的實際問題，則是一件創造性的工作，需要教師們長期不懈的努力。

參考文獻:

[1] 吉根林，陳波，王瓊，等.數據結構[M].北京:清華大學出版社，2009.

[2] 李紅衛，徐亞平，出棧序列的研究[J].計算機技術與發展，2007(10).

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

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