算法面试——栈与队列：单调栈、双栈实现队列

栈和队列是面试高频基础结构重点考察单调栈和用栈实现队列这两类变形题。这篇把经典题全部整理出来代码直接可跑。一、用两个栈实现队列队列先进先出栈后进先出。用两个栈入队栈 出队栈。classMyQueue{DequeIntegerinStacknewArrayDeque();DequeIntegeroutStacknewArrayDeque();publicvoidpush(intx){inStack.push(x);}publicintpop(){if(outStack.isEmpty()){// 把入队栈全部倒入出队栈顺序就反过来了while(!inStack.isEmpty()){outStack.push(inStack.pop());}}returnoutStack.pop();}publicintpeek(){if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}returnoutStack.peek();}publicbooleanempty(){returninStack.isEmpty()outStack.isEmpty();}}摊还复杂度 O(1)每个元素最多被倒两次入栈出栈。二、有效的括号publicbooleanisValid(Strings){DequeCharacterstacknewArrayDeque();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();}三、单调栈下一个更大元素核心思想栈内元素单调递减遇到更大元素就出栈结算。// LeetCode 739 每日温度返回每个元素后面第一个更大元素的距离publicint[]dailyTemperatures(int[]temperatures){intntemperatures.length;int[]resultnewint[n];DequeIntegerstacknewArrayDeque();// 存下标for(inti0;in;i){// 当前温度比栈顶高 → 栈顶出栈它的答案就是 iwhile(!stack.isEmpty()temperatures[i]temperatures[stack.peek()]){intidxstack.pop();result[idx]i-idx;}stack.push(i);}returnresult;// 没出栈的默认0说明后面没有更大温度}单调栈模板总结找右边第一个更大 → 从左往右栈单调递减 找左边第一个更大 → 从右往左栈单调递减 找右边第一个更小 → 从左往右栈单调递增四、最小栈实现一个栈支持 O(1) 获取栈内最小值。classMinStack{DequeIntegerdatanewArrayDeque();DequeIntegerminnewArrayDeque();// 辅助栈同步维护最小值publicvoidpush(intval){data.push(val);// 辅助栈顶存当前最小值if(min.isEmpty()||valmin.peek()){min.push(val);}else{min.push(min.peek());}}publicvoidpop(){data.pop();min.pop();}publicinttop(){returndata.peek();}publicintgetMin(){returnmin.peek();}}总结栈和队列题目核心就两类括号匹配类直接模拟和单调栈类下一个更大/更小元素。单调栈记住口诀“栈内有序、出栈结算”几乎所有单调栈题都能套模板。时间复杂度 O(n) 单次遍历比暴力 O(n²) 高效得多。 觉得有用的话点赞 关注【张老师技术栈】吧