一、栈
1、特点及应用
先进后出。（如果会和队列先进先出记混的话，就记场景吧：弹栈弹栈，就是把最上面的最新进来的弹出去；而队列就像我们火车站排队检票出站一样，谁排在前面谁就先出去。）
应用的话，其实我们经常接触呀。比如Undo操作（就是撤销操作）就是使用的栈的思想，以及程序调用的系统栈。下面我们举一个经典的括号匹配的例子：
题目要求：
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
解题思路：第一想到的应该就是用栈来做。如果是 { （ [ 之中的，就直接压入栈，如果有出现了 ) } ] 之间的，就开始匹配。先从栈顶的元素开始匹配，如果不同则直接返回false；如果相同则继续匹配，直到栈里ianshi空的。
源码如下：
import java.util.Stack;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 (stack.isEmpty())return false;char top = stack.pop();if (c == ')' && top != '(')return false;if (c == '}' && top != '{')return false;if (c == ']' && top != '[')return false;}}return stack.isEmpty();}
}二、队列
先进先出。
1、循环队列
循环队列是很常见的数据结构，在大学计算机课程上也会遇到，被应用到很多场景，比如管道的实现（固定的容量64K）、MapReduce中数据溢写入磁盘（默认100M，超过80M溢写）、网络库中常见的IO buffer等等。
循环队列需要两个索引front和tail，分别指向队列头和尾（下次要放入的下标），假设队列长度为length：
