数学和计算机科学板块_辛酸网

数据结构与算法4

  栈是一种特殊的线性表，其核心特征叫FILO(First In Last Out)或LIFO(Last Out First In)，即先进后出，后进先出。向栈中插入(push)和弹出(pop)元素只能在最后面进行。对于栈而言，最前面的地方叫栈底(base)，最后面的地方叫栈顶(top)，相应地元素顺序也由一般线性表的前后，经常被描述为上下。为了简化设计，栈通常用顺序表实现，用链表做的链栈虽然有但是很少。顺序栈我们一般用数组来实现，那既然是数组就有大小（那你要非拿STLvector等抬杠我啥也不说），有大小就意味着不能无限地放东西，放着放着就满了，这要是还放就放不下了，此时就溢出了，曰上溢。反之，要是把里面的元素都弹出去，栈都空了你还要拿东西，那又是溢出，就是下溢。如果你在编程时不设立一套内存的检查机制，造成栈溢出了还不报错，那后果是很严重。在信息安全领域，栈的溢出可以引起一些系统的崩溃，所以是一种厉害的攻击手段。

  你可以把栈底设为指向最下面那个元素，也可以向单链表的头指针和头结点那样，指向最下方元素更靠下的一个位置。栈顶可以指向最靠上的元素，也可以指向更靠上的一个位置。只是规则不同，那么判空条件就不同。假设从下往上内存地址是越来越大，而且栈顶栈底都指向最上最下的元素，那么只有一个元素时栈顶栈底都指向它，空的时候top就再减1，反而比base小了。但如果栈底被定义为最底部元素前面的一个位置，那么判空条件就是top==base了。值得一提的是，我们定义一个栈，涉及到top和base的定义，但你可以把top和base真的定义为指针，也可以定义为元素在数组中的下标或是链表中的序号。因此如果二者不相等，到底差多少还要看你怎么定义。

  如果你做的是链栈，那就没有这方面的问题。这里只讨论顺序栈。
  一个顺序栈最简单的实现确实是数组，它涉及入栈和出栈两大操作，一个是在结尾插入，另一个是弹出。所谓插入就是在现有元素最大下标+1处赋值放东西，只要不溢出保证整个栈实际所占空间不变，只是长度+1.但是出栈呢？注意：出栈不是删除这个元素，出栈以后只要不再入栈，这个元素依然存在，没有被覆盖！出栈仅仅是修改了top的值而已。这就好比一个铁通，里面会放一块块砖头，每一块砖头都在不同高度处，不能重叠。出栈不是把最上面那块砖头拿出去，是把这个铁通最上面的那一层铁皮用刀切下来，于是那块砖头暴露在外，宣布不再属于铁通内的一部分而已。要是再入栈就拿块新砖头代替原来砖头的位置，顺便拿502把最上面一层铁皮补上去而已。现在思考下，一旦真的上溢了怎么办？我们可以另外建立一个数组，后面的元素都在那里存放，不过这样就使得操作复杂化了，因为你要根据栈的实际长度和各数组长度关系判断该往哪里放东西或删东西。现在给出一个简单的栈的定义。

#define MAXSIZE 1000//具体最大多少你自己看着办吧
class Stack{
	public:
		int top,base;
		DataType* value;
		DataType*init(void);//初始化，内有数组的动态分配
		bool push(DataType x);//返回值是是否成功
		bool pop(void);
	};

  这还是一个栈，如果是多个栈，如何共享一块空间呢？对于两个栈，我们一般采取双头处理的方式，一个栈的栈底在一头，另一个栈的栈底在另一头。一个栈的栈顶越入栈地址越大，另一个栈顶越入栈地址越小，双向奔赴了属于是。多个栈的话，就要提前预估好每个栈最大要占的空间，分别在同一个空间里的不同片段工作。这种情况叫做共享栈。

  栈有很多应用，包括但不限于：工厂模式程序的撤销与重做、表达式求值、代码编译解释时的括号匹配、函数的调用与返回、CPU中断内套中断的跳转机制、进制转换、二叉树遍历、图的深度优先搜索等。例如，一个程序中要执行一个函数f，函数f调用了另一个函数g，而函数g有恰好调用了函数h……就这样层层套娃。CPU在f调用g时就要把f中的一些局部变量，以及调用g的那条跳转指令的下一条指令的地址给记下来。只有这样在执行完g以后才能继续执行f剩下的部分。同理g调用h时也要记录下g中的局部变量和调用h的指令的下一条指令，这样才会在执行完h后继续正常执行g。函数返回时，最后被调用的函数结束，继续执行直接调用它的函数，再执行调用 调用它的函数 的函数。所以调用顺序是fgh，返回时就是hgf，刚好反过来。像这样的栈就叫函数调用栈，里面有局部变量和跳转指令的下一条指令之地址。CPU中断也有类似的栈，只不过会有中断屏蔽等烦人的东西。

  现在来看一个栈的典型应用，表达式求值。例如一个表达式(a+b)*(c-d)+e，怎么计算？显然是要先得到x=a+b,Y=c-d，再得出Z=XY，最后得到Z+e即为答案。对此最通常的求值方法是建立两个栈，一个数字栈放着参与运算的数，一个符号栈，放着运算符。遍历表达式，如果发现是数那就入数字栈，待会要算。如果发现运算符，那我们知道，运算符是有优先级的，如果我们现在遍历的运算符和符号栈顶相比，优先级更高，那就说明这个运算符的运算，先于栈顶运算符的运算。反之，要是当前运算符优先级小于符号栈顶，那么我们就知道现在就是符号栈顶相对应的运算该发生的时候，至少，这个运算的发生是在当前遍历的运算符的运算之前。（或者说，等效起来是这样的）所以，一旦符号栈顶优先级高，我们就得果断弹出，展开运算。一般而言，栈顶若不是单目运算符，那数字栈的弹出还不止一个呢。

  现在我们遍历这个表达式。

1.当前运算符(，入符号栈 2.当前数a，入数字栈 3.当前运算符+，优先级高于(，入符号栈 4.当前数b，入数字栈 5.当前运算符)，优先级低于+，两栈弹出，数字栈内有a+b，符号栈有(   发现(将其弹出 6.当前运算符*,符号栈空，入符号栈 7.当前运算符(，入符号栈 8.当前数c，入数字栈 9.当前运算符-，优先级高于(，入符号栈 10.当前数d，入数字栈 11.当前运算符)，两栈弹出，数字栈顶c-d，符号栈顶为* 12.当前运算符+，优先级低于*，两栈弹出，数字栈内有唯一元素(a+b)*(c-d)，符号栈有(   发现(将其弹出，+入符号栈 13.当前数e，入数字栈 14.表达式遍历完毕，两栈弹出，得【(a+b)*(c-d)】+【e】

  今有如下遍历方案：

  如果是数，入数字栈
  否则，若符号栈空，必入之
  否则，若为左括号(，必入符号栈
  否则，若为右括号，两栈弹出，进行运算，)必不入栈
    运算结果入数字栈，直至在符号栈遇到(，弹出(
  否则，比较当前运算符与符号栈顶的优先级
    如果当前运算符优先级高，入符号栈
    否则，两栈弹出，执行符号栈顶对应的运算，结果入数字栈
  表达式遍历完毕，则两栈弹出至符号栈空，此时数字栈唯一的元素即为结果

  不过，这是针对只有小括号而言的，若考虑中括号和大括号，可以像C语言代码那样都变成小括号。担心括号有问题的，运算之前可以做括号匹配，同样用栈实现。像(a+b)*(c-d)+e这样的表达式叫中缀表达式，因为运算符有很大一部分甚至全部都是夹杂在直接参与其运算的数之间的。如果运算符就跟在参与运算的数或表达式后面，叫后缀表达式，也叫逆波兰式。而在前面的就是前缀表达式，也叫波兰式。这二者的处理方式和中缀表达式一模一样，只不过方便计算机处理，运算快些，歧义少点。中缀表达式转后缀表达式时，要先按照运算顺序打括号。接着把括号看作整体，括号之间的双目运算符放在两括号后，再去掉括号。例如上面的就成了ab+cd-*e+

辛酸网 ©版权所有