02 线性表，栈和队列

这几种数据结构都比较简单，其中较为复杂的是栈的应用。

   我们来看看栈的应用之一：表达式求值。这可能是我们第一次遇到这个问题，因为如果是手工计算表达式的话，那是小学的课程。然后我们就被告知应该用栈实现表达式求值，包括怎么把中缀表达式转成后缀表达式，然后用后缀表达式求出值，这两个过程都用到了栈，说明栈很有用，也就完了。但我们为什么要用后缀表达式呢？又为什么用栈呢？

   我们来看一个表达式 1+2*(3-4)/5 。按照运算法则，先计算3－4＝－1，然后是2×－1＝－2，－2/5＝－0.4 最后1＋（－0.4）=0.6。我们怎么知道第一个计算的是3－4而不是1＋2呢？

   我们从计算机的角度来看，它只会从左向右扫描，首先得到1，得知这是一个操作数。然后遇到＋，然后遇到2，这时问题就来了，1＋2这个运算能不能进行呢？在这个时候还是未知的，如果后面的运算符是＋和－，则可以计算，如果是×／，则还不能进行。因此＋要保存起来。然后遇到×，说明＋必须在×之后运算，所以是后进先出，把×也保存。然后是括号，3，－。如果没有括号，则×可以运算了，但左括号提高了－的优先级，保存－，接着遇到4，）。这时－可以运算了。接着遇到／，说明×可运算了，然后是5，然后表达式结束了，说明／可以运算，最后是＋。

   也就是说，遇到一个运算符还不能马上确定能不能执行这个运算，要看它的下一个运算符，如果下一个比它的优先级高，说明这个运算符必须在它的下一个运算符之后执行。至于它的下一个运算符什么时候执行则要由它后面的运算符确定。如果下一个的优先级不高于它，则这个运算可以马上执行，运算的结果作为一个新的操作数。

另外一个运算符的两个操作数也要和操作符对应上。一种办法是把操作数和运算符同时存入一个栈。比如上面的例子，1，＋，2，×，（，3，－，4入栈，遇到），把栈顶的元素弹出直到遇到（。3－4＝－1，然后把－1压入。栈为1，＋，2，×，－1，接着遇到／，从栈顶往下找到第一个运算符为×，所以×可以执行，执行后栈为1，＋，－2，因为／比＋优先级高，所以压入／，接着遇到5，表达式介绍，所以执行－2／5＝－0.4，－0.4入栈，最后执行1＋（－0.4）＝0.6。

从上面的过程可以看出，把运算符和操作数压入同一个栈有时很不方便。首先要求运算符和操作数的大小一样以便于压入同一个栈，此外，我们在比较当前运算符和前面的运算符的优先级时要弹出夹在中间的操作数感觉也很不方便。因此可以用两个栈，一个存操作数，因此存运算符。

再来看看用递归来解决hanoi塔的问题。我记得第一次见到这个问题是在学习C语言时。好像是讲C语言是支持递归的，然后就举了这个例子。当时反正搞不清是怎么回事，只是记住了hanoi问题就该这么做。假设要把n个盘从X移到Z，Y为辅助塔。则先把上面n－1一个盘从X移到Y，用Z做辅助。然后把第n号盘从X移到Z，最后把前n－1个盘从Y移到Z，X做辅助。算法如下。

# include <iostream.h>

void move(int n,char X,char Y){

  cout<<"move disk "<<n<<" from "<<X<<" to "<<Y<<endl;

}

void hanoi(int n,char X,char Y,char Z){

  if(n<=1)

         move(n,X,Z);

  else{

         hanoi(n-1,X,Z,Y);

         move(n,X,Z);

         hanoi(n-1,Y,X,Z);

  }

}

   算法的时间复杂度是O（2ⁿ）。似乎一切都很好，问题也解决了。

我们换个角度来考虑。上面的算法是将规模为n的问题分解为两个规模是n－1的相同子问题以及一个常数时间的问题。那我能不能像分治法那样把n的问题分成几个规模是n/2的子问题呢？下面的算法可以吗？

void hanoi2(int from,int to,char X,char Y,char Z){

  if(from==to)

         move(from,X,Z);

  else{

         int mid=(from+to)/2;

         hanoi2(from,mid,X,Z,Y);

         hanoi2(mid+1,to,X,Y,Z);

         hanoi2(from,mid,Y,X,Z);

  }

}

   算法为，把1到（1＋n）/2号盘从X移到Y，把（1＋n）/2+1到n号盘从Y移到Z，最后把1到（1＋n）/2号盘从Y移到Z。如果能够实现的话，那么它的复杂度：T(n)=3T(n/2)+c

为O(n^log₂³)。

但一运行就发现不对了。为什么这个算法不行？首先，假设可以把1到（1＋n）/2号盘从X移到Y，现在要把(1+n)/2+1到n号盘从X移到Z，问题是(1+n)/2+1到n号盘都比Y上的1到(1+n)/2号盘大，也就是没有辅助盘的情况下把(1+n)/2+1到n号盘从X移到Z，这显然是不可能实现的。也就是说第二次递归调用hanoi2(mid+1,to,X,Y,Z);时，问题和原来的问题不同了。

那么为什么前面的算法又是正确的呢？

我们分两步来证明。

1，如果规模为n的hanoi塔是有解的，即如果可以把n个盘从X移到Z。那么一定可以把前n－1个盘从X移到Y。

a.，对于任意一个合法的解，肯定有一次移动是把第n号盘从X或Y移到Z。

如果是把n盘从X移到Z，则说明在这次移到前，X上只有n号盘（否则有盘压在上面，n是不能移到的），Z上没有盘(否则任何盘都比n小，n也没法移到Z)，则其余n－1个盘都在Y上，即前面的一系列移到已经把n－1个盘从X移到了Y。

如果是把n盘从Y移到Z，则说明前面的一系列可以把n－1个盘从X移到Z（否则第n盘无法移到Y），假设这些移动为move₁, move₂,…., move_k，其中move_i表示把盘x从a移到b。如果a或b中有Y或Z，则我们把Y(Z)换成Z(Y)，就可以得到把n－1个盘从X移到Y的移到方法了。

b，当我们把前n－1号盘移到Y，第n号盘移到了Z，则可以把n－1个盘从Y移到Z

   这其实是一个规模为n－1的问题了，因为n号盘已经到位，可以不动了，而且它的盘号最大，不会影响别的盘的移到（任何其它盘可以压在它之上）。

总结a，b，如果规模为n的hanoi塔是有解的，那么上面的算法可以解决它。

2，现在该证明hanoi塔是有解的了。用数学归纳法证明如下：

n＝1是显然有解。

假设n＝k时有解，考虑n＝k＋1。先把第1到k号盘从X移到Y（k时有解），把第k＋1号盘从X移到Z，最后把1到k号盘从Y移到Z（k＋1号盘不会影响1到k号盘的移动。

  发现证明过程和求解一样。

  最后一个问题是：有没有更好的算法（移动的次数更少）？我们写的算法是要移动2ⁿ-1次。能不能证明不可能用少于这些次数解决hanoi问题？

   现在来证明上面的算法的移动次数是最小的。

它等价于证明任何一个合法的解至少要移动2ⁿ-1次盘。

n＝1时成立。

  假设n＝k时成立，则n＝k＋1时。

  在任何合法的解中，至少有一次是把n盘从X或Y移动到Z。

  在说明移动n盘的时候，前n－1盘都在Z或Y上。说明已经把前n－1个盘从X移动到了Y或Z，根据归纳假设，至少要2^n-1-1次移动，然后还得把其它n-1个盘从X或Y移动到Z，也要2^n-1-1次移动，共计最少2（2^n-1-1）＋1＝2ⁿ-1次。