目录栈特点：先进后出（FILO）使用场景：十进制转二进制函数调用栈js中没有栈，但是可以用数组模拟42/242%2=021/221%2=110/210%2=05/25%2=12/22%2=01/21%2=1堆栈：[0,1,0,1,0,1]res:101010fn1(){fn2()}fn2(){fn3()}fn3(){}fn1()stack：[fn1,fn2,fn3]stack的时间复杂度：压入和弹出O(1)，查找O(n)946。验证堆栈序列（中）给定两个序列pushed和popped，每个序列中的值不重复，只有当它们可能在初始值时返回true如果一系列push和pop操作的结果在空堆栈上;否则，返回假。示例1：输入：pushed=[1,2,3,4,5],popped=[4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1),推(2)、推(3)、推(4)、弹出()->4、推(5)、弹出()->5、弹出()->3、弹出()->2、弹出()->1示例2：输入：pushed=[1,2,3,4,5],popped=[4,3,5,1,2]输出：false解释：1不能在2之前弹出。Tips:1<=pushed.length<=10000<=pushed[i]<=1000pushed的所有元素都是互不相同的。popped.length==pushed.lengthpopped是push过大的排列动画。点击查看思路：使用栈模拟在出栈和入栈的过程中，当popped中index指向的位置的元素与栈顶元素一致时，出栈和index++，最后判断栈是否为空。复杂度：时间复杂度O(n)，在pushed元素被push和pop一次，空间复杂度为O(n)，栈的大小为js:constvalidateStackSequences=(pushed,popped)=>{conststack=[];//利用栈来模拟出栈和入栈的过程letindex=0;constlen=pushed.length;for(leti=0;ii+j,0);};155.最小栈(easy)设计一个栈，支持push、pop、top操作，可以在常数时间内取出最小的元素。实现MinStack类：MinStack()初始化堆栈对象。voidpush(intval)将元素val压入堆栈。voidpop()移除栈顶元素。inttop()获取栈顶元素。intgetMin()获取堆栈中的最小元素。示例1：输入：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]输出：[null,null,null,null,-3,null,0,-2]解释：MinStackminStack=newMinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();-->返回-3.minStack.pop();minStack.top();-->返回0.minStack.getMin();-->返回-2。提示：-231<=val<=231-1pop、top和getMin操作总是在非空栈上调用push、pop、top和getMin调用3*104次思路：定义两个栈stack和min_stack，栈为正常压入，而min_stack只会压入需要压入栈顶的较小的元素。getMin返回min_stack的栈顶元素，top返回栈顶元素。复杂度：所有操作的时间复杂度为O(1)js:varMinStack=function(){this.stack=[];this.min_stack=[Infinity];};//正常压栈，min_stack只会压栈MinStack.prototype.push=function(x){this.stack.push(x);this.min_stack.push(Math.min(this.min_stack[this.min_stack.length-1],x));};//栈正常出栈，min_stack正常出栈MinStack.prototype.pop=function(){this.堆栈弹出（）；this.min_stack.pop();};//返回栈顶元素MinStack.prototype.top=function(){returnthis.stack[this.stack.length-1];};//返回min_stack栈顶元素MinStack.prototype.getMin=function(){returnthis.min_stack[this.min_stack.length-1];};232.使用栈实现队列（简单）请只使用两个栈实现先进先出队列。队列应该支持一般队列支持的所有操作（push、pop、peek、empty）：实现MyQueue类：voidpush(intx)将元素x推到队列的末尾intpop()从队列的开头intpeek()返回队列开头的元素booleanempty()如果队列为空则返回true；否则，返回false解释：你只能使用标准的堆栈操作——也就是说，只有压入顶部、从顶部查看/弹出、大小和为空操作是合法的。您的语言可能不支持堆栈。可以用list或者deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。示例1：输入：["MyQueue","push","push","peek","pop","empty"][[],[1],[2],[],[],[]]输出：[null,null,null,1,1,false]解释：MyQueuemyQueue=newMyQueue();myQueue.push(1);//队列是：[1]myQueue.push(2);//队列是：[1,2]（最左边是队列的前面）myQueue.peek();//返回1myQueue.pop();//返回1，队列是[2]myQueue.empty();//returnfalsehint:1<=x<=9假设所有操作都有效，调用push、pop、peek和empty最多100次（例如，空队列不会调用pop或peek操作）advanced:你能实现吗每个操作具有O(1)分摊时间复杂度的队列？换句话说，执行n个操作的总时间复杂度是O(n)，即使其中一个操作可能需要更长的时间。方法一、栈动画过大，点击查看思路：这是一道模拟题，不涉及具体算法，考察对栈和队列的掌握程度。用一个栈来模拟一个队列的行为，如果只用一个栈肯定行不通，所以需要两个栈，一个输入栈，一个输出栈。这里，要注意输入栈和输出栈的关系。压入数据的时候，只要把数据放入输入栈就可以了，但是出栈的时候，操作就比较复杂了。如果输出栈为空，则将所有数据导入栈中（注意是全部导入），然后从输出栈中弹出数据。如果输出栈不为空，可以直接出栈。最后，如果push和pop都为空，说明模拟队列为空。复杂度分析：push的时间复杂度为O(1)，pop的时间复杂度为O(n)。因为pop时输出栈是空的，所以输入栈的所有元素都加入到输出栈中。空间复杂度O(n)，两个栈空间js:varMyQueue=function(){//准备两个栈this.stack1=[];this.stack2=[];};MyQueue.prototype.push=function(x){//添加输入栈时推送this.stack1.push(x);};MyQueue.prototype.pop=function(){constsize=this.stack2.length;if(size){//push时判断输出栈是否为空returnthis.stack2.pop();//不为空则出栈}while(this.stack1.length){//输出栈为空，则将输入栈中的所有元素添加到输出栈中this.stack2.push(this.stack1.pop());}returnthis.stack2.pop();};MyQueue.prototype.peek=function(){constx=this.pop();//查看队头元素并复用pop方法，然后将元素压入输出栈this.stack2.push(x);returnx;};MyQueue.prototype.empty=function(){return!this.stack1.长度&&!this.stack2.length};20.有效括号(easy)给定一个只包含'(',')','{','}','[',']'的字符串s，判断该字符串是否有效。一个有效的字符串需要满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例1：输入：s="()"输出：true示例2：输入：s="()[]{}"输出：true示例3：输入：s="(]"输出：false提示：1<=s.length<=104sonlyconsistsofbrackets'()[]{}'方法一、堆栈思路：首先，如果字符串能形成有效的括号，长度一定是偶数。我们可以遍历字符串，遇到左边的括号是暂存的，预计会有右括号与之匹配，如果遇到右括号，则检查是否可以与上次暂存的括号匹配，这个符合特性栈的数据结构。。所以我们可以准备一个栈来存放括号对。在遍历字符串的时候，如果遇到左括号入栈，判断右括号是否能匹配到栈顶元素遇到右括号时的栈，在循环结束的时候，还要判断栈是否为空，如果没有t,不是括号匹配的有效字符串复杂度分析：时间复杂度O(n)，空间复杂度O(n)，n为字符串长度js:varisValid=function(s){constn=s.长度;if(n%2===1){//如果字符串能组成有效括号，则长度必须为偶数returnfalse;}constpairs=newMap([//使用栈来存储括号对[')','('],[']','['],['}','{']]);常量stk=[];for(letchofs){//循环字符串if(pairs.has(ch)){//遇到右括号，判断右括号是否能匹配栈顶元素if(!stk.length||stk[stk.length-1]!==pairs.get(ch)){返回false;}stk.pop();}else{stk.push(ch);//将左括号压入栈}};return!stk.length;//循环结束时，需要判断栈是否为空};视频讲解：传送门
