栈和队列虽然只是限制了操作位置的线性表但它们在计算机科学中的应用极广。这篇把 408 中最常考的栈和队列应用讲透。一、括号匹配括号匹配是栈最经典的应用之一编译器检查代码语法时就是用它。publicclassBracketMatcher{/** * 判断括号字符串是否合法 * 测试isValid(({[]})) → true * isValid(({[}])) → false */publicbooleanisValid(Strings){StackCharacterstacknewStack();for(charc:s.toCharArray()){if(c(||c[||c{){stack.push(c);}else{if(stack.isEmpty())returnfalse;chartopstack.pop();if(c)top!()returnfalse;if(c]top![)returnfalse;if(c}top!{)returnfalse;}}returnstack.isEmpty();}}原理遇到左括号入栈遇到右括号检查栈顶是否匹配。最终栈为空则合法。二、表达式求值1. 中缀、前缀、后缀中缀表达式人看的 A B × C 前缀表达式波兰式 A × B C 后缀表达式逆波兰式A B C × 计算机更适合处理后缀表达式因为不需要括号和优先级判断。2. 中缀转后缀publicclassInfixToPostfix{/** * 中缀表达式转后缀表达式 * 输入AB*C-(DE) * 输出[A, B, C, *, , D, E, , -] */publicListStringconvert(Stringinfix){// 运算符优先级MapCharacter,IntegerprecnewHashMap();prec.put(,1);prec.put(-,1);prec.put(*,2);prec.put(/,2);StackCharacteropsnewStack();ListStringoutputnewArrayList();for(inti0;iinfix.length();i){charcinfix.charAt(i);if(Character.isLetterOrDigit(c)){// 操作数直接输出output.add(String.valueOf(c));}elseif(c(){ops.push(c);}elseif(c)){// 弹出直到左括号while(!ops.isEmpty()ops.peek()!(){output.add(String.valueOf(ops.pop()));}ops.pop();// 丢弃左括号}else{// 运算符弹出优先级不低于当前的操作符while(!ops.isEmpty()ops.peek()!(prec.get(ops.peek())prec.get(c)){output.add(String.valueOf(ops.pop()));}ops.push(c);}}// 剩余操作符出栈while(!ops.isEmpty()){output.add(String.valueOf(ops.pop()));}returnoutput;}}3. 计算后缀表达式publicclassPostfixCalculator{/** * 计算后缀表达式的值 * 输入[2, 3, , 4, *] → (23)*4 20 */publicintevaluate(ListStringpostfix){StackIntegerstacknewStack();for(Stringtoken:postfix){if(token.matches(\\d)){stack.push(Integer.parseInt(token));}else{intbstack.pop();intastack.pop();switch(token){case:stack.push(ab);break;case-:stack.push(a-b);break;case*:stack.push(a*b);break;case/:stack.push(a/b);break;}}}returnstack.pop();}}整体流程中缀表达式 → 中缀转后缀 → 计算后缀表达式 → 结果 AB*C-(DE) → [A,B,C,*,,D,E,,-] → 计算三、循环队列1. 为什么需要循环队列普通顺序队列的问题 enqueue(A): front0, rear1 [A, , , , ] enqueue(B): front0, rear2 [A, B, , , ] dequeue(): front1, rear2 [ , B, , , ] ← 下标0浪费了 循环队列通过取模运算让数组空间可以复用2. 完整实现classCircularQueue{privateint[]data;privateintfront;// 队头指针privateintrear;// 队尾指针指向下一个插入位置privateintsize;// 当前元素个数privateintcapacity;publicCircularQueue(intk){datanewint[k];capacityk;front0;rear0;size0;}publicbooleanenQueue(intvalue){if(isFull())returnfalse;data[rear]value;rear(rear1)%capacity;size;returntrue;}publicbooleandeQueue(){if(isEmpty())returnfalse;front(front1)%capacity;size--;returntrue;}publicintFront(){if(isEmpty())return-1;returndata[front];}publicintRear(){if(isEmpty())return-1;// 返回 rear 前一个位置的元素intidx(rear-1capacity)%capacity;returndata[idx];}publicbooleanisEmpty(){returnsize0;}publicbooleanisFull(){returnsizecapacity;}}3. 判空判满的两种方式方式一size 字段推荐 isEmpty() → size 0 isFull() → size capacity 简单直观 方式二牺牲一个存储单元 isEmpty() → front rear isFull() → (rear 1) % capacity front 不占额外空间但浪费一个数组元素四、栈与队列的相互实现1. 两个栈实现队列classQueueByTwoStacks{privateStackIntegerinStack;// 入队栈privateStackIntegeroutStack;// 出队栈publicQueueByTwoStacks(){inStacknewStack();outStacknewStack();}publicvoidpush(intx){inStack.push(x);}publicintpop(){if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}returnoutStack.pop();}}2. 两个队列实现栈classStackByTwoQueues{privateQueueIntegerqueue1;privateQueueIntegerqueue2;publicStackByTwoQueues(){queue1newLinkedList();queue2newLinkedList();}publicvoidpush(intx){queue1.offer(x);}publicintpop(){// 除了队尾元素全部移到 queue2while(queue1.size()1){queue2.offer(queue1.poll());}intresultqueue1.poll();// 交换两个队列的引用QueueIntegertempqueue1;queue1queue2;queue2temp;returnresult;}}五、单调栈单调栈是栈的高级应用用于解决下一个更大元素类问题。/** * 下一个更大元素 * 输入[2, 1, 2, 4, 3] * 输出[4, 2, 4, -1, -1] * * 维护一个单调递减栈 */publicint[]nextGreaterElement(int[]nums){intnnums.length;int[]resultnewint[n];Arrays.fill(result,-1);StackIntegerstacknewStack();for(inti0;in;i){while(!stack.isEmpty()nums[i]nums[stack.peek()]){intidxstack.pop();result[idx]nums[i];}stack.push(i);}returnresult;}六、408 考研常见考题题1栈在括号匹配中的应用表达式{[()()]}([]) 判断过程 { → 入栈 [ → 入栈 ( → 入栈 ) → 弹出 ( → 匹配 ✓ ( → 入栈 ) → 弹出 ( → 匹配 ✓ ] → 弹出 [ → 匹配 ✓ } → 弹出 { → 匹配 ✓ ( → 入栈 [ → 入栈 ] → 弹出 [ → 匹配 ✓ ) → 弹出 ( → 匹配 ✓ 栈空 → 完全匹配题2循环队列的存储数组 A[0..m-1] 存放循环队列front5, rear2 队中元素个数 (rear - front m) % m (2-58)%8 5题3表达式求值中缀A B * (C - D) - E / F 后缀A B C D - * E F / - 计算后缀时用栈存操作数 遇到操作数入栈遇到操作符弹出两个计算后入栈七、总结栈的应用 括号匹配 → 左入右出最后判空 表达式求值 → 中缀转后缀再计算 函数调用 → JVM 虚拟机栈 队列的应用 循环队列 → 取模运算空间复用 任务调度 → 线程池任务队列 树的遍历 → 层序遍历BFS 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。