栈的应用_1. 栈的应用-模拟工厂 【问题描述】 有n个物品,编号为1,2,....,n 有这样一个机器,

栈有一个很重要的应用：在程序设计语言中讲了递归。那么什么是递归呢？当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗？如果A、B两面镜子互相面对面放着，你往中间一站，嘿，两面镜子都有你的千百个“化身”，为什么会有这么奇妙的现象呢？原来，A镜子里有B镜子的像，B镜子里也有A镜子的像，这样反反复复，就会产生一连串的“像中像”。这是一种递归现象。我们先来看一个经典的递归例子：斐波那契数列（Fibonacci）。为了说明这个数列，这位斐老还举了一个很形象的例子。
栈的代码很容易看懂,但是栈的效率低。

1.递归

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

函数怎么可以自己调用自己？听起来有些难以理解，不过你可以不要把一个递归函数中调用自己的函数看做是在调用自己，而就当它是在调用另一个函数。只不过，这个函数和自己长得一样而已。当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归都需要一个退出递归的条件。递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会消耗大量的时间和内存。那么我们讲了那么多递归的内容，和栈有什么关系呢？程序设计基础阶段我们已经了解了递归是如何执行它的前行和退回的。递归过程退回的顺序是它前行顺序的逆序。显然这符合栈的存储方式。简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压如栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都由系统代劳就可以了。

使用栈可以模拟递归过程,并且消除递归,对于单向递归和尾递归而言,可以用迭代的方法消除递归。

1.1 求n阶

int fun(int n)
{
       if(n==1)
    {
              return 1;
    }
    else
    {
              return fun(n-1)*n;
       }
}
1
2
3
4
5
6
7
8
9
10
11

1.2 斐波那契数列实现

int fun(int n)//计算斐波那契数列第n项的值
{
       if(n==1||n==2)
    {
              return 1;
    }
    else
    {
              return fun(n-1)+fun(n-2);
       }
 }
1
2
3
4
5
6
7
8
9
10
11

1.3 n的k次幂

int fun(int n,int k)
{
       if(k==1)
    {
              return n;
    }
    else
    {
              return fun(n,k-1)*n;
       }
}
1
2
3
4
5
6
7
8
9
10
11

1.4 字符串逆转

void strReverse(char s[],int len)    

{

    if(len==1)                            

    {

        printf(“%c”,s[0]);

    }

else

{

    printf(“%c”,s[len-1]);          

    strReverse(s,len-1);                 

}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.进制转换

在计算机中存储的数据都是二进制，所以往往需要把十进制数据转换成二进制，转换的过程实际就是除2取余数，这其中我们可以看到最先求得余数实际是个位数，书写一个数据的时候都是先书写高位的数据，而后依次到个位。这正好和栈后进先出的特性吻合，因此可以使用栈来存储。

例如：十进制的25转换成2进制

25 25/2 25%2 n 0==n/2 y=n%2

25 12 1

12 6 0

6 3 0

3 1 1

1 0 1

根据最后得到的是高位，先除余得到的是个位，最后得到的二进制值是：11001

3.括号匹配

判断一个表达式的”(“和”）”是否匹配，思路是这样的：遇到”（“则入栈，遇到”）”则从栈顶弹出”（“与之配成一对，当整个表达式扫描完毕时：

（1） 若栈内为空，则说明（与）是匹配的。

（2） 若表达式扫描完毕，栈内仍有（则说明左括号是多的。

（3） 若当）被扫描到，栈里却没有（能弹出了，说明）多，表达式中）也是多的。

4.表达式求值

算法思想：

（1） 首先置操作数栈OPND为空栈，表达式的起始符#为运算符栈OPTR的栈底元素；

（2） 依次读入表达式中的每个字符

若运算符是‘#’或栈顶是‘#’，结束计算，返回OPND栈顶值。

if（是操作数） → 则PUSH（ OPND，操作数）；

if（是运算符） → 则与OPTR栈顶元素进行比较，按优先级进行操作；

优先级操作细则如下：

① if栈顶元素<输入算符，则算符压入OPTR栈，并接收下一字符

② if栈顶元素=运算符但≠‘#’，则脱括号(弹出左括号)并收下一字；

③ if栈顶元素>运算符，则退栈、按栈顶计算，将结果压入OPND栈。

④ 且该未入栈的运算符要保留，继续与下一个栈顶元素比较！

表达式求值过程的描述：3*（7 – 2 ）