摘 要棧是一種非常重要的數據結構遞歸函數調用都離不開棧對n個元素入棧和出棧的研究是棧的一個主要研究內容利用二叉樹給出了入棧和出棧序列的表示給出了由前置棧序列構造出二叉樹的算法證明了對於按次序入棧的n個元素其出棧序列總數為C（nn)／(n+)對三種求解出棧序列算法進行了分析和研究並提出一種時間復雜度為O( n)判斷某一序列是否為出棧序列的算法它提高了程序的執行效率
關鍵詞出棧序列Catalan數二叉樹
中圖分類號TP． 文獻標識碼A 文章編號X( )
引 言
已知集合N ={…n}如果按給定的次序…n依次人棧出棧的序列共有多少種?如何給出全部的解?如何判斷某一序列是否為出棧序列?對於這幾個問題文獻[～] 對其進行了分析和研究在此基礎上提出一種用二叉樹來表示人棧和出棧序列求得出棧序列總數以及利用棧的性質判斷某一序列是否為出棧序列還給出一種比文獻[]所提算法執行時間更短的程序
出棧序列的總數
由文獻 [ ～ ] 可知出棧序列總共有C(nn)／(n+)種它是一個Catalan數文獻[]利用n×n的矩形方格 設其左下角坐標為( )右上角坐標為(nn)求從() 到(nn)的路徑數要求中途所經過的點(ab)滿足a≤ b且僅能向右和向上行走文獻[]利用在出棧序列的位置結合Catalan性質而求出文獻[]證明了前序序列為…n的二叉樹其中序序列即為出棧序列再由二叉樹的性質求出棧序列總數
[] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22744.html
