什么是栈
我们来看一下百度百科中对栈的定义：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈的实现
栈和数组，链表一样，也是一种线性的数据结构。在有些编程语言中并没有栈这种数据结构，但是要实现一个栈却也简单，通过数组或者链表都可以来实现一个栈。
通过数组实现
在 Java 中，栈（Stack 类）就是通过数组来实现的，下面我们就自己利用数组来实现一个简单的栈：
package com.lonely.wolf.note.stack;
import java.util.Arrays;
/**
* 基于数组来实现自定义栈
*/
public class MyStackByArray<E> {
public static void main(String[] args) {
MyStackByArray stack = new MyStackByArray();
stack.push(1);
System.out.println("stack有效元素个数：" + stack.size);//输出 1
System.out.println("查看栈顶元素：" + stack.peek());//输出 1
System.out.println("栈是否为空：" + stack.isEmpty());//输出 false
System.out.println("弹出栈顶元素：" + stack.pop());// 输出 1
System.out.println("栈是否为空：" + stack.isEmpty());//输出 true
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println("stack有效元素个数：" + stack.size);//输出 3
System.out.println("弹出栈顶元素：" + stack.pop()); //输出 4
}
private Object[] element;//存储元素的数组
private int size;//栈内有效元素
private int DEFAULT_SIZE = 2;//默认数组大小
public MyStackByArray() {
element = new Object[DEFAULT_SIZE];
}
/**
* 判断是否为空，注意不能直接用数组的长度
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 查看栈顶元素
* @return
*/
public synchronized E peek() {
if (size == 0){
return null;
}
return (E)element[size-1];
}
/**
* 查看并弹出栈顶元素
* @return
*/
public E pop() {
if (size == 0){
return null;
}
E obj = peek();
size--;//利用 size 属性省略元素的移除
return obj;
}
/**
* 压栈
* @param item
* @return
*/
public E push(E item) {
ensureCapacityAndGrow();
element[size++] = item;
return item;
}
/**
* 扩容
*/
private void ensureCapacityAndGrow() {
int len = element.length;
if (size + 1 > len){//扩容
element = Arrays.copyOf(element,len * 2);
}
}
}
通过队列实现
除了通过数组，其实通过链表等其他数据结构也能实现，实现栈最关键就是要注意栈的后进先出特性。
在 leetcode 中的第 225 是利用两个队列来实现一个栈，具体要求是这样的：
请你仅使⽤两个队列实现⼀个后⼊先出（LIFO）的栈，并⽀持普通栈的全部四种操作（push、top、pop 和 empty），你只能使用队列的基本操作（也就是 push to back、peek/pop from front、size 和 is empty 这些操作）。
在解决这个问题之前，我们先要明白队列的特性，队列最主要的一个特性就是先进先出，所以我们不管先把元素放到哪个队列，最后出来的元素依然是先进先出，似乎实现不了栈的后进先出特性。
实现思路
为了满足栈的特性，我们就必须要让先入队的元素最后出队，所以我们可以这么做：
使用一个队列作为主队列，每次出栈都从主队列（mainQqueue）获取元素，另外一个队列作为辅助队列（secondQueue），仅仅用来存储元素，每次存储元素的时候先存入 secondQueue，然后将 mainQueue 内的元素依次放入 secondQueue，最后再将两个队列互换，这样每次出队的时候只需要从 mainQueue 依次获取元素即可。
下面我们一起来画一个流程图帮助理解这个过程：
- 放入元素
1。
先将元素放入 secondQqueue，这时候 mainQueue 为空，所以不需要移动元素，直接交换两个队列即可，所以最终得到的依然是 mainQueue 内有一个元素 1，而 secondQueue 中没有元素：
- 继续放入元素
2。
这时候元素 2 依然先放入 secondQqueue，然后此时发现 mainQueue 里面有元素，一次取出来，入队 secondQueue，然后继续将两个队列交换：
- 继续放入元素
3。
继续放入元素 3 也是一样的道理，依然先放入 secondQqueue，然后将 mainQueue 中的两个元素一次放回到 secondQueue，最后再将两个队列进行交换：
大部分算法都是这样，关键是理清思路，思路理清了剩下的就是代码翻译的过程，这个过程只要做好好边界控制及其他注意事项，相对来说就比较容易实现了：
package com.lonely.wolf.note.stack;
import java.util.LinkedList;
import java.util.Queue;
public class MyStackByTwoQueue {
public static void main(String[] args) {
MyStackByTwoQueue queue = new MyStackByTwoQueue();
queue.push(1);
queue.push(2);
System.out.println(queue.pop());
}
private Queue<Integer> mainQueue = new LinkedList<>();
private Queue<Integer> secondQueue = new LinkedList<>();
public void push(int e){
secondQueue.add(e);
if (!mainQueue.isEmpty()){
secondQueue.add(mainQueue.poll());
}
//交换连个 queue，此时新加入的元素 e 即为 mainQueue 的头部元素
Queue temp = mainQueue;
mainQueue = secondQueue;
secondQueue = temp;
}
public int top(){
return mainQueue.peek();
}
public int pop(){
return mainQueue.poll();
}
public boolean empty() {
return mainQueue.isEmpty();
}
}
栈的经典应用场景
因为栈是一种操作受限的数据结构，所以其使用场景也比较有限，下面我们列举几个比较经典的应用场景。
浏览器前进后退
浏览器的前进后退就是典型的先进后出，因为有前进后退，所以我们需要定义两个栈：forwardStack 和 backStack。当我们从页面 1 访问到页面 4，那么我们就把访问过的页面依次压入 backStack：
后退的时候直接从 backStack 出栈就可以了，当 backStack 为空就说明不能继续后退了；而且当从 backStack 出栈的同时又将页面压入 forwardStack，这样前进的时候就可以从 forwardStack 依次出栈：
括号配对
利用栈来验证一个字符串中的括号是否完全配对会非常简单，因为右括号一定是和最靠近自己的一个左括号配对的，这就满足了后进先出的特性。所以我们可以直接遍历字符串，遇到左括号就入栈，遇到右括号就看看是否和当前栈顶的括号匹配，如果不匹配则不合法，如果匹配则将栈顶元素出栈，并继续循环，直到循环完整个字符串之后，如果栈为空就说明括号恰好全部配对，当前字符串是有效的。
leetcode 20 题
在 leetcode 中的第 20 题就是一道括号配对的题，题目是这样的：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。
知道了上面的解题思路，代码实现起来还是比较简单的：
public static boolean isValid(String s){
if (null == s || s.length() == 0){
return false;
}
Stack<Character> stack = new Stack<>();
Map<Character,Character> map = new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
for (int i=0;i<s.length();i++){
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{'){
stack.push(c);//左括号入栈
}else{
if (stack.isEmpty() || map.get(c) != stack.peek()){
return false;
}
stack.pop();//配对成功则出栈
}
}
return stack.isEmpty();
}
表达式求值
算法表达式也是栈的一个经典应用场景，为了方便讲解，我们假设表达式中只有 +、-、*、/ 四种符号，然后我们要对表示式 18-12/3+5*4 进行求解应该如何做呢？
其实这道题也可以利用两个栈来实现，其中一个用来保存操作数，称之为操作数栈，另一个栈用来保存运算符，称之为运算符栈。具体思路如下：
- 遍历表达式，当遇到操作数，将其压入操作数栈。
- 遇到运算符时，如果运算符栈为空，则直接将其压入运算符栈。
- 如果运算符栈不为空，那就与运算符栈顶元素进行比较：如果当前运算符优先级比栈顶运算符高，则继续将其压入运算符栈，如果当前运算符优先级比栈顶运算符低或者相等，则从操作数符栈顶取两个元素，从栈顶取出运算符进行运算，并将运算结果压入操作数栈。
- 继续将当前运算符与运算符栈顶元素比较。
- 继续按照以上步骤进行遍历，当遍历结束之后，则将当前两个栈内元素取出来进行运算即可得到最终结果。
leetcode 227 题
题目：给你一个有效的字符串表达式 s，请你实现一个基本计算器来计算并返回它的值，整数除法仅保留整数部分，s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开。
这道题目可以利用我们上面讲述的思路进行解决，不过除此之外，在审题时我们应该还需要考虑两个点：
- 表达式中有空格，我们需要将空格处理掉
- 操作数可能有多位，也就是说我们需要将操作数先计算出来。
使用两个栈求解
这道题如果我们按照上面的思路，使用两个栈来做的话，虽然代码有点繁琐，但是思路还是清晰的，具体代码如下：
public static int calculateByTwoStack(String s){
if (null == s || s.length() == 0){
return 0;
}
Stack<Integer> numStack = new Stack<>();//操作数栈
Stack<Character> operatorStack = new Stack<>();//运算符栈
int num = 0;
for (int i = 0;i<s.length();i++){
char c = s.charAt(i);
if (Character.isDigit(c)){//数字
num = num * 10 + (c - '0');
if (i == s.length() - 1 || s.charAt(i+1) == ' '){//如果是最后一位或者下一位是空格，需要将数字入栈
numStack.push(num);
num = 0;
}
continue;
}
if (c == '+' || c == '-' || c == '*' || c == '/'){
if (s.charAt(i-1) != ' '){//如果前一位不是空格，那需要将整数入栈
numStack.push(num);
num = 0;
}
if (c == '*' || c == '/'){//如果是乘除法，那么需要将当前运算法栈内的乘除法先计算出来
while (!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')){
numStack.push(sum(numStack,operatorStack.pop()));//将计算出的结果再次入栈
}
} else {//如果是加减法，优先级已经是最低，那么当前运算符栈内所有数据都需要被计算掉
while (!operatorStack.isEmpty()){
numStack.push(sum(numStack,operatorStack.pop()));
}
}
operatorStack.push(c);
}
}
//最后开始遍历：两个操作数，一个运算符进行计算
while (!numStack.isEmpty() && !operatorStack.isEmpty()){
numStack.push(sum(numStack,operatorStack.pop()));//计算结果再次入栈
}
return numStack.pop();//最后一定剩余一个结果入栈了
}
private static int sum(Stack<Integer> numStack,char operator){
int num1 = numStack.pop();
int num2 = numStack.pop();
int result = 0;
switch (operator){
case '+':
result = num2 + num1;
break;
case '-':
result = num2 - num1;
break;
case '*':
result = num2 * num1;
break;
case '/':
result = num2 / num1;
break;
default:
}
return result;
}
上面题目中我们也可以先使用正则把表达式中所有空格去除，这样的话也可以省去空格的判断
使用一个栈求解
其实这道题因为只有加减乘除法，所以我们其实可以取巧，只利用一个栈也可以实现。
因为乘除法一定优先于加减法，所以可以先把乘除法计算出来后将得到的结果放回表达式中，最后得到的整个表达式就是加减法运算，具体做法为：
遍历字符串 s，并用变量 preOperator 记录每个数字之前的运算符，对于表达式中的第一个数字，我们可以默认其前一个运算符为加号。每次遍历到数字末尾时（即：读到一个运算符，或者读到一个空格，或者遍历到字符串末尾），根据 preOperator 来决定计算方式：
- 加号：将数字直接压入栈内。
- 减号：将对应的负数压入栈内。
- 乘/除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。
这样最终只需要将栈内的所有数据相加就可以得到结果，具体代码示例如下：
public static int calculateOneStack(String s){
if (null == s || s.length() == 0){
return 0;
}
Stack<Integer> stack = new Stack<>();
char preOperator = '+';//默认前一个操作符是加号
int num = 0;
for (int i = 0;i<s.length();i++){
char c = s.charAt(i);
if (Character.isDigit(c)){
num = num * 10 + (c - '0');
}
if ((!Character.isDigit(c) && c != ' ') || i == s.length()-1){//判断数字处理是否已经结束，如果结束需要将数字入栈或者计算结果入栈
switch (preOperator){
case '+':
stack.push(num);//加法则直接将数字入栈
break;
case '-':
stack.push(-num);//减法则将负数入栈
break;
case '*':
stack.push(stack.pop() * num);//乘法则需要计算结果入栈
break;
case '/':
stack.push(stack.pop() / num);//除法则需要计算结果入栈
break;
default:
}
preOperator = c;
num = 0;
}
}
int result = 0;
while (!stack.isEmpty()){//最后将栈内所有数据相加即可得到结果
result+=stack.pop();
}
return result;
}
函数调用
除了上面的三个经典场景，其实我们平常的方法调用也是用的栈来实现的，我们每次调用一个新的方法就会定义一个临时变量，并将其作为一个栈帧进行入栈，当方法执行完毕之后，就会将当前方法对应的栈帧进行出栈。
总结
本文主要讲述了栈这种操作受限的数据结构，并通过数组实现了一个简易版的栈，同时讲述了如何通过两个队列实现一个栈。最后我们列举了栈的四大经典应用场景：括号配对，表达式求值，浏览器前进后退，函数调用等，而其中括号配对和表达式求值这两种场景又会衍生出不同的算法题。