一小时搞定关于栈的那点事儿，其实挺简单的 _栈

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;
}
}
其实栈会进行如下的操作进行匹配