type
status
date
slug
summary
tags
category
icon
password
Property
栈（Stack）是一种后进先出（LIFO：Last In First Out）的数据结构。
只能不断地往
Stack中压入（push）元素，最后进去的必须最早弹出（pop）来。Stack只有入栈和出栈的操作：- 把元素压栈：
push(E)
- 把栈顶的元素“弹出”：
pop()
- 取栈顶元素但不弹出：
peek()
在Java中，用
Deque可以实现Stack的功能：- 把元素压栈：
push(E)/addFirst(E)
- 把栈顶的元素“弹出”：
pop()/removeFirst()
- 取栈顶元素但不弹出：
peek()/peekFirst()
为什么Java的集合类没有单独的
Stack接口呢？因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了。把
Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。Stack的作用
Stack在计算机中使用非常广泛，JVM在处理Java方法调用的时候就会通过栈这种数据结构维护方法调用的层次：
JVM会创建方法调用栈，每调用一个方法时，先将参数压栈，然后执行对应的方法；当方法返回时，返回值压栈，调用方法通过出栈操作获得方法返回值。
因为方法调用栈有容量限制，嵌套调用过多会造成栈溢出，即引发
StackOverflowError：对整数进行进制的转换就可以利用栈
例如，要把一个
int整数12500转换为十六进制表示的字符串，如何实现这个功能？首先准备一个空栈：
然后计算12500÷16=781…4，余数是
4，把余数4压栈：
然后计算781÷16=48…13，余数是
13，13的十六进制用字母D表示，把余数D压栈：
然后计算48÷16=3…0，余数是
0，把余数0压栈：
最后计算3÷16=0…3，余数是
3，把余数3压栈：
当商是
0的时候，计算结束，把栈的所有元素依次弹出，组成字符串30D4，这就是十进制整数12500的十六进制表示的字符串。计算中缀表达式
在编写程序的时候，我们使用的带括号的数学表达式实际上是中缀表达式，即运算符在中间，例如：
1 + 2 * (9 - 5)。但是计算机执行表达式的时候，它并不能直接计算中缀表达式，而是通过编译器把中缀表达式转换为后缀表达式，例如：
1 2 9 5 - * +。这个编译过程就会用到栈。我们先跳过编译这一步（涉及运算优先级，代码比较复杂），看看如何通过栈计算后缀表达式。
计算后缀表达式不考虑优先级，直接从左到右依次计算，因此计算起来简单。首先准备一个空的栈：
然后我们依次扫描后缀表达式
1 2 9 5 - * +，遇到数字1，就直接扔到栈里：
紧接着，遇到数字
2，9，5，也扔到栈里：
接下来遇到减号时，弹出栈顶的两个元素，并计算
9-5=4，把结果4压栈：
接下来遇到
*号时，弹出栈顶的两个元素，并计算2*4=8，把结果8压栈：
接下来遇到
+号时，弹出栈顶的两个元素，并计算1+8=9，把结果9压栈：
扫描结束后，没有更多的计算了，弹出栈的唯一一个元素，得到计算结果
9。