2025年新版堆栈队列面试题及答案

2025年新版堆栈队列面试题及答案1.如何用数组实现一个线程安全的栈？要求push、pop操作均为O(1)时间复杂度，需处理并发冲突。解答：线程安全的栈需通过锁或无锁机制保证操作原子性。基于数组实现时，可定义容量上限，维护top指针（初始-1）。push时检查top+1是否越界，若未越界则将元素放入top+1位置并原子递增top；pop时检查top是否≥0，若有效则原子递减top并返回原top位置元素。Java中可通过ReentrantLock或AtomicInteger配合CAS实现无锁操作。示例伪代码：classThreadSafeStack<T>{privatefinalT[]elements;privatefinalAtomicIntegertop=newAtomicInteger(-1);privatefinalintcapacity;publicThreadSafeStack(intcapacity){this.capacity=capacity;this.elements=(T[])newObject[capacity];}publicbooleanpush(Titem){intcurrentTop;do{currentTop=top.get();if(currentTop+1>=capacity)returnfalse;//栈满}while(!pareAndSet(currentTop,currentTop+1));elements[currentTop+1]=item;returntrue;}publicTpop(){intcurrentTop;do{currentTop=top.get();if(currentTop<0)returnnull;//栈空}while(!pareAndSet(currentTop,currentTop1));returnelements[currentTop];}}复杂度：push/pop的CAS操作在无竞争时为O(1)，高并发下可能因重试次数增加导致时间复杂度上升，但平均仍接近O(1)。空间复杂度O(n)（n为容量）。2.设计一个双端队列（Deque），要求用双向链表实现，支持从头部或尾部插入/删除元素，且需处理空队列边界条件。解答：双向链表每个节点包含prev、next指针和数据域。维护head（头节点）和tail（尾节点）指针，初始时head=tail=null。插入头部时，若队列为空则head=tail=新节点；否则新节点的next指向原head，原head的prev指向新节点，更新head为新节点。删除尾部时，若队列仅一个节点则head=tail=null；否则取tail的prev节点，将其next置null，更新tail为prev节点。关键操作代码（Python）：classNode:def__init__(self,val):self.val=valself.prev=Noneself.next=NoneclassDeque:def__init__(self):self.head=Noneself.tail=NonedefaddFront(self,val):new_node=Node(val)ifnotself.head:self.head=self.tail=new_nodeelse:new_node.next=self.headself.head.prev=new_nodeself.head=new_nodedefaddRear(self,val):new_node=Node(val)ifnotself.tail:self.head=self.tail=new_nodeelse:new_node.prev=self.tailself.tail.next=new_nodeself.tail=new_nodedefremoveFront(self):ifnotself.head:returnNoneval=self.head.valifself.head==self.tail:self.head=self.tail=Noneelse:new_head=self.head.nextnew_head.prev=Noneself.head=new_headreturnvaldefremoveRear(self):ifnotself.tail:returnNoneval=self.tail.valifself.head==self.tail:self.head=self.tail=Noneelse:new_tail=self.tail.prevnew_tail.next=Noneself.tail=new_tailreturnval边界处理：插入时判断队列是否为空，删除时检查头尾是否相同（队列仅一个元素）。所有操作时间复杂度O(1)，空间复杂度O(n)（n为元素个数）。3.给定一个整数数组，要求用单调队列实现滑动窗口最大值问题。窗口大小为k，数组长度为n（n≥k≥1），需输出每个窗口的最大值数组。解答：单调队列维护窗口内可能成为最大值的元素索引，队列头部为当前窗口最大值索引。遍历数组时，若队列头部索引≤i-k（超出窗口左边界）则弹出；若当前元素≥队列尾部对应元素，则弹出尾部（因其不可能成为后续窗口最大值），直到队列为空或尾部元素更大，将当前索引加入队列；当i≥k-1时，队列头部对应元素即为当前窗口最大值。示例代码（Java）：publicint[]maxSlidingWindow(int[]nums,intk){Deque<Integer>deque=newArrayDeque<>();int[]result=newint[nums.lengthk+1];for(inti=0;i<nums.length;i++){//移除超出窗口的头部元素while(!deque.isEmpty()&&deque.peekFirst()<=ik){deque.pollFirst();}//移除尾部小于当前元素的索引while(!deque.isEmpty()&&nums[deque.peekLast()]<=nums[i]){deque.pollLast();}deque.offerLast(i);//当窗口形成时记录最大值if(i>=k1){result[ik+1]=nums[deque.peekFirst()];}}returnresult;}复杂度：每个元素入队和出队各一次，时间复杂度O(n)；空间复杂度O(k)（队列最多存储k个元素）。4.实现一个支持O(1)时间复杂度获取最小值的栈（MinStack）。要求push、pop、top、getMin操作均为O(1)。解答：使用两个栈，主栈存储数据，辅助栈存储当前主栈对应位置的最小值。push时，若辅助栈为空或新元素≤辅助栈顶，则将新元素压入辅助栈；否则重复压入辅助栈顶元素。pop时同步弹出主栈和辅助栈的栈顶元素。getMin直接返回辅助栈顶。优化方案可仅在辅助栈记录最小值变化点，减少空间占用。示例代码（C++）：classMinStack{private:stack<int>dataStack;stack<int>minStack;public:voidpush(intval){dataStack.push(val);if(minStack.empty()||val<=minStack.top()){minStack.push(val);}else{minStack.push(minStack.top());//优化后可省略此步，改为记录差值}}voidpop(){if(!dataStack.empty()){dataStack.pop();minStack.pop();}}inttop(){returndataStack.top();}intgetMin(){returnminStack.top();}};优化版（仅存储最小值变化点）：辅助栈存储最小值及出现次数。push时若新值小于当前最小值，则压入新值和计数1；等于则计数+1；大于则不操作。pop时若主栈顶等于当前最小值且计数为1，则弹出辅助栈顶；否则计数-1。此方法空间复杂度平均更低。5.用两个队列实现一个栈，要求pop和top操作的均摊时间复杂度为O(1)。解答：维护两个队列q1（主队列）和q2（辅助队列）。push时直接将元素加入q1。pop时，将q1中除最后一个元素外的所有元素依次移到q2，取出q1的最后一个元素作为弹出值，然后将q2的元素移回q1（或交换队列角色避免频繁移动）。优化方法是每次pop时仅保留最后一个元素，其余移到辅助队列，下次push时直接加入当前非空队列。示例代码（Python）：classMyStack:def__init__(self):self.q1=deque()self.q2=deque()defpush(self,x:int)->None:始终将元素加入非空队列，初始时q1为空则加入q1ifself.q1:self.q1.append(x)else:self.q2.append(x)defpop(self)->int:确定当前非空队列main_q=self.q1ifself.q1elseself.q2aux_q=self.q2ifself.q1elseself.q1保留最后一个元素，其余移到辅助队列whilelen(main_q)>1:aux_q.append(main_q.popleft())val=main_q.popleft()returnvaldeftop(self)->int:类似pop，取出最后一个元素但不删除main_q=self.q1ifself.q1elseself.q2aux_q=self.q2ifself.q1elseself.q1whilelen(main_q)>1:aux_q.append(main_q.popleft())val=main_q[0]假设deque支持索引访问aux_q.append(main_q.popleft())移回辅助队列以保持状态returnvaldefempty(self)->bool:returnnotself.q1andnotself.q2均摊分析：每次pop操作需要移动n-1个元素（n为当前栈大小），但每个元素最多被移动一次（从主队列到辅助队列再移回），因此均摊时间复杂度为O(1)。6.设计一个循环队列（CircularQueue），要求用数组实现，支持动态扩容。当队列满时，容量自动翻倍；当队列元素数小于容量1/4时，容量减半（最小容量为8）。解答：循环队列用数组存储，维护front（队头索引）、rear（队尾索引，指向下一个插入位置）、size（当前元素数）、capacity（数组容量）。队满条件为size==capacity，队空条件为size==0。扩容时创建新数组，将原队列元素按顺序复制到新数组，front=0，rear=size。缩容逻辑类似。关键操作代码（Java）：classCircularQueue<T>{privateT[]elements;privateintfront=0;privateintrear=0;privateintsize=0;privatestaticfinalintMIN_CAPACITY=8;publicCircularQueue(intinitialCapacity){elements=(T[])newObject[Math.max(initialCapacity,MIN_CAPACITY)];}publicbooleanenqueue(Titem){if(size==elements.length){resize(elements.length2);//扩容}elements[rear]=item;rear=(rear+1)%elements.length;size++;returntrue;}publicTdequeue(){if(size==0)returnnull;Tval=elements[front];elements[front]=null;//帮助GCfront=(front+1)%elements.length;size--;//缩容检查：元素数小于容量1/4且容量大于最小容量if(size>0&&size<elements.length/4&&elements.length>MIN_CAPACITY){resize(elements.length/2);}returnval;}privatevoidresize(intnewCapacity){T[]newElements=(T[])newObject[newCapacity];for(inti=0;i<size;i++){newElements[i]=elements[(front+i)%elements.length];}elements=newElements;front=0;rear=size;}publicTpeek(){returnsize==0?null:elements[front];}publicbooleanisEmpty(){returnsize==0;}}扩容缩容均摊时间复杂度：每次扩容/缩容需要O(n)时间，但由于容量变化是指数级的，每个元素被复制的次数为O(logn)，均摊后每个操作的时间复杂度仍为O(1)。7.给定一个字符串，判断其是否为有效的括号序列。要求支持三种括号：()、[]、{}，且允许嵌套（如"([{}])"有效），但不允许交叉（如"([)]"无效）。需用栈实现。解答：遍历字符串，遇到左括号压栈；遇到右括号时，若栈空或栈顶左括号不匹配则返回false，否则弹出栈顶。遍历结束后栈必须为空。代码（JavaScript）：functionisValid(s){conststack=[];constmap={')':'(',']':'[','}':'{'};for(constcharofs){if(Object.values(map).includes(char)){stack.push(char);}else{if(stack.length===0||stack.pop()!==map[char]){returnfalse;}}}returnstack.length===0;}扩展问题：若字符串包含其他字符（如字母、数字），需忽略非括号字符。修改遍历逻辑，仅处理括号字符即可。8.实现一个队列，支持在O(1)时间复杂度内获取最大值。要求push、pop、getMax操作均为O(1)均摊时间。解答：使用双端队列维护可能的最大值候选。主队列存储所有元素，辅助双端队列存储递减序列（队头为当前最大值）。push时，将辅助队列尾部所有小于当前元素的节点弹出，然后加入当前元素；pop时，若主队列头部等于辅助队列头部，则弹出辅助队列头部。示例代码（Go）：typeMaxQueuestruct{queue[]intmaxDeque[]int}funcConstructor()MaxQueue{returnMaxQueue{}}func(thisMaxQueue)Push(xint){this.queue=append(this.queue,x)//维护maxDeque的递减性forlen(this.maxDeque)>0&&this.maxDeque[len(this.maxDeque)-1]<x{this.maxDeque=this.maxDeque[:len(this.maxDeque)-1]}this.maxDeque=append(this.maxDeque,x)}func(thisMaxQueue)Pop()int{iflen(this.queue)==0{return-1}front:=this.queue[0]this.queue=this.queue[1:]iffront==this.maxDeque[0]{this.maxDeque=this.maxDeque[1:]}returnfront}func(thisMaxQueue)GetMax()int{iflen(this.maxDeque)==0{return-1}returnthis.maxDeque[0]}复杂度：每个元素最多入队和出队辅助队列一次，均摊时间复杂度O(1)；空间复杂度O(n)。9.用栈模拟递归过程，实现二叉树的后序遍历。要求不使用递归，仅用显式栈结构。解答：后序遍历顺序为左-右-根，可通过标记法实现。栈中存储节点及访问标记（是否已处理）。首次访问节点时标记为未处理，压入栈；弹出时若标记为未处理，则重新压入（标记为已处理），然后压入右子节点（未处理）、左子节点（未处理）。若标记为已处理，则访问该节点。代码（Python）：classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpostorderTraversal(root):ifnotroot:return[]stack=[(root,False)]result=[]whilestack:node,visited=stack.pop()ifvisited:result.append(node.val)else:stack.append((node,True))ifnode.right:stack.append((node.right,False))ifnode.left:stack.append((node.left,False))returnresult关键点：通过标记区分节点是首次访问（需压入左右子节点）还是二次访问（需记录值）。时间复杂度O(n)，空间复杂度O(n)（栈最大深度为树高）。10.设计一个缓存系统，要求支持最近最少使用（LRU）策略。需用哈希表和双向链表实现，保证put和get操作的时间复杂度为O(1)。解答：双向链表维护访问顺序（最近访问的节点放在头部），哈希表存储键到链表节点的映射。get时若键存在，将节点移到头部；put时若键存在则更新值并移到头部，若不存在则创建新节点（若容量满则删除尾部节点并从哈希表移除），然后将新节点加入头部并更新哈希表。关键代码（Java）：classLRUCache{classNode{intkey,val;Nodeprev,next;Node(intk,intv){key=k;val=v;}}privateMap<Integer,Node>map=newHashMap<>();privateNodehead=newNode(0,0);//哨兵头privateNodetail=newNode(0,0);/