文章目录1. 括号匹配LC20题目描述解题思路代码示例2. 逆波兰表达式LC150)题目描述解题思路代码示例3. 出栈入栈次序匹配JZ31题目描述解题思路代码示例4. 最小栈问题LC155题目描述解题思路代码示例5. 设计循环队列LC622题目描述解题思路代码示例6. 用队列实现栈LC225题目描述解题思路代码示例7. 用栈实现队列LC232题目描述解题思路代码示例1. 括号匹配LC20括号匹配题目描述解题思路字符串大致可以分为四种情况括号匹配正确左右括号不匹配匹配但左括号多匹配但右括号多这种结构使用栈先进后出更合适先定义一个栈遍历字符串只要字符是[{(其中一个则入栈。不是这种情况则先检查栈是否为空如果为空则符合情况4返回false如果栈不为空则获取栈顶元素判断与当前字符是否匹配匹配则删除不匹配则返回false遍历结束后再检查栈是否为空如果不为空则复合第3种情况返回false以上情况全部排除即在括号匹配字符串遍历完成且栈为空则返回true代码示例publicbooleanisValid(Strings){StackCharacterstacknewStack();for(inti0;is.length();i){charchs.charAt(i);if(ch{||ch[||ch(){stack.push(ch);}else{if(stack.isEmpty())returnfalse;charch1stack.peek();if(ch1(ch)||ch1[ch]||ch1{ch})stack.pop();elsereturnfalse;}}if(!stack.isEmpty())returnfalse;returntrue;}2. 逆波兰表达式LC150)逆波兰表达式题目描述解题思路先判断当前字符是数字还是操作符如果是数字则用Integer.parseInt转化为整型压栈。如果是操作符则拿出栈后两个元素需要注意两个操作数的顺序。计算后再压栈返回栈中最后的元素代码示例booleanisOperator(Strings){return(s.equals()||s.equals(-)||s.equals(*)||s.equals(/));}publicintevalRPN(String[]tokens){StackIntegerstacknewStack();for(Stringstr:tokens){if(!isOperator(str)){intxInteger.parseInt(str);stack.push(x);}else{intval1stack.pop();intval2stack.pop();switch(str){case:stack.push(val2val1);break;case-:stack.push(val2-val1);break;case*:stack.push(val2*val1);break;case/:stack.push(val2/val1);break;}}}returnstack.pop();}3. 出栈入栈次序匹配JZ31出栈入栈次序匹配题目描述解题思路创建栈来存放pushA中的元素i指针遍历pushV中的元素j指针遍历popV中元素每存放一个元素将栈顶元素与popV[j]对比相等则出栈直到栈空或不相等最后如果栈空则返回true不空返回false代码示例publicbooleanIsPopOrder(int[]pushV,int[]popV){if(pushV.length0)returnfalse;intj0;StackIntegerstacknewStack();for(inti0;ipushV.length;i){stack.push(pushV[i]);while(!stack.isEmpty()stack.peek()popV[j]){stack.pop();j;}}returnstack.isEmpty();}4. 最小栈问题LC155最小栈问题题目描述解题思路创建一个栈stack用于存放所有元素一个栈minStack存放最小元素void push(int val)将元素val推入stack。如果minStack为空或者val栈顶元素则压栈。需要注意的是相等也需要压入栈因为后续有弹出的操作所以stack和minStack中最小元素必须相等void pop()删除堆栈顶部的元素。如果stack和minStack栈顶元素相等则minStack也删除int getMin()获取minStack栈顶元素代码示例classMinStack{StackIntegerstacknewStack();StackIntegerminStacknewStack();publicMinStack(){}publicvoidpush(intval){stack.push(val);if(minStack.isEmpty()||minStack.peek()val){minStack.push(val);}}publicvoidpop(){intvalstack.pop();if(minStack.peek()val)minStack.pop();}publicinttop(){returnstack.peek();}publicintgetMin(){returnminStack.peek();}}5. 设计循环队列LC622设计循环队列题目描述解题思路底层是数组elemrear用于维护队尾front用于维护队首size记录已存放元素的个数capacity记录数组容量。数组的头和尾要特殊处理enQueue()入队考虑rear是否在数组最后如果是则置为0不是则rear1deQueue()出队与入队相同考虑front是否在数组最后如果是则置为0不是则rear1Rear()返回队尾元素考虑rear是否为0是则访问最后一个下标也就是capacity-1不是则访问rear-1代码示例classMyCircularQueue{int[]elem;intrear;intfront;intsize;intcapacity;publicMyCircularQueue(intk){this.elemnewint[k];this.capacityk;}publicbooleanenQueue(intvalue){if(isFull())returnfalse;elem[rear]value;rear(rearcapacity-1)?0:rear1;size;returntrue;}publicbooleandeQueue(){if(isEmpty())returnfalse;front(frontcapacity-1)?0:front1;size--;returntrue;}publicintFront(){if(isEmpty())return-1;returnelem[front];}publicintRear(){if(isEmpty())return-1;intretrear0?capacity-1:rear-1;returnelem[ret];}publicbooleanisEmpty(){returnsize0;}publicbooleanisFull(){returnsizecapacity;}}6. 用队列实现栈LC225用队列实现栈题目描述解题思路队列只能遵循先进先出要实现栈就要用两个队列q1,q2搭配。void push()找到空的队列依次入队。int pop()先把队尾之前的元素依次入队到另一个空队列最后把队尾元素弹出并返回int top()与pop()方法类似所有元素依次入队到另一个空队列但是需要一个变量(val)记录出队的元素最后返回valboolean empty()如果q1,q1都为空则栈为空代码示例importjava.util.LinkedList;importjava.util.Queue;publicclassMyStackUseQueue{QueueIntegerq1;QueueIntegerq2;publicMyStackUseQueue(){q1newLinkedList();q2newLinkedList();}publicvoidpush(intx){if(!q1.isEmpty())q1.offer(x);elseif(!q2.isEmpty())q2.offer(x);elseq1.offer(x);}publicintpop(){if(empty())return-1;if(q2.isEmpty()){intsizeq1.size();for(inti0;isize-1;i)q2.offer(q1.poll());intretq1.poll();returnret;}else{intsizeq2.size();for(inti0;isize-1;i)q1.offer(q2.poll());intretq2.poll();returnret;}}publicinttop(){if(empty())return-1;if(q2.isEmpty()){intval0;intsizeq1.size();for(inti0;isize;i){valq1.poll();q2.offer(val);}returnval;}else{intval0;intsizeq2.size();for(inti0;isize;i){valq2.poll();q1.offer(val);}returnval;}}publicbooleanempty(){returnq1.isEmpty()q2.isEmpty();}}7. 用栈实现队列LC232用栈实现队列题目描述解题思路与上一题类似用两个栈来实现s1,s2队列。指定s1用于入队s2用于出队void push(int x)将元素 x 压栈到s1中int pop()返回s2栈顶元素如果s2为空则先将s1的所有元素依次压栈到s2中再返回s2栈顶元素int peek()与pop()类似最后将s2栈顶元素弹出并返回boolean empty()如果s1s2都为空则返回true代码示例importjava.util.Stack;publicclassMyQueueUseStack{StackIntegers1;StackIntegers2;publicMyQueueUseStack(){s1newStack();s2newStack();}publicvoidpush(intx){s1.push(x);}publicintpop(){if(empty())return-1;if(s2.isEmpty())while(!s1.isEmpty())s2.push(s1.pop());returns2.pop();}publicintpeek(){if(empty())return-1;if(s2.isEmpty())while(!s1.isEmpty())s2.push(s1.pop());returns2.peek();}publicbooleanempty(){returns1.isEmpty()s2.isEmpty();}}