课程名称:JavaScript版数据结构与算法
课程章节： 数据结构之“栈”
课程讲师： lewis
课程内容：

课程介绍

栈简介
什么场景下用栈
LeetCode：20.有效的括号
前端与栈：JS 中的函数调用堆栈
LeetCode：144. 二叉树的前序遍历

一、什么是堆栈

Stack是一种高效率的数据结构，相比List，它仅支持在一端（尾部）进行存取操作，即常说的后进先出LIFO。在计算机底层和编程语言内部实现中以及现实问题中都有广泛的应用。

举例：洗盘子。用过的盘子一个一个叠放，那么最上面的盘子先洗，然后是下面的，洗的过程叫做入栈。
洗完后，最后洗完的在最上面，开始使用从最后洗完的开始依次倒着使用，这个就叫出栈。
同理： 家里的冰柜，最先放进去的在最下层，最后放进去的在最上层，打开后也是从最后放入的进行使用。

二、栈的作用原理

一个函数设计里面，有2个问题：

1.参数传递
传递参数的目的，是为了代码可以重用，让一种方法可以应用到更多的场合，而不需要为N种情况写N套类似的代码。那用什么方法来做参数的传递？可以选择:

a.为了速度快，使用cpu的寄存器传递参数。这会碰到一个问题，cpu寄存器的数量是有限的，当函数内再想调用子函数的时候，再使用原有的cpu寄存器就会冲突了。想利用寄存器传参，就必须在调用子函数前把寄存器存储起来，然后当函数退出的时候再恢复。

b.利用某些ram（随机存取存储器）的区域来传递参数。这和上面a的情况几乎一样，当函数嵌套调用的时候，还是会出现冲突，依然面临要把原本数据保存到其他地方，再调用嵌套函数。并且保存到什么地方，也面临困难，无论临时存储到哪里，都会有上面传递参数一样的困境。

2.函数里面也有可能要使用到局部变量，而不能总是用全局变量。则局部变量存储到哪里合适，即不能让函数嵌套的时候有冲突，又要注重效率。

以上问题的解决办法，都可以利用栈的结构体来解决：
1）寄存器传参的冲突，可以把寄存器的值临时压入栈里面，非寄存器传参也可以压入到栈里面。
2）局部变量的使用也可以利用栈里面的内存空间，只需要移动下栈指针，腾出局部变量占用的空间。最后利用栈指针的偏移来完成存取。于是函数的这些参数和变量的存储演变成记住一个栈指针的地址，每次函数被调用的时候，都配套一个栈指针地址，即使循环嵌套调用函数，只要对应函数栈指针是不同的，也不会出现冲突。
3）利用栈，当函数不断调用的时候，不断的有参数局部变量入栈，栈里面会形成一个函数栈帧的结构，一个栈帧结构归属于一次函数的调用。栈的空间也是有限的，如果不限制的使用，就会出现典型的栈溢出的问题。有了栈帧的框架在，我们在分析问题的时候，如果能获取到当时的栈的内容，则有机会调查当时可能出现的问题。

举个栗子：
使用堆栈可以方便的将一个10进位数n转换为b进位数，方法如下：

将n%b的结果存入堆栈，即为对应b进位数的最低位
用n/b替换n
重复步骤1和2，只到n为0
将堆栈中所有数字弹出，即得到完整的b进位数

function mulBase(num, base) {
   var s = new Stack();
   do {
      s.push(num % base);
      num = Math.floor(num /= base);
   } while (num > 0);
   var converted = "";
   while (s.length() > 0) {
      converted += s.pop();
   }
   return converted;
}

// 验证mulBase的正确性
var num = 32;
var base = 2;
var newNum = mulBase(num, base);
print(num + " converted to base " + base + " is " + newNum);
num = 125;
base = 8;
var newNum = mulBase(num, base);
print(num + " converted to base " + base + " is " + newNum);

三、总结

堆栈和队列是计算机数据结构和算法中的底层机制，对其有深入的了解才能在算法领域有所建树。