3.1 栈

3.1.1 栈的基本概念

栈是一种特殊的线性表，其特殊性体现在元素插入和删除运算上，它的插入和删除运算仅限定在表的某一端进行，不能在表中间和另一端进行。允许进行插入和删除的一端称为栈顶，另一端称为栈底。栈的插入操作称为进栈（或入栈），删除操作称为出栈（或退栈）。处于栈顶位置的数据元素称为栈顶元素。不含任何数据元素的栈称为空栈。

正是这种受限的元素插入和删除运算，使得栈表现出先进后出或者后进先出的特点。举一个例子进行说明，假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有5个人，分别编号为①～⑤，按编号的顺序依次进入此死胡同，如图3.1（a）所示。此时若编号为④的人要退出死胡同，必须等⑤退出后才可以。若①要退出，则必须等到⑤、④、③、②依次都退出后才行，如图3.1（b）所示。这里人进出死胡同的原则是先进去的后出来。

在该例中，死胡同就看作是一个栈，栈顶相当于死胡同口，栈底相当于死胡同的另一端，进、出死胡同可看作进栈、出栈操作。插入栈的示意图如图3.2所示。

栈的基本运算主要包括以下6种。

（1）初始化栈InitStack（st）：建立一个空栈st。

（2）销毁栈DestroyStack（st）：释放栈st占用的内存空间。

（3）进栈Push（st，x）：将元素x插入栈st中，使x成为栈st的栈顶元素。

（4）出栈Pop（st，x）：当栈st不空时，将栈顶元素赋给x，并从栈中删除当前栈顶元素。

（5）取栈顶元素GetTop（st，x）：若栈st不空，取栈顶元素x并返回1；否则返回0。

（6）判断栈空StackEmpty（st）：判断栈st是否为空栈。

包含基本运算的栈如图3.3所示，其中，op1～op6表示上述6个基本运算。

【例3.1】设一个栈的输入序列为a、b、c、d，借助一个栈（假设栈大小足够大）所得到的出栈序列不可能是________。

A．a、b、c、d

B．b、d、c、a

C．a、c、d、b

D．d、a、b、c

解：a、b、c、d序列经过栈的情况如图3.4所示，根据栈的特点，很容易得出d、a、b、c是不可能的，因为d先出栈，说明a、b、c均已在栈中，按照进栈顺序，从栈顶到栈底的顺序应为c、b、a，出栈的顺序只能是d、c、b、a。所以不可能的出栈序列是D。

【例3.2】已知一个栈的进栈序列是1，2，3，…，n，其出栈序列是p1，p2，…，pn，若p1=n，则pi的值为________。

A．i

B．n—i

C．n—i+1

D．不确定

解：p1=n，则出栈序列是唯一的，即为n，n—1，…，2，1，由此推出pi=n—i+1。本题答案为C。

【例3.3】元素a、b、c、d、e依次进入初始为空的栈中，假设栈大小足够大。若元素进栈后可停留、可立即出栈，直到所有的元素都出栈，则所有可能的出栈序列中，以元素d开头的出栈序列个数是________。

A．3

B．4

C．5

D．6

解：若元素d第一个出栈，a、b、c均在栈中，从栈顶到栈底的顺序应为c、b、a，如图3.5所示，此后合法的栈操作如下。

（1）e进栈，e出栈，c出栈，b出栈，a出栈，得到的出栈序列decba。

（2）c出栈，e进栈，e出栈，b出栈，a出栈，得到的出栈序列dceba。

（3）c出栈，b出栈，e进栈，e出栈，a出栈，得到的出栈序列dcbea。

（4）c出栈，b出栈，a出栈，e进栈，e出栈，得到的出栈序列dcbae。

以元素d开头的出栈序列个数为4，本题答案为B。

3.1.2 栈的顺序存储结构

栈是一种特殊的线性表，和线性表存储结构类似，栈也有两种存储结构：顺序存储结构和链式存储结构。

栈的顺序存储结构称为顺序栈。顺序栈通常由一个一维数组data和一个记录栈顶元素位置的变量top组成。习惯上将栈底放在数组下标小的那端，栈顶元素由栈顶指针top所指向。顺序栈类型声明如下。

在上述顺序栈定义中，ElemType为栈元素的数据类型，MaxSize为一个常量，表示data数组中最多可放的元素个数，data元素的下标范围为0～MaxSize—1。当top=—1时表示栈空；当top=MaxSize—1时表示栈满。

图3.6说明了顺序栈st的几种状态（假设MaxSize=5）。图3.6（a）表示顺序栈为栈空，这也是初始化运算得到的结果。此时栈顶指针top=—1。如果做出栈运算，则会“下溢出”。

图3.6（b）表示栈中只含一个元素a，在图3.6（a）的基础上用进栈运算Push（st，'a'），可以得到这种状态。此时栈顶指针top=0。

图3.6（c）表示在图3.6（b）基础上又有两个元素b、c先后进栈，此时栈顶指针top=2。

图3.6（d）表示在图3.6（c）状态下执行一次Pop（st，x）运算得到。此时栈顶指针top=1。故b为当前的栈顶元素。

图3.6（e）表示在图3.6（d）状态下执行两次Pop（st，x）运算得到。此时栈顶指针top=—1，又变成栈空状态。

归纳起来，对于顺序栈st，其初始时置st.top=—1，它的4个要素如下。

（1）栈空条件：st.top==—1。

（2）栈满条件：st.top==MaxSize—1。

（3）元素x进栈操作：st.top++；将元素x放在st.data[st.top]中。

（4）出栈元素x操作：取出栈元素x=st.data[st.top]；st.top——。

顺序栈的基本运算算法如下。

1．初始化栈运算算法

其主要操作是设定栈顶指针top为—1，对应的算法如下。

2．销毁栈运算算法

这里顺序栈的内存空间是由系统自动分配的，在不再需要时由系统自动释放其空间。对应的算法如下。

      void DestroyStack(SqStack st)
      {  }

3．进栈运算算法

其主要操作是：栈顶指针加1，将进栈元素放在栈顶处。对应的算法如下。

4．出栈运算算法

其主要操作是：先将栈顶元素取出，然后将栈顶指针减1。对应的算法如下。

5．取栈顶元素运算算法

其主要操作是：将栈顶指针top处的元素取出赋给变量x，top保持不动。对应的算法如下。

6．判断栈空运算算法

其主要操作是：若栈为空（top==—1）则返回值1，否则返回值0。对应的算法如下。

提示：将顺序栈类型声明和栈基本运算函数存放在SqStack.cpp文件中。

当顺序栈的基本运算函数设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会顺序栈的各种运算的实现过程。

上述程序的执行结果如图3.7所示。

【例3.4】若一个栈用数组data[1..n]存储（n为一个大于2的正整数），初始栈顶指针top为n+1，则以下元素x进栈的正确操作是________。

A．top++；data[top]=x；

B．data[top]=x；top++；

C．top——；data[top]=x；

D．data[top]=x；top——；

解：栈元素是向一端伸展的，即从栈底向栈顶方向伸展。这里初始栈顶指针top为n+1，说明data[n]端作为栈底，在进栈时top应递减，由于不存在data[n+1]的元素，所以在进栈时应先将top递减，再将x放在top处。本题答案为C。

3.1.3 栈的链式存储结构

栈的链式存储结构是采用某种链表结构，栈的链式存储结构简称为链栈。这里采用单链表作为链栈，如图3.8所示，该单链表是不带头结点的，通过首结点指针ls唯一标识整个单链表。同时，单链表的首结点就是链栈的栈顶结点（图中首结点值为an表示最近进栈的元素是an），所以ls也作为栈顶指针，栈中的其他结点通过next域链接起来，栈底结点的next域为NULL。因链栈本身没有容量限制，所以不必考虑栈满的情况，这是链栈相比顺序栈的一个优点。

链栈的类型定义如下。

归纳起来，链栈ls初始时ls=NULL，其4个要素如下。

（1）栈空条件：ls==NULL。

（2）栈满条件：不考虑。

（3）元素x进栈操作：创建存放元素x的结点p，将其插入到栈顶位置上。

（4）出栈元素x操作：置x为栈顶结点的data域，并删除该结点。

链栈的基本运算算法如下。

1．初始化栈运算算法

其主要操作是：置s为NULL标识栈为空栈。对应的算法如下。

2．销毁栈运算算法

链栈的所有结点空间都是通过malloc函数分配的，在不再需要时需通过free函数释放所有结点的空间，与单链表销毁算法类似，只是这里链栈是不带头结点的。对应的算法如下。

3．进栈运算算法

其主要操作是：先创建一个新结点p，其data域值为x；然后将该结点插入到开头作为新的栈顶结点。对应的算法如下。

4．出栈运算算法

其主要操作是：将栈顶结点（即ls所指结点）的data域值赋给x，然后删除该栈顶结点。对应的算法如下。

说明：尽管链栈操作时不考虑上溢出，但仍然需要考虑出栈操作时的下溢出。

5．取栈顶元素运算算法

其主要操作是：将栈顶结点（即ls所指结点）的data域值赋给x。对应的算法如下。

6．判断栈空运算算法

其主要操作是：若栈为空（即ls==NULL）则返回值1，否则返回值0。对应的算法如下。

      int StackEmpty(LinkStack ∗ ls)
      {    if(ls==NULL) return 1;
           else return 0;
      }

提示：将链栈结点类型声明和链栈基本运算函数存放在LinkStack.cpp文件中。

当链栈的基本运算函数设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会顺序栈的各种运算的实现过程。

上述程序的执行结果如图3.7所示。

【例3.5】以下各链表均不带有头结点，其中最不适合用作链栈的链表是________。

A．只有表尾指针没有表头指针的循环单链表

B．只有表头指针没有表尾指针的循环单链表

C．只有表头指针没有表尾指针的循环双链表

D．只有表尾指针没有表头指针的循环双链表

解：由于各链表均不带有头结点，这里表头指针就是首结点指针。采用一种链表作为链栈时，通常将链表首结点处作为栈顶。一个链表适不适合作为链栈，就看它是否能够高效地实现栈的基本运算，而栈的主要操作是进栈和出栈。

考虑选项A，只有表尾指针没有表头指针的循环单链表，假设表尾指针为rear，它指向循环单链表的尾结点，如图3.9所示。元素x进栈的操作是：创建存放x的结点p，将结点p插入在rear结点之后作为栈顶结点，不改变rear；出栈的操作是：删除rear结点之后的结点。两种操作的时间复杂度均为O（1）。

考虑选项B，只有表头指针没有表尾指针的循环单链表，假设表头指针为first，它指向循环单链表的首结点，如图3.10所示。元素x进栈的操作是：创建存放x的结点p，将结点p插入在first结点之前，即p—>next=first，first=p，但还要将其改变为循环单链表，而尾结点需要遍历所有结点找到，遍历的时间为O（n），所以进栈操作的时间复杂度为O（n）；出栈的操作是：删除first结点，删除后仍然需要将其改变为循环单链表，所以出栈操作的时间复杂度为O（n）。两种操作的时间复杂度均为O（n）。

考虑选项C和D，由于都是循环双链表，可以通过表头结点直接找到尾结点，在插入和删除后改为循环双链表的时间均为O（1），所以它们的进栈和出栈操作的时间复杂度都是O（1）。

比较起来，只有表头指针没有表尾指针的循环单链表作为链栈时，进栈和出栈操作的时间性能最差。本题答案为B。

3.1.4 栈的应用示例

在较复杂的数据处理过程中，通常需要保存多个临时产生的数据，如果先产生的数据后进行处理，那么需要用栈来保存这些数据。本节通过几个经典示例说明栈的应用方法，并且算法中均采用顺序栈，实际上采用链栈完全相同。

【例3.6】假设以I和O分别表示进栈和出栈操作，栈的初态和终态均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。

（1）下面所示的序列中哪些是合法的？

A．IOIIOIOO

B．IOOIOIIO

C．IIIOIOIO

D．IIIOOIOO

（2）通过对（1）的分析，设计一个算法利用链栈的基本运算判定操作序列str是否合法。若合法返回1；否则返回0。

解：（1）A、D均合法，而B、C不合法。因为在B中，先进栈一次，立即出栈两次，这会造成栈下溢。在C中共进栈5次，出栈3次，栈的终态不为空。

归纳起来，这样的操作序列是合法的，当且仅当其中所有I的个数与O的个数相等，而且任何前缀中I的个数大于或等于O的个数。

（2）本例用一个顺序栈st来判断操作序列是否合法，其中，str为存放操作序列的字符数组，n为该数组的元素个数。对应的算法如下。

说明：本例的另一种解法是用cnt累计I与O的个数差，cnt从0开始，循环遍历str，遇到I增1，遇到0减1。cnt小于0时返回0。循环结束后cnt为0则返回1。

【例3.7】回文指的是一个字符串从前面读和从后面读都一样，如＂abcba＂、＂123454321＂都是回文。设计一个算法利用栈判断一个字符串是否为回文。

解：由于回文是从前到后以及从后到前都是一样的，所以只要将待判断的字符串颠倒，然后与原字符串相比较，就可以决定是否回文了。

将字符串str从头到尾的各个字符依次进栈到顺序栈st中，由于栈的特点是后进先出，则从栈顶到栈底的各个字符正好与字符串str从尾到头的各个字符相同；然后将字符串str从头到尾的各个字符，依次与从栈顶到栈底的各个字符相比较，如果两者不相同，则表明str不是回文，在相同时继续比较；如果相应字符全部匹配，则说明str是回文。对应的算法如下。

【例3.8】设计一个算法，判断一个可能含有小括号（“（”与“）”、）、中括号（“[”与“]”）和大括号（“{”与“}”）的表达式中各类括号是否匹配。若匹配，则返回1；否则返回0。

解：设置一个顺序栈st，定义一个整型flag变量（初始为1）。用i扫描表达式exp，当i＜n并且flag=1时循环：当遇到左括号“（”“[”“{”时，将其进栈；遇到“}”“]”“）”时，出栈字符ch，若出栈失败（下溢出）或者ch不匹配，则置flag=0退出循环，否则直到exp扫描完毕为止。若栈空并且flag为1则返回1，否则返回0。

例如，对于表达式＂[（]）＂，其括号不匹配，匹配过程如图3.11（a）所示；对于表达式＂[（）]＂，其括号是匹配的，匹配过程如图3.11（b）所示。

对应的算法如下。

【例3.9】设计一个算法将一个十进制正整数转换为相应的二进制数。

解：将十进制正整数转换成二进制数通常采用除2取余数法（称为辗转相除法）。在转换过程中，二进制数是从低位到高位的次序得到的，这和通常的从高位到低位输出二进制的次序相反。为此设计一个栈，用于暂时存放每次得到的余数，当转换过程结束时，退栈所有元素便得到从高位到低位的二进制数。如图3.12所示是十进制数12转换为二进制数1100的过程。

对应的算法如下。

设计如下主函数。

本程序的一次执行结果如下。

      输入一个正整数：120↙
      对应的二进制数：1111000