0x00 栈
栈是一种操作受限的线性表，只允许一端插入和删除数据，相比数组和链表，栈的操作只有限制
事实上，在功能上数组和链表确实可以替代栈，栈的底层一般也是数组或链表实现的，但是
特定的数据结构是对特定场景的抽象，而且数组或链表暴露了太多的接口，操作上灵活自由，但使用起来也比较不可控，很容易出错
当某个数据只涉及在一端插入或删除数据，并且满足先进后出、后进先出的特性，我们就应首选栈
0x01 栈实现
- 数组实现
// n:栈的大小 items:栈中的元素 count:栈中元素的个数
case class ArrayStack(n:Int,items:Array[String]) {
// 栈中元素个数
var count=0
// 入栈
def push(item:String): Boolean ={
// 栈满了，返回false
if (count == n){
return false
}
items(count) = item
count += 1
true
}
// 出栈
def pop(): String ={
// 栈为空 返回null
if (count == 0){
return null
}
count -= 1
items(count)
}
// 清空栈
def clear(): Unit ={
count = 0
}
}
- 链表实现
class LinkedStack {
var head:Option[Node] = None
var size:Int = 0
// 入栈
def push(value:Int): Boolean ={
head = Option(Node(value,head))
size += 1
true
}
// 出栈
def pop(): Option[Node] ={
if (size==0){
return None
}
val item = head
head = head.get.next
size -=1
item
}
// 清空栈
def clear(): Unit ={
size = 0
head = None
}
}
0x02 应用
- 函数调用栈
操作系统给每个线程分配了独立的内存空间，这块内存被组织成栈这种数据结构，用来保存函数调用的临时变量，当一个函数调用完成，就全部弹栈，然后执行下一个函数，以此来维护函数调用链
- 四则运算
我们人常见的四则运算，例如 1-3*4+4/2 对于电脑来说并不好识别执行的先后顺序，一般会使用栈来计算，专栏中介绍了一种依靠两个栈实现的方式，还有一种逆波兰表达式也叫后缀表达式的方法求解
1、两个栈实现
一个栈存储数字，一个栈存储运算符，从左到右遍历运算式，如果是数字就压栈，如果是运算符，就与运算符栈的栈顶元素比较，如果比栈顶运算符优先级高，就压栈，如果优先级低或相同，则从数字栈取两个数字，从栈顶取一个操作符计算，并将结果压入数字栈，然后继续比较栈顶运算符和当前运算符的优先级
不包含括号的版本，如果包含小括号，可以把右括号优先级设为最小，左括号优先级设为最大，然后特殊处理一下左右括号
// 只有+-*/ 不包含括号
def caculate(express:String): Long ={
val addInt = '+'.toInt
val minusInt = '-'.toInt
val multiInt = '*'.toInt
val divideInt = '/'.toInt
val symbolMap = Map(addInt->1,minusInt->1,multiInt->2,divideInt->2)
val numStack = new LinkedStack
val symbolStack = new LinkedStack
// 前一个是否是数字
var preIfNum = true
// 数字栈栈顶放一个0 表达式第一个一定是数字，这样不用对头做特殊处理
numStack.push(0)
for (s <- express){
var i = s.toInt - 48
// 0-9
if(i >= 0 && i<=9){
// 如果前一个字符也是数字，那么将前一个*10加上当前数字然后入栈
if (preIfNum){
i += 10*numStack.pop().get.data
}
numStack.push(i)
preIfNum=true
}else{
preIfNum = false
var preSymbol = symbolStack.pop()
while (preSymbol.isDefined){
// 如果当前的运算符优先级小于等于上一个运算符，则计算上一个运算符
if (symbolMap(preSymbol.get.data) >= symbolMap(s.toInt)){
val a = numStack.pop().get.data
val b = numStack.pop().get.data
val res = preSymbol.get.data match {
case `addInt` => b+a
case `minusInt` => b-a
case `multiInt` => b*a
case `divideInt` => b/a
}
numStack.push(res)
preSymbol = symbolStack.pop()
}else{
// 放回弹出的上一个运算符，跳出循环
symbolStack.push(preSymbol.get.data)
preSymbol = None
}
}
// 将当前运算符放入栈
symbolStack.push(s.toInt)
}
}
// 计算栈中剩下的数据
var symbol = symbolStack.pop()
while (symbol.isDefined){
val a = numStack.pop().get.data
val b = numStack.pop().get.data
val res = symbol.get.data match {
case `addInt` => b+a
case `minusInt` => b-a
case `multiInt` => b*a
case `divideInt` => b/a
}
numStack.push(res)
symbol = symbolStack.pop()
}
numStack.pop().get.data
}
2、逆波兰表达式
逆波兰表达式又叫后缀表达式，这种方法是先将我们常见的中缀表达式转换成后缀表达式，例如：(2+3)*5 => 2 3 + 5 * 运算符在两个计算数字后面，这样方便计算机程序判断计算，使用一个栈就可以完成，详细代码见GitHub代码的caculate3方法
- 括号匹配
常见的算法题中还有括号匹配，小括号、中括号、打括号，任意组合，判断是够匹配，例如：[{()}([])]匹配，可以通过栈来实现
GitHub
def isValid(s:String): Boolean ={
val bracket = Map('('->')','['->']','{'->'}')
val stack = mutable.Stack[Char]()
for (c <- s){
if (bracket.contains(c)){
stack.push(c)
}else{
if(stack.isEmpty || c != bracket(stack.pop())){
return false
}
}
}
if (stack.nonEmpty){
return false
}
true
}
0x03 课后思考
1、我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用栈来保存临时变量，用其他数据结构行不行？
保存临时变量可以用很多种数据结构，使用栈只是因为符合先进后出的场景，对于函数调用来说，从调用函数进入被调用函数，最主要的变化是作用域，所以只要能保证进入调用函数后能方便的切换作用域就可以，而当进入被调用函数时，使用栈存储新的函数变量，当函数调用完成，将栈顶复位，正好可以直接回到调用函数
2、java内存管理中有堆栈的概念，栈内存用来存储局部变量和方法调用，堆内存用来存储java中的对象，java中的栈和我们数据结构中的栈是不是一回事？如果不是为什么也称为栈呢？
按我的理解，java内存管理中的栈和栈可以是一回事，因为内存管理中的栈也是一种组织内存数据的方式，满足先进后出的实现，但是，可能提供了更多的功能，所以可以认为是一回事
节选专栏评论区小邓的评论：
课后思考问题2是多次困扰我的一个问题：内存管理上的“栈”和数据结构上的“栈”到底是不是一回事。
按出题套路而言，问“如果不是，给出理由”的问题答案大多是“不是”。高赞留言里有的说是，有的说不是，我简单翻了翻三大本厚书《C#图接教程》、《算法》、《深入理解计算机基础》，再去翻了翻相关博客和知乎，我的回答是“不是”。
（1）首先，在内存管理和数据结构上，都有“堆”和“栈”这两个概念。
（2）内存管理上的“堆”和“栈”，强调的是数据的生命周期（分配释放是否有次序要求）；数据结构上的“堆”和“栈”，强调的是数据的组织。
（3）内存管理上的“栈”符合数据结构的“栈”的特点，即LIFO，两者同名可以接受。
（4）数据结构上的“堆”定义：它是一种数组对象，它可以被视为一科完全二叉树结构；应用场景包括堆排序，优先队列等。和内存管理的“堆”定义不同（这里我不是很确定，没有看过内存管理上堆的实现细节）。
参考：
（1）数据结构之“堆”：http://www.cnblogs.com/Jason-Damon/archive/2012/04/18/2454649.html
（2）专题 | 堆、栈简介：https://zhuanlan.zhihu.com/p/45597548
（3）知乎| 为什么c++中要分为heap（堆）和stack（栈）? - Milo Yip的回答：https://www.zhihu.com/question/281940376/answer/424990646
