假期连载之四
（限定性线性表——栈，栈的递归应用）
五）限定性线性表——栈和队列
前面我们介绍了几种简单线性表的抽象数据结构及其基本运算，在一些应用中，通常还有一些逻辑结构与线性表相同，但含额外运算限制的数据结构需求，例如栈和队列。
栈
栈Stack被广泛应用于计算机基础应用中，例如汇编程序中的中断、句法识别以及表达式运算，函数的传参、函数值返回等各种机制。
栈的定义是一种只允许在表的末端进行插入和删除的线性表。通常允许相关操作的一端称为栈顶Top，而不允许进行插入和删除操作的一端称为栈底bottom。当栈中没有任何元素时称为空栈。由栈的定义可知，栈又是一种后进先出（LIFO，Last In First Out）的线性表。
栈的抽象数据类型定义与普通线性表相类似，例如下面的C语言形式描述：
ADT Stack
{
数据元素：可以是任意类型的数据，但必须属于同一个数据对象。
结点关系：栈中数据元素之间是线性关系。
InitStack(S); //初始化空栈
ClearStack(S); //将S置为空栈
IsEmpty(S); //判断是否栈空，是则返回TRUE，否则返回FALSE。
IsFull(S); //判断是否栈满，与上类似。
Push(S,x); //在S栈顶压入元素x，成功返回TRUE，否则返回FALSE。
Pop(S,x); //在S栈顶弹出元素，并保存入x返回，与上类似。
GetTop(S,x); //取S栈顶元素并保存入x返回，但不弹出该值，与上类似。
}
通常对于一种线性表，一般具备顺序存储和链式存储两种形式，栈相应分为顺序栈和链栈。
顺序栈按定义可知其是建立在顺序存储结构的基础上，通常用一维数组表示。下面是顺序栈的结构类型定义：
#define Stack_Size 50
typedef struct
{
stackElementType elements[Stack_Size];
int top;
}
用C++描述的顺序栈初始化构造函数如下：
template <class T>
seqStack<T>::SeqStack(int sz):top(-1), Stack_Size (sz)
{
elements = new T[Stack_Size];
assert(elements != NULL); //判断动态存储分配是否成功
}
上段程序需要注意的是，构造函数在声明部分就初始化了数据成员的值，并在参数部分声明了一个局部变量，这里的Stack_Size并非const类型，这可以使用户自己定义顺序栈空间的大小，top=-1表示栈顶指针指空，这种写法需要注意。
下面以链栈为例，给出栈的几种基本运算的伪码描述。
1）进栈操作
Push(top,x) //top为栈顶指针，x为数据元素值，下同
temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));
if temp==NULL then
return FALSE;
else then
temp->data=x;
temp->next=top->next;
top->next=temp;
return TRUE;
2）出栈操作
Pop(top,*x)
temp=top->next;
if temp==NULL then
return FALSE;
else then
top->next=temp->next;
*x=temp->data;
free(temp);
return TRUE;
在以上两例中，栈由带头结点top的单链表实现，具体操作时采用了头插法入栈。实际应用中还可以采用尾指针进行尾插法入栈。
3）多栈共享
在实际应用中，可能会遇到一个程序使用多个栈的情况。当使用顺序栈时，会由于栈空间预估不足，造成有的栈溢出、有的栈空闲过多等问题，为了解决上述问题，通常采用多个数组共享一个数组空间，并利用栈操作的特性对其存储空间互相补充，这就是多栈共享技术。
多栈共享中又存在两种情况，其一是程序需要使用最多两个栈的情况，通常采用双端栈技术予以解决，这种栈的特点如下：
1、 首先申请一个数组空间S[M]，将两个栈的栈底分别放在一维数组的两端，分别为0，M-1。
2、 通过简单对比可知，由于栈顶动态变化，两栈在空间上形成互补关系，逻辑上实现了栈空间由其所需求空间动态决定的机制，从而提高了空间利用率。
3、 在实际应用中通常将两个栈编号标记，方便调用。
另一种情况，是当程序需求两个以上栈的情况。显然双端栈无法满足这一需求。因此当我们遇到这种情况时，一般采用链栈形式，并用一个统一的一维结构指针数组管理每个栈的栈顶指针。
栈与递归
递归recurve在数学和计算机科学中有着十分重要的作用。在计算机科学中，递归从编译原理的句法定义，到数据结构中的树形结构搜索、排序等问题，都是必不可少的应用。
递归在数学及程序设计方法学中的定义是：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的，而且若一个过程直接地或间接地调用自己，则称这个过程是递归过程。
有人可能注意到了“直接”或“间接”的表述，“直接递归函数”顾名思义就是在自己的定义中直接调用自己的方法函数。“间接”主要是指方法函数通过一系列的中间语句，通过其它函数调用自己。
一般在以下3种情况下，需要使用递归方法。
1）定义上是递归的
例如数学上常用的阶乘函数、幂函数、斐波拉契数列等，其定义运算都是递归的。例如斐波那契数列，这是一个从前两项为自然数1，第三项开始为前两项之和的无穷数列，即：
1、1、2、3、5、8、13、…、n。在计算机实现时，我们只需给出此数列的递归关系“f(n)=f(n-1)+f(n-2)，其中n>=2”，即可实现递归运算。
2）数据结构是递归的
在我们已经讨论过的单链表结构中，可以明显地看到一种递归关系。即LinkNode由数据域data和指针域next构成，而next又由LinkNode定义。利用递归关系我们可以写出寻找单链表中某一结点的算法的递归形式。
3）问题的解法是递归的
递归是解决一些应用问题唯一有效的解决方案。典型例题即是著名的汉诺塔Tower of Hanoi问题。问题介绍可以看wiki：
http://zh.wikipedia.org/w/index.php?title=%E6%B1%89%E8%AF%BA%E5%A1%94&variant=zh-cn
这里给出简单的伪码演示：
Hanoi(n,A,B,C)
If n==1 then printf Move top disk from A to C;
Else then
Hanoi(n-1,A,C,B);
printf Move top disk from A to C;
Hanoi(n-1,B,A,C);
这里重申递推和递归的关系，递推是利用问题本身所具有的递推关系对问题求解的一种方法，而这种递推性质决定了已知i-1的解，由此可求得1、2、…、i-1的一系列的解，其问题规模为i，例如n!问题。
递推问题通常可以用递归方法求解，同时也可以使用循环迭代的方法求解。
在程序设计语言中，递归的实现主要得益于递归工作栈的工作原理。每一层递归调用所需要保存的的信息包括：
1）返回地址，即上一层中本次调用自己的语句的后继语句处。
2）在本次过程调用时，为与形参结合的实参创建副本。
3）本层的局部变量。
在每进入一层递归时，系统就要建立一个新的工作记录，把上述项目登入并加入到递归工作栈的栈顶位置。每退出一层递归，就从递归工作栈退出一个工作记录。
在实际应用中，递归通常体现出两个特性：
1）递归算法简单有效，通常可用来解决一些复杂问题。
2）由于实现机制的问题，递归算法效率较低。
因此在求解一些问题时，我们一般用递归方法分析问题，而使用非递归方法求解相关问题。
1）用栈实现递归过程的非递归算法
一般的递归过程可以用递归调用树进行表示，因此可以由栈代替递归算法实现树的运算，这将在以后树结构的介绍中作一说明。
2）用迭代法实现递归过程
实际上就是使用循环结构，有一类递归可以使用循环结构简单表示，即单向递归。单向递归是指递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，相互之间参数无关，并且这些递归调用的语句处于算法的最后，例如斐波那契数列。还有一种递归，指递归调用语句只有一个，而且是处于算法最后，显然这是单向递归的一个特例，称为尾递归。
无论使用何种非递归方法实现递归过程，一般应先根据递归算法画出程序流程图，然后建立起循环结构。
在下一节，我们将继续扩展递归应用，使用回溯法backracking解决较复杂的迷宫Maze问题，并对几种高级编程技术进行介绍，并加以综合利用。
（未完待续）