什么是栈？我们在日常编码中会遇到很多。很多人接触栈可能仅限于栈的递归使用和StackOverflowException。堆栈是一种后进先出的数据结构（你可以想象生化金字塔的牢房和生物竞技场的狗洞）。栈简单却不简单，因为直接学栈比较容易，但是用栈解决问题往往需要巧妙的方法。本篇重点介绍栈数据结构的设计与实现，然后在文末补充两道非常非常经典的关于栈的问题！你一定知道！它带回了一波回忆。栈的定义是这样的：栈（stack），又称堆栈，是一个有限操作的线性表。将插入和删除操作限制在列表末尾的线性列表。这一端称为栈顶，另一端称为栈底。向栈中插入一个新元素也称为压入、压入或压入。就是将新元素放到栈顶元素的最上面，使其成为新的栈顶元素；从堆栈中删除元素也称为入栈或出栈。unstack，就是删除栈顶元素，让相邻的元素成为新的栈顶元素。简单介绍一下关键术语：有限操作：就是不能随便删除和插入这个表。插入和删除只能按照它的规则进行。例如，一个栈只能在一端插入和删除。同样，队列也有操作限制，只能在两端操作。线性表：栈也是线性表的一种。前面详细介绍过线性表，它表达的是数据的一种逻辑关系。也就是说，栈中的每个元素都是相邻的。当然，在具体实现上，也分为组和链表，它们的物理存储结构是不同的。但是逻辑结构（实现的目的）是一样的。栈顶和栈底：这个描述是偏向于逻辑内容的，因为大家都知道在数组的末尾更容易插入和删除，通常在数组的头部更容易插入和删除单链表。所以数组可以用尾作为栈顶，链表可以用头作为栈顶。栈的应用：栈的应用很广泛，比如查看你的程序执行时的调用栈，计算机的四次加减运算，算法的非递归形式，括号匹配问题等等在。所以栈也是一种必须要掌握的数据结构。最简单的是，每个人都经历过。当你上下堆叠一本书时，这是一个后进先出的过程。你可以把它想象成一个堆栈。下面我们分别介绍数组实现的栈和链表实现的栈。数组实现数组实现的堆栈使用得更多。我们经常用数组来实现一个简单的栈来解决简单的问题。结构设计对于数组，我们模拟栈的过程非常简单，因为栈是后进先出的，我们可以很方便的在数组的末尾插入和删除。所以我们选择末尾作为栈顶。所以栈需要的基本元素是一个data[]数组和一个表示栈顶位置的top(int)。那么初始化函数代码为：privateTdata[];privateinttop;publicseqStack(){data=(T[])newObject[10];top=-1;}publicseqStack(intmaxsize){data=(T[])newObject[maxsize];top=-1;}push是入栈的核心操作之一push()：入栈操作。如果top<数组长度-1。入栈，top++;a[top]=value;iftop==arraylength-1;堆栈已满。pop弹出并返回第一位。如果top>=0，则栈不为空，可以出栈。返回数据[顶部--]；如下图，原栈为1,2,3,4,5,6（栈顶），执行pop操作，top变为3的位置，返回4；peek操作等其他操作返回栈顶，不弹出。所以只要满足要求就返回data[top]即可。数组实现：包队栈；publicclassseqStack{privateTdata[];privateinttop;publicseqStack(){data=(T[])newObject[10];top=-1;}publicseqStack(intmaxsize){data=(T[])newObject[maxsize];top=-1;}booleanisEmpty(){returntop==-1;}intlength(){returntop+1;}booleanpush(Tvalue)throwsException//入栈{if(top+1>data.length-1){thrownewException("栈满");}else{data[++top]=value;returntrue;}}Tpeek()throwsException//返回栈顶元素，不移除{if(!isEmpty()){returndata[top];}else{thrownewException("堆栈为空");}}Tpop()throwsException{if(isEmpty()){thrownewException("堆栈为空");}else{returndata[top--];}}publicStringtoString(){if(top==-1){return"";}else{Stringva="";for(inti=top;i>=0;i--){va+=data[i]+"";}returnva;}}}链表可以用数组实现，当然链表也可以实现。对于栈的设计，大致可以分为两种思路：像数组一样在末尾插入和删除。大家都知道链表的查询效率低，向尾查询的效率很低。即使使用尾指针，也能解决尾插入的效率问题，但无法解决删除效率问题（删除需要找到前驱节点），需要双向链表。之前虽然详细介绍了双向链表，但是太复杂了！所以我们使用带前导节点的单链表在头部进行插入和删除，将头部视为栈顶。一个节点就够了，可以完美满足栈的需求。结构设计与链表非常相似。长话短说，不说了，直接写代码看懂就知道了。链表节点：staticclassnode{Tdata;nodenext;publicnode(){}publicnode(Tvalue){this.data=value;}}基本结构：publicclasslisStack{intlength;nodehead;//headNodepubliclisStack(){head=newnode<>();length=0;}//其他方法}推入插入和单链表头插入一致。不太了解的可以看上面写的线性表，具体讲解过程。与数组形成的栈有区别。链实现的栈理论上没有大小限制（不突破内存系统的限制），不需要考虑是否越界，而数组需要考虑容量问题。如果一个节点team入栈：一个空链表入栈head.next=team;一个非空链表被压入栈中team.next=head.next;head.next=team;pop弹窗与删除单链表表头一致。不明白的请先看作者对线性表的介绍。和数组一样，也需要判断栈是否为空。如果节点队出栈：head指向队尾的司机节点。其他操作，比如peek操作，返回栈顶而不弹出。所以只需要在head.next.data为空的时候返回，满足题意即可。至于长度，可以遍历链表返回长度，也可以动态设置（本文采取的）跟随栈长度的变化。链表实现：包队栈；publicclasslisStack{staticclassnode{Tdata;nodenext;publicnode(){}publicnode(Tvalue){this.data=value;}}intlength;nodehead;//头节点publiclisStack(){head=newnode<>();length=0;}booleanisEmpty(){returnhead.next==null;}intlength(){returnlength;}publicvoidpush(Tvalue){//nearstacknodeteam=newnode(值);if(length==0){head.next=team;}else{team.next=head.next;head.next=team;}length++;}publicTpeek()throwsException{if(length==0){thrownewException("链表为空");}else{//删除return(T)head.next.data;}}publicTpop()throwsException{//popif(length==0){thrownewException("The链表为空");}else{//删除Tvalue=(T)head.next.data;head.next=head.next.next;//va.nextlength--;returnvalue;}}publicStringtoString(){if(length==0){return"";}else{Stringva="";nodeteam=head.next;while(team!=null){va+=team.data+"";team=team.next;}returnva;}}}栈可以这样玩既然上面详细解释了设计栈，这里有两个很经典很经典的栈例子（很频繁，容易忘记，也很重要，常见问题不会被释放）韭菜20有效括号：标题：给定一个只包含'(',')','{','}','[',']'的字符串，判断该字符串是否有效。:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。请注意，空字符串被视为有效字符串。例子：输入："()[]{}"输出：true例子：输入："([)]"输出：false分析：括号的问题是一个经典的栈问题，必须想到用栈来处理用它。判断一个字符串是否满足有效字符串，就是看它能不能成对。从单对括号来看，((,))不满足，只能满足()，即一左一右。从多个括号对，{[(string也可以接受任意无穷大的(,[,{括号。但是如果左括号只能接受)括号(变成{[)。从上面可以看成是一个思路相消。比如(({[()()]}))在遍历一个字符串时可以这样处理：(({[(next)消失在(({[(({[(next)消失在(({[(({[next]被淘汰成(({(({next})被淘汰成(((((next)被淘汰成((next)被淘汰成this，满足每个操作的意思总判断剩余有效括号的顶括号是否可以从遍历中剔除，这个过程是用栈来判断是入栈还是出栈，最后如果栈为空，说明满足,否则不满足。当然具体的括号必须对应。具体实现代码为：publicbooleanisValid(Strings){Stackstack=newStack();for(inti=0;i=0&&a[index]=='[')index--;else{returnfalse;}}elseif(te=='}'){if(index>=0&&a[index]=='{')index--;else{returnfalse;}}elseif(te==')'){if(index>=0&&a[index]=='(')index--;else{returnfalse;}}elsea[++index]=te;}returnindex==-1;}里托32最长有效括号（难）题目描述：给定一个只包含'('和')'的字符串，求包含有效括号的最长子串的长度示例：输入："(()"输出：2解释：最长的有效括号子串是"()"例子：输入：")()())"输出：4解释：最长的有效括号子串是"()()"方案1这种暴力题的核心思路就是利用栈模拟。这道题比较简单一点，因为只有两种括号（and），而且使用暴力的时候，可以每次循环遍历，找到最长的有效括号。匹配到括号时，可以直接终止的情况是）匹配不上的右括号太多。比如())(到第三个不能连到前面。如果来了(只是期望后面能来)，一个)可以和一个(，在栈中消去一个(。的当然，在具体实现上，我们使用数组来模拟栈，实现代码为：publicintlongestValidParentheses(Strings){charstr[]=s.toCharArray();//字符数组intmax=0;for(inti=0;i=str.length-i)break;for(intj=i;jmax)){max=j-i+1;}}}returnmax;}??这个复杂度太高了，看怎么用栈优化方案2栈优化怎么把这道题的时间复杂度从O(n2)优化到O(n)?很简单，我们要注意他的过程，我们先看几种可能的最大情况。())()(()())到后面的部分（空格分隔）()()((()到前面的部分(((((()()()()到backpartforsuch一旦你得到它，你会发现不同的括号之间存在一些差异：(:一旦左括号出现，他期望a)匹配，但它后面可能有)还有许多其他括号对):右扩展标记有两种情况：一种是无法继续超出左括号前面。例如第三个括号()()的出现已经使整个字符串不可能继续下去，最大值要么在左边，要么在右边。你可以理解为一个清零初始机制。另一种情况）是目标栈中有（可以匹配到）。匹配后,必须叠加在消去后的层数上,判断是否为最大值.(后面会解释)在te具体实现思路rms，就是用一个int数组来标记当前层数（栈深度），用正确的括号个数。从左到右模拟一个栈行为，遇到）太多（当前栈中不存在（用于匹配））会清空数据重新开始。这将持续到最后。你可以把它看成一个台阶，当你遇到（就是上台阶清除新的台阶，遇到它），你会进入下一步，并在台阶上掉落后添加金额。具体可以看下图的模拟过程：()(()()(()))仔细看这张图，具体实现代码为：publicstaticintlongestValidParentheses(Strings){intmax=0;intvalue[]=newint[s.length()+1];intindex=0;for(inti=0;imax)//更新max=value[index];}}}returnmax;}也可以用栈实现，但效率比数组略低：publicintlongestValidParentheses(Strings){intmaxans=0;Stackstack=newStack<>();stack.push(-1);for(inti=0;i
