一小时搞定关于栈的那点事儿，其实挺简单的
1 后入先出的结构
这是一个后入先出的结构，和先入先出的队列恰好相反，下面我们就介绍一下这个后入先出的结构——栈。
在日常使用栈最明显的地方，绝对就是浏览器了，浏览器的前进后退就是使用了栈，每次浏览的网页全部都加入到栈中，每次后退时，就进行出栈的操作即可。
栈也是一种线性结构，只能在一端进行插入和删除的操作，先进入的元素被压入栈底，后进入的元素在栈顶，栈底的位置是固定不变的。
栈所拥有的具体的方法如下：
boolean isFull() ：判断栈是否满
boolean isEmpty() ：判断栈是否空
boolean push(int x) ：入栈
boolean pop() ：出栈
int top()：获取栈顶元素
2 图示入栈与出栈
push 入栈图示 ：
pop 出栈图示 ：
出栈和入栈的时间复杂度都是O(1)
3 使用数组实现栈的数据结构
package com.banana.stack;
public class MyStack {
private int size;
private int[] nums;
private int top;
// 构造函数，声明大小
public MyStack(int size) {
this.size = size;
nums = new int[size];
top = -1;
}
// 出栈
public boolean pop() {
if (isFull()) {
return false;
} else {
top--;
return true;
}
}
// 入栈
public boolean push(int x) {
if (isFull()) {
return false;
} else {
nums[++top] = x;
return true;
}
}
// 判空
public boolean isEmpty() {
return top == -1;
}
// 判满
public boolean isFull() {
return top == (size - 1);
}
// 获取栈顶元素
public int top() {
if (isEmpty()) {
return -1;
} else {
return nums[top];
}
}
}
4 计算1-n的和
计算从1到n的和，最简单的办法是可以用公式方法做，直接(1+n)/2就能得到结果，但是我们使用递归的办法，利用栈的数据结构，也能得到我们想要的结果
package com.banana.stack;
public class SumTest {
public static void main(String[] args) {
System.out.println(Sum(5));
}
private static int Sum(int n) {
if (n == 0) return 0;
return n + Sum(n - 1);
}
}
打个断点，我们就可以看到函数的调用关系，可以很清楚的看到利用栈来进行函数调用，计算结果依次return，就能得到最后的值
函数栈调用关系：
5 括号匹配
应用leetcode上面的一道题，括号匹配，利用栈就可以很好的运算，题目是这样的：
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
使用栈进行匹配，如果遇到左括号就进行入栈操作，如果遇到右括号，那就进行出栈操作和当前的右括号进行匹配，匹配成功就继续，匹配不成功就直接返回
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') stack.push(c);
else if (c == ')') {
if (stack.isEmpty() || stack.pop() != '(') return false;
} else if (c == ']') {
if (stack.isEmpty() || stack.pop() != '[') return false;
} else if (c == '}') {
if (stack.isEmpty() || stack.pop() != '{') return false;
}
}
if (!stack.isEmpty()) return false;
return true;
}
}
其实栈会进行如下的操作进行匹配
6 双栈运算
这部分来自《算法（第四版）》，我觉得实在是相当不错，就放在这里了，算是张涨姿势吧
计算算式 `` 的值，我们使用两个栈来完成这个任务，一个栈用来保存运算符，一个栈用来保存操作数。
表达式由括号、运算符和操作数组成。我们根据以下4种情况从左到右逐个将这些实体送入栈处理：
- 将操作数压入操作数栈
- 将运算符压入运算符栈
- 忽略左括号
- 在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈
package com.banana.stack;
import JAVA.util.Stack;
public class Evaluate {
public static void main(String[] args) {
String str = "(1 + ( (2+3) * (4*5) ) )";
System.out.println(calculate(str));
}
public static double calculate(String str) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
for (int i = 0; i < str.length(); i++) {
String ele = "" + str.charAt(i);
// Neglect the operator "(" and " "
if (ele.equals("(") || ele.equals(" ")) ;
else if (ele.equals("+")) ops.push(ele);
else if (ele.equals("-")) ops.push(ele);
else if (ele.equals("*")) ops.push(ele);
else if (ele.equals("/")) ops.push(ele);
else if (ele.equals(")")) {
String op = ops.pop();
double v1 = vals.pop();
double v2 = vals.pop();
if (op.equals("+")) vals.push(v1 + v2);
if (op.equals("-")) vals.push(v1 - v2);
if (op.equals("*")) vals.push(v1 * v2);
if (op.equals("/")) vals.push(v1 / v2);
} else vals.push(Double.valueOf(ele));
}
return vals.pop();
}
}
这段Stack的用例使用了两个栈来计算表达式的值。它展示了一种重要的计算模型：将一个字符串解释为一段程序并执行该程序得到结果。有了泛型，我们只需实现Stack一次即可使用String值得栈和Double值得栈。
7 写在最后
栈使用得场景相比较队列、链表会少一点，但是它的重要性一点不比它们差，所以一定需要认真得思考与总结，学习完只有进行总结，才能把知识变成自己的。
