前言
说完了链表，我们再看看栈。
理解栈
栈是什么，很金典的比喻就是把 栈 比喻成叠盘子，一个个叠上去，然后拿的时候会先拿最上面的，也就是最后叠上去的那个。
先进者后出、后进者先出，这就是栈结构。
实际应用
那么栈在实际应用中有什么场景呢？
可太多了，比如Activity中的任务栈，编译器实现方法表达式，浏览器的前进后退。
这里拿浏览器的前进后退做例子。
- 在浏览器中，每打开一个页面，就把这个页面入栈，然后点击后退的时候就将页面出栈。这是不是挺像Activity页面的任务栈的。
- 如果有前进功能，那么就再需要一个栈，当点击后退的时候，就把页面从A栈出，然后进入B栈，这样点击前进的时候，就能从B栈重新回到A栈了。
1）浏览网页，每打开一个网页就入栈A。比如这里打开了网页M和网页N。
2）点击后退，网页N出栈A，入栈B。
3）点击前进，网页N出栈B，入栈A。
Java中的栈类
在Java中，栈的对应类为Stack。
//初始化栈 Stack<String> stack =new Stack<String>(); //入栈 stack.push("test"); //出栈，返回出栈的元素 String str=stack.pop();
算法题
还是老样子，来一题栈相关的算法题。
题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例 1：输入：s = "()" 输出：true
示例 2：输入：s = "()[]{}" 输出：true
示例 4：输入：s = "([)]" 输出：false
示例 5：输入：s = "{[]}" 输出：true
解法
解法就是利用栈了。
遇到左括号入栈，遇到右括号就把相应的左括号出栈，如果右括号和要出栈的这个元素不一致，就说明括号没有成对。
关于左括号和右括号的对应关系，可以用HashMap来存储，来一起看看：
public boolean isValid(String s) { int n = s.length(); if (n % 2 == 1) { return false; } Map<Character, Character> pairs = new HashMap<Character, Character>() {{ put(')', '('); put(']', '['); put('}', '{'); }}; Deque<Character> stack = new LinkedList<Character>(); for (int i = 0; i < n; i++) { char ch = s.charAt(i); if (pairs.containsKey(ch)) { if (stack.isEmpty() || stack.peek() != pairs.get(ch)) { return false; } stack.pop(); } else { stack.push(ch); } } return stack.isEmpty(); }
也有比较灵活的办法，就是入栈的时候就确定好括号的对应关系，直接入栈左括号对应的右括号。
public boolean isValid(String s) { if(s.isEmpty()) return true; Stack<Character> stack=new Stack<Character>(); for(char c:s.toCharArray()){ if(c=='(') stack.push(')'); else if(c=='{') stack.push('}'); else if(c=='[') stack.push(']'); else if(stack.empty()||c!=stack.pop()) return false; } if(stack.empty()) return true; return false; }
时间复杂度
需要遍历字符串，所以时间复杂度为 O(n)
空间复杂度
栈的字符数量最大为n，Map数量为3，所以空间复杂度就是O(n)
