出栈序列生成的算法研究与设计

王防修，周 康

(武汉工业学院数学与计算机学院，湖北武汉430023)

栈的应用非常广泛，诸如电网优化、各种智能算法都需要用到栈。可以说，几乎所有高级算法的程序实现都需要用到栈，没有栈，这些算法的实现将寸步难行。因此，数据结构［1］中栈的学习非常重要。事实上，只有在用栈解决实际问题时才能充分体会栈的作用。虽然栈是一种先进后出的线性表，但什么时候入栈和什么时候出栈不是随意的，而是由实际问题决定的。许多人在学习栈时，由于书中所举例子的局限性，导致许多人对栈的认识比较肤浅，进而使得他们不能灵活任用栈来解决实际问题。所以，笔者希望通过对出栈序列的生成算法［2］介绍和实现来提高大家对栈的认识，最终使大家能够自觉任用栈来解决各种实际问题。

1 问题描述和分析

1.1 问题描述

根据问题的规模由小到大和问题的难度由低到高，可将其归纳为以下两个方面:

(1)有四个元素 a，b，c，d 依次入栈，任何时候都可以出栈，请写出所有可能的出栈序列［3－11］和所有不存在的序列。

(2)有多个元素依次入栈，任何时候都可以出栈，请写出所有可能的出栈序列。

1.2 问题分析

对于问题(1)，由排列组合可知，这4个元素可以组成4!=24个不同的元素序列，并且这些元素序列分别为:abcd;abdc;acbd;acdb;adbc;adcb;bacd;badc;bcad;bcda;bdac;bdca;cabd;cadb;cbad;cbda;cdab;cdba;dabc;dacb;dbac;dbca;dcab;dcba。

由栈的先进后出特性，可以得到所有的出栈序列分别为:abcd;abdc;acbd;acdb;adcb;bacd;badc;bcad;bcda;bdca;cbad;cbda;cdba;dcba。所有不可能的序列为:adbc;bdac;cabd;cadb;cdab;dabc;dacb;dbac;dbca;dcab。

显然，对问题(1)，采用的是穷举法同时又是手工计算的方式得到所有的出栈序列和所有不可能的序列。然而，这种方法只适合入栈元素很少的情况。事实上，当入栈元素有6个时，由于可以组成6!=720个不同的元素序列，如果此时仍采用手工方式计算所有可能的出栈序列，将需要花费大量时间，并且很容易出错。

因此，用手工方式计算问题是不现实的。如果能够发现出栈序列的某种共同规律，在此基础上进而形成一种算法，那么问题(2)就迎刃而解。

2 算法思想及构造

2.1 算法思想

定义1 设n个元素x1，x2，…，xn依次入栈，并且任何时候栈顶元素可以出栈，则得到的一系列出栈元素称为出栈系列。

性质1 如果入栈元素有n个，则需要进行n次入栈操作和n次出栈操作。

性质2 没有入栈就没有出栈，因此入栈操作比出栈操作先发生。

性质3 如果用字符‘1’表示入栈操作和用字符‘0’表示出栈操作，那么得到一个长度为n的出栈序列需要经过一个长度为2n的二进制字符串栈操作序列。

定义2 如果从左往右依次对二进制字符串栈操作序列进行顺序编号，则从第1位到第i位所形成的二进制字符串称为第i位左子串。

性质4 栈操作序列的每一位左子串中字符‘1’的个数不得少于字符‘0’的个数。

证明:如果左子串中字符‘1’的个数少于字符‘0’的个数，那么当栈中的元素全部出栈后，还需要进一步出栈，而此时栈中已经没有元素，因此就会发生出栈错误。

性质5 栈操作序列中字符‘0’的个数与字符‘1’的个数相同。

证明:如果栈操作序列中字符‘0’的个数少于字符‘1’的个数，那么出栈元素的个数就会少于n，从而也就不可能得到出栈序列;反之，如果栈操作序列中字符‘0’的个数多于字符‘1’的个数，就会发生出栈错误，同样得不到出栈序列。

通过对栈操作序列性质的分析，不难发现，栈操作序列与出栈序列存在一一映射的关系。

现在来判断一个长度为8的二进制字符串是否是4个入栈元素的栈操作序列。已知二进制字符串“11001010”，那么该字符串是否是栈操作序列呢?首先，该二进制序列有4个‘1’和4个‘0’，满足性质1、性质3和性质5。其次，该二进制字符串的第一位是‘1’，满足性质2。最后，不难发现，字符串中每一位的左子串中字符‘1’的个数都不少于字符‘0’的个数，满足性质5。因此，该二进制字符串是一个出栈序列。如果依次入栈的四个元素是a，b，c，d，那么由该栈操作序列“11001010”依次执行的栈操作是:a入栈;b入栈;b出栈;a出栈;c入栈;c出栈;d入栈;d出栈。因此，该栈操作序列对应的出栈序列是 bacd。再判断二进制字符串“11000110”是否是栈操作序列，由于该字符串的第5位的左子串中字符‘0’的个数3比字符‘1’的个数2多，故该字符串不满足性质4，以致该字符串不是栈操作序列。

从上面的分析可知，只要找出所有的栈操作序列，就可以找到所有的出栈序列。总之，栈操作序列具有下列特征:

(1)如果依次输入的元素有n个，那么栈操作序列就是长度为2n的二进制字符串;

(2)栈操作序列的第一个字符一定是‘1’;

(3)栈操作序列的最后一个字符一定是‘0’;

(4)栈操作序列中‘1’和‘0’的个数相同;

(5)栈操作序列的每一位的左子串中‘1’的个数不少于‘0’的个数。

2.2 算法构造

设x1，x2，…，xn是依次入栈的n个元素，则由栈操作序列的性质和特征，可知栈操作序列应该在“10…0”(2n－1个‘0’字符)至“1…1”(2n个‘1’字符)中进行选择。为此，可以充分利用将数字转换为子字符串的转换函数itoa(k，str，2)，该命令的功能是将整数k转换成二进制字符串并且保存在字符数组str中。比如22n－1经转换后就变成了“10…0”(2n－1个‘0’字符)，22n－1经转换后就变成了“1…1”(2n个‘1’字符)。这意味着可以在22n－1至22n－1之间搜索栈操作序列。

因此，具体算法描述如下:

步骤1 初始化k=22n－1和入栈元素序列S=“x1x2…xn”。

步骤2 执行itoa(k，str，2)，可将整数k变为长度为2n二进制字符串str。

步骤3 判断str是否是栈操作序列:

(1)如果str中出现字符‘0’与字符‘1’的个数不等，则跳到步骤5;

(2)如果str中出现某一位的左子串中字符‘0’的个数多于字符‘1’的个数，则跳到步骤5。

步骤4 对入栈元素序列S执行栈操作序列:

(1)设 p=q=0，使得 S［p］=‘x1’，q指向 str的第一个字符;

(2)当 str［q］=‘1’，则将 S［p］入栈，同时执行p=p+1，使 p指向下一个入栈元素;当 str［q］=‘0’，将栈顶元素弹栈;

(3)q=q+1，是指向下一个操作字符;

(4)当q＜2n，则返回到(2);

(5)由所有的出栈元素按先后关系得到一个出栈序列。

步骤5 执行k=k+1。

步骤6 当k＜2n－1，则返回到步骤2。

步骤7 循环结束，得到所有的出栈序列。

3 算法分析［12］及改进

3.1 算法分析

本算法采用枚举法来选择栈操作序列，因此得到的一定全部最优解。由于算法中的k从22n－1开始，故计算量减少了一半。由于要找到所有的出栈序列，只有用枚举才能做到这一点。本算法所耗费的时间主要体现两个方面:(1)从二进制字符串中选择栈操作序列;(2)根据栈操作序列得到出栈序列。

由于算法中的k是无符号长整型，因此它最多能表示长度为32的二进制字符串，从而也就只能满足入栈元素不多于16个的情形。对于依次入栈的元素如果多于16个，则本算法无能为力。为了能求出入栈元素更多的出栈序列，必须对本算法加以改进。

3.2 改进算法

当将上述算法由单循环变成双循环，则入栈元素的个数由原来最多16个扩大到最多32.具体做法是用两个无符号整数(共64位)对应一个长度为64的二进制字符串。

改进算法描述如下:

步骤1 初始化k1=2n－1和入栈元素序列S=“x1x2…xn”;

步骤2 执行 itoa(k1，str1，2)，可将整数 k1变为长度为n二进制字符串str1;

步骤3 初始化k2和str2=“0…0”(n个0);

步骤4 执行 itoa(k2，str3，2)，strcpy(str2+n －strlen(str3)，str3)，strcpy(str，str2)和 strcat(str，str2);

步骤5 判断str是否是栈操作序列:

(1)如果str中出现字符‘0’与字符‘1’的个数不等，则跳到步骤7;

(2)如果str中出现某一位的左子串中字符‘0’的个数多于字符‘1’的个数，则跳到步骤7;步骤6 对入栈元素序列S执行栈操作序列:

(1)设 p=q=0，使得 S［p］=‘x1’，q指向 str的第一个字符;

(2)当 str［q］=‘1’，则将 S［p］入栈，同时执行p=p+1，使 p指向下一个入栈元素;当 str［q］=‘0’，将栈顶元素弹栈;

(3)q=q+1，是指向下一个操作字符;

(4)当q＜2n，则返回到(2);

(5)由所有的出栈元素按先后关系得到一个出栈序列。

步骤7 执行k2=k2+1;

步骤8 当k2＜2n－1，则返回到步骤4;

步骤9 执行k1=k1+1;

步骤10 当k1＜2n－1，则返回到步骤2;

步骤11 循环结束，得到所有的出栈序列。

以上算法可以解决入栈元素个数大于16但不超过32的情况，至于入栈元素超过32的情形，只需采用三重循环即可。类似算法容易写出，这里不再獒述。

4 算法测试

假设问题(2)的入栈元素序列是abcdefghijklmnopqrst，那么其中的部分出栈序列如表1所示。

表1 20个元素依次入栈所产生的部分出栈序列

测试结果表明，栈操作序列与出栈序列存在一一对应关系，不同的栈操作序列对应不同的出栈序列。同时，入栈的元素越多，需要选择的二进制字符串数目越多，因此程序所花费的时间越多。对算法进行分析可知，该算法的时间复杂度为O(2n)［13］。

5 结束语

求入栈元素比较多的出栈序列时，程序在执行过程中需要花费大量时间。但是，这是因为用穷举法求所有出栈序列造成的。然而，很多求最优解的问题，运用栈知识可以很快求出最优解。求出栈序列本身就不是一件容易的事情，没有对栈的充分理解和认识，是无法用算法来求所有的出栈序列的。因此，在从事教学和科研过程中，只有充分认识所要解决的问题，才能灵活运用栈来解决实际问题。通过出栈序列的求取，真正认识到栈的强大威力和有效性。

［1］严蔚敏，吴伟明.数据结构(第二版)［M］.北京:清华大学出版社，2000.

［2］朱大铭，马绍汉.算法设计与分析［M］.北京:高等教育出版社，2009.

［3］吴集林.关于出栈序列、二叉树、二叉搜索树三个问题计数的一致性［J］.广东广播电视大学学报，2005，56(4):106 －107.

［4］吴集林.用二叉树解决出栈序列问题［J］.赣南师范学院学报，2005，6:28 －30.

［5］徐凤生.出栈序列的性质及其求解新算法［J］.计算机工程与应用，2006，5:66 －68.

［6］袁红娟.基于链表的出栈序列生成算法［J］.河北北方学院学报，2006，22(5):70 －75.

［7］李红卫，徐亚平.出栈序列的研究［J］.计算机技术与发展，2007，17(10):127 －129.

［8］张先伟，曹雁锋.用插入法解决堆栈输出问题［J］.计算机应用与软件，2007，24(11):169 －171.

［9］韩静.“数据结构”课程中出栈序列的一种求解算法［J］.计算机教育，2008，23:67 －68.

［10］于林.关于数据结构中出栈序列问题的讨论［J］.计算机光盘软件与应用，2011，7:111 －112.

［11］吴福英，谭罗生，黄超.一个判定出栈序列的新方法［J］江西师范大学学报，2011，35(3):251－253.

［12］Mark Allen Weiss.Data Structures and Algorithm Analysis in C:Second Edition［M］.北京:人民邮电出版社，2005.

［13］(美)Robert Sedgewick，(法)Philippe Flajolet.算法分析导论［M］.冯舜玺，李学武，裴伟东，等.北京:机械工业出版社，2006.