前言说完链表，我们再来看看栈。要理解什么是栈，一个经典的类比就是把一栈比作一叠盘子，一个一个地叠起来，然后先拿最上面的，也就是最后叠的那个。先进后出，后进先出，这就是栈结构。实际应用那么栈在实际应用中有哪些场景呢？太多了，比如Activity中的任务栈，编译器实现的方法表达式，浏览器的前进后退等等。这里以浏览器的前进和后退为例。在浏览器中，每打开一个页面，页面就会被压入栈中，然后点击返回时页面被弹出栈。是不是很像Activity页面的任务栈？如果有前向功能，则需要另一个堆栈。点击返回时，页面从A栈中取出，然后进入B栈。这样当你点击forward的时候，就可以从B栈回到A栈了。1）浏览网页，每打开一个网页，就把它压入栈A。比如这里打开了网页M和网页N。2）点击返回，网页N从栈A中弹出，推入栈B。3）点击前进，网页N从栈B中弹出，推入栈A。Java中的stack类在Java中，对应的栈的类是Stack。//初始化栈Stackstack=newStack();//入栈stack.push("test");//出栈并返回出栈元素Stringstr=stack.pop();算法题还是老样子，这里出一道栈相关的算法题。问题给定一个仅包含'(',')','{','}','[',']'的字符串s，判断该字符串是否有效。一个有效的字符串需要满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。示例1：输入：s="()"输出：true示例2：输入：s="()[]{}"输出：true示例4：输入：s="([)]"输出：false示例5:输入：s="{[]}"输出：true解决方案解决方案是使用堆栈。当一个左括号被压入堆栈时，当遇到一个右括号时，相应的左括号被从堆栈中弹出。如果右括号与要出栈的元素不一致，说明括号不成对。关于左右括号的对应关系，可以用HashMap来存储。我们来看一下：publicbooleanisValid(Strings){intn=s.length();if(n%2==1){returnfalse;}Mappairs=newHashMap(){{put(')','(');put(']','[');put('}','{');}};Dequestack=newLinkedList();for(inti=0;istack=newStack();for(charc:s.toCharArray()){if(c=='(')stack.push(')');elseif(c=='{')stack.push('}');elseif(c=='[')stack.push(']');elseif(stack.empty()||c!=stack.pop())returnfalse;}if(stack.empty())returntrue;returnfalse;}时间复杂度需要遍历字符串，所以时间复杂度为O(n)空间复杂度栈字符最大数量为n，Map的数量为3，所以空间复杂度为O(n)。参考https://time.geekbang.org/column/article/41222关注下方二维码。转载本文请联系代码上的积木公众号。
