数据结构.栈

一、基本概念

1.栈是限定仅在表尾（栈顶）进行插入和删除操作的线性表；

2.栈：后进先出（LIFO），适用于撤销操作

二、存储结构

1.栈的顺序存储结构：

1）数组的首元素作栈底

2）两栈共享空间

2.栈的链式存储结构：

链栈不需要头结点

三、栈的应用：

1.经典递归例子：斐波那契数列

递归函数：直接调用自己或通过一系列的调用语句间接调用自己的函数。

每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。（迭代使用的是循环结构，递归使用的是选择结构）

2.栈的应用——四则运算表达式求值：

后缀表达式：所有符号都是在要运算数字的后面出现。

代码示例：

 1 ///Name:Stack
 2 ///Author:JA
 3 ///Date:2015-3-4
 4 
 5 
 6 
 7 ///算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，
 8 ///OP为运算符集合。
 9 OperandType EvaluateWxpression(){
10     InitStack(OPTR); Push(OPTR, '#');
11     InitStack(OPND); c = getchar();
12     while (c != '#' || GetTop(OPTR) != '#'){
13         if (!In(c, OP)){ Push(OPND, C); c = getchar(); }
14         else
15             switch (Precede(GetTop(OPTR), c)){
16             case'<':    //栈顶元素优先权低
17                 Push(OPTR, c); c = getchar();
18                 break;
19             case'=':   //脱括号并接收下一字符
20                 Pop(OPTR, x); c = getchar();
21                 break;
22             case'>':    //出栈并将运算结果入栈
23                 Pop(OPTR, theta);
24                 Pop(OPND, b); Pop(OPND, a);
25                 Push(OPND, Operate(a, theta, b);
26                 break;
27         }//switch
28     }//while
29     return GetTop(OPND);
30 }//EvaluateExpresssion
31 
32 ///n阶汉诺塔问题
33 void hanoi(int n, char x, char y, char z){
34     if (n = 1)
35         move(x, 1, z);                //将编号为1的圆盘从x激至z
36     else{
37         hanoi(n - 1,x,z,y);           //将x上编号为1至n-1的圆盘移到y,z作辅助塔
38             move(x, n, z);           //将编号为n的圆盘从x激至z
39         hanoi(n - 1, y, x, z);        //将y上编号为1至n-1的圆盘移到z,x作辅助塔
40     }
41 }

View Code