摘要本文将介绍数据结构Stack的基本操作及其一些应用。我们将看到Stack应用于括号匹配检测、表达式评估和函数调用。递归是一种特殊的函数调用。由于递归在编程中很重要，也不是很容易理解，所以我将解释一下我对递归的理解。***我们将看到如何使用堆栈和递归优雅地解决一个经典游戏：汉诺塔。本文还将给出表达式求值和汉诺塔的HTML5演示。Stack简介Stack是一个堆栈。以下是维基百科的定义：在计算机科学中，是一种特殊的串行形式的数据结构。添加数据（英文：push）和输出数据（英文：pop）的操作是针对栈顶指标进行的，英文：top）。此外，堆栈还可以以一维数组或串联的形式完成。根据定义，我们知道对栈的操作只有三种：入栈（push）、出栈（pop）、获取栈顶元素（top）。并且栈只能操作栈顶元素，即只能对一端进行操作。由于栈具有后进入的元素先弹出的特性，所以栈又称为后进先出（LIFO，LastInFirstOut）结构。栈的操作非常简单。我们可以用一个单链表（LinkedList）和一个数组来实现栈。但是在JavaScript中，Array自带了pop()、push()操作，我们可以使用Array[Array.length-1]来实现top()操作。所以不需要再实现一个Stack类型，直接用Array来表达即可。后进先出使用Stack的特点使其适用于解决很多实际问题。下面我们选取它的三个应用来说明。括号匹配检测我们平时在编辑器中写代码的时候，有些编辑器会自动检测前后括号是否匹配，如果不匹配就会报错。利用Stack的后进先出特性，我们可以轻松实现这个功能。该算法的伪代码如下：//新建一个Stackss=newstack()//读取字符直到结束whilereadtoc!=EOF://如果字符是左括号如'(''[''{'等，将它们压入栈中栈顶元素与左括号不匹配，会报错ifsisemptyorfs.pop()isnotcorrespondtoc:returnerror!//如果***栈不为空，则报错ifisnotempty:returnerror!//如果没有返回错误，则恢复正常。*左括号是否匹配，如果没有找到左括号则报错，或者***左括号不匹配。因为我们总是而且只需要找到最后一个元素，所以我们将左括号压入堆栈并在匹配时将其弹出。由于Stack的特性，该算法简单明了，消耗的时间复杂度为线性级别O(n)。expressionevaluationStack的强大特性也使其可以用于表达式求值。想象一个表达式：2+4/(3-1)这个表达式有三种类型的符号：操作数：2422运算符：+/-括号：()计算它的算法如下：//分配两个堆栈,ops为运算符栈,nums为栈号ops=newStack,nums=newStack//从表达式中读取字符直到结束whilereadcinexpression!=EOF://如果是左括号，则进入运算符栈ifcis'(':ops.push(c)//如果是数字，则放入数字栈elseifcisanumber:nums.push(c)//如果是运算符elseifcisanooperator://如果运算符栈的栈顶元素是higherthanclevel如果level高或者同level，则执行单个操作whileops.top()isequalorprecedenceoverc:op=ops.pop()opn2=nums.pop()opn1=nums.pop()//执行单次操作，把操作数压栈nums.push(cal(op,opn1,opn2))//如果是右括号elseifcis')'://除非栈顶元素是左括号,运算符栈will被出栈，计算结果放入数栈op=ops.pop()whileop!='(':opn2=nums.pop()opn1=nums.pop()nums.push(cal(op,opn1,opn2))op=ops.pop()//返回数栈的栈顶元素returnnums.top()下面是表达式求值的DEMO：函数调用我们在调试代码的时候，经常会发现如下遇到函数错误时类似的错误提示：/Users/tim/Codes/JavaScript/dsaginjs/DSinJS/Stack/InfixExpression.js:59returnprioty[a])prioty[b];^SyntaxError:Unexpectedtoken)atModule._compile(module.js:439:25)atObject.Module._extensions..js(module.js:474:10)atModule.load(module.js:356:32)atFunction.Module。_load(module.js:312:12)atFunction.Module.runMain(module.js:497:10)atstartup(node.js:119:16)atnode.js:902:3其实我们只是错了一个地方，为什么打印出这么多错误信息怎么办？原因是解释器打印出了报错函数传递的所有调用函数的栈。当函数被调用时，我们需要切换到被调用的函数，但是一旦函数调用结束，我们又要回到原来的位置。使用栈，我们可以有序的实现，即在调用函数时，我们将当前函数的变量和上下文压入栈中，当函数调用结束时，弹出栈得到先前的上下文和变量。#p#递归函数调用的一个特例是调用自身，称为递归。最简单的例子，求解阶乘：functionfactorial(n){returnn==0?1:n*factorial(n-1);}递归是一个非常有用的工具，但新手往往难以理解。先说说对递归的理解吧。递归需要终止条件，否则会无限递归每次递归都需要缩小问题范围，否则不满足终止条件，就会无限递归很明显，递归调用了自己，这和我们照镜子很像在一家理发店。如果没有终止条件，我们永远不知道还剩下多少个自己。其实用递归解决问题的本质就是找到比原问题更小的问题，并且可以用同样的方法处理。此外，我们还需要判断递归何时结束，即判断递归的终止条件。例如求阶乘：我们如何求3的阶乘？3的阶乘等于3的阶乘加2的阶乘。我们怎么求2的阶乘呢？2的阶乘等于2和1的阶乘。我们怎么求1的阶乘呢？0的乘法和阶乘我们如何找到0的阶乘？我们不需要求0的阶乘，因为我们知道0的阶乘是1。这样分析问题，如何求n的阶乘呢？答案是：如果n为0，则返回1，否则返回n乘以n-1的阶乘。于是我们得到了阶乘的递归表达式：functionfactorial(n){returnn==0?1:n*factorial(n-1);}factorial的递归终止条件是n==0；缩小问题范围的方法是发现n-1的问题和n的问题是一致的。显然，递归的基础是函数调用，而函数调用的基础是Stack。所以，每次递归的开销就是需要不断的进行入栈和出栈操作，会消耗大量的空间，也可能造成冗余操作。解决办法可能是：尾递归，动态规划。河内塔河内塔是一款经典游戏。它的维基百科描述是：有A、B、C三个杆子，A杆上有N（N>1）个穿孔圆盘，圆盘的尺寸从下往上变小。要求将所有圆盘按照以下规则移动到C杆上：一次只能移动一个圆盘；大圆盘不能叠放在小圆盘上面。汉诺塔的解法有很多种，我认为最优雅的解法是递归法，如果你不知道汉诺塔的解法，请先尝试递归求解再继续往下看。好吧，我承认我一开始并没有弄清楚如何使用递归来解决它，但是在阅读了它的解决方案之后，我认为它是优雅而微妙的。汉诺塔递归方法的伪代码如下：//根据规则将n个盘子从a列移动到c列hanoi(n,a,b,c){if(n>0){hanoi(n-1,a,c,b);//将a列的顶板移动到c列c.push(a.pop());河内（n-1，b，a，c）；}}整个算法思路是：暂时把a列的n-1个盘子移动到b列，a列只剩下***个盘子，移动到目标列c***再移动n-1platesonthebcolumnn-1platesonthetargetcolumnc问题的收窄策略是我们如何将n个plates从a移动到c，这同样适用于n-1个plates从a移动到c。当n已经减到3时，我们先把最上面的两个盘子移到b，然后把最高的盘子移到c，再把b上的两个盘子移到c。当n减少到2时，问题终于变得直观了。我们将顶板移动到b，然后将底板移动到c，最后将b的板移动到c。当n减为1时，我们直接把a的顶板移到c就OK了。这是问题的终止条件。该算法的时间复杂度是指数级的O(2^n)。有关详细信息，请参阅河内塔的复杂性？。最少的求解步骤是2^n-1。河内塔的传说：相传印度某座神庙中有三根柱子，上面串着64块金盘。寺院的僧侣按照古老的预言，按照上述规则移动盘子；预言说，当盘子被移动时，世界就会灭亡。这个传说叫做梵天之塔。如果传说属实，僧侣需要2^64?1步才能完成这个任务；如果它们每秒能完成一个板块的运动，则需要5846亿年才能完成。整个宇宙现在只有137亿岁-.-！以下是河内塔的demo：原文链接：http://wuzhiwei.net/ds_app_stack/
