2025年新版堆棧隊列面試題及答案1.如何用數(shù)組實現(xiàn)一個線程安全的棧？要求push、pop操作均為O(1)時間復雜度，需處理并發(fā)沖突。解答：線程安全的棧需通過鎖或無鎖機制保證操作原子性?；跀?shù)組實現(xiàn)時，可定義容量上限，維護top指針（初始-1）。push時檢查top+1是否越界，若未越界則將元素放入top+1位置并原子遞增top；pop時檢查top是否≥0，若有效則原子遞減top并返回原top位置元素。Java中可通過ReentrantLock或AtomicInteger配合CAS實現(xiàn)無鎖操作。示例偽代碼：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)，高并發(fā)下可能因重試次數(shù)增加導致時間復雜度上升，但平均仍接近O(1)?？臻g復雜度O(n)（n為容量）。2.設計一個雙端隊列（Deque），要求用雙向鏈表實現(xiàn)，支持從頭部或尾部插入/刪除元素，且需處理空隊列邊界條件。解答：雙向鏈表每個節(jié)點包含prev、next指針和數(shù)據域。維護head（頭節(jié)點）和tail（尾節(jié)點）指針，初始時head=tail=null。插入頭部時，若隊列為空則head=tail=新節(jié)點；否則新節(jié)點的next指向原h(huán)ead，原h(huán)ead的prev指向新節(jié)點，更新head為新節(jié)點。刪除尾部時，若隊列僅一個節(jié)點則head=tail=null；否則取tail的prev節(jié)點，將其next置null，更新tail為prev節(jié)點。關鍵操作代碼（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為元素個數(shù)）。3.給定一個整數(shù)數(shù)組，要求用單調隊列實現(xiàn)滑動窗口最大值問題。窗口大小為k，數(shù)組長度為n（n≥k≥1），需輸出每個窗口的最大值數(shù)組。解答：單調隊列維護窗口內可能成為最大值的元素索引，隊列頭部為當前窗口最大值索引。遍歷數(shù)組時，若隊列頭部索引≤i-k（超出窗口左邊界）則彈出；若當前元素≥隊列尾部對應元素，則彈出尾部（因其不可能成為后續(xù)窗口最大值），直到隊列為空或尾部元素更大，將當前索引加入隊列；當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.實現(xiàn)一個支持O(1)時間復雜度獲取最小值的棧（MinStack）。要求push、pop、top、getMin操作均為O(1)。解答：使用兩個棧，主棧存儲數(shù)據，輔助棧存儲當前主棧對應位置的最小值。push時，若輔助棧為空或新元素≤輔助棧頂，則將新元素壓入輔助棧；否則重復壓入輔助棧頂元素。pop時同步彈出主棧和輔助棧的棧頂元素。getMin直接返回輔助棧頂。優(yōu)化方案可僅在輔助棧記錄最小值變化點，減少空間占用。示例代碼（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());//優(yōu)化后可省略此步，改為記錄差值}}voidpop(){if(!dataStack.empty()){dataStack.pop();minStack.pop();}}inttop(){returndataStack.top();}intgetMin(){returnminStack.top();}};優(yōu)化版（僅存儲最小值變化點）：輔助棧存儲最小值及出現(xiàn)次數(shù)。push時若新值小于當前最小值，則壓入新值和計數(shù)1；等于則計數(shù)+1；大于則不操作。pop時若主棧頂?shù)扔诋斍白钚≈登矣嫈?shù)為1，則彈出輔助棧頂；否則計數(shù)-1。此方法空間復雜度平均更低。5.用兩個隊列實現(xiàn)一個棧，要求pop和top操作的均攤時間復雜度為O(1)。解答：維護兩個隊列q1（主隊列）和q2（輔助隊列）。push時直接將元素加入q1。pop時，將q1中除最后一個元素外的所有元素依次移到q2，取出q1的最后一個元素作為彈出值，然后將q2的元素移回q1（或交換隊列角色避免頻繁移動）。優(yōu)化方法是每次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())移回輔助隊列以保持狀態(tài)returnvaldefempty(self)->bool:returnnotself.q1andnotself.q2均攤分析：每次pop操作需要移動n-1個元素（n為當前棧大?。?，但每個元素最多被移動一次（從主隊列到輔助隊列再移回），因此均攤時間復雜度為O(1)。6.設計一個循環(huán)隊列（CircularQueue），要求用數(shù)組實現(xiàn)，支持動態(tài)擴容。當隊列滿時，容量自動翻倍；當隊列元素數(shù)小于容量1/4時，容量減半（最小容量為8）。解答：循環(huán)隊列用數(shù)組存儲，維護front（隊頭索引）、rear（隊尾索引，指向下一個插入位置）、size（當前元素數(shù)）、capacity（數(shù)組容量）。隊滿條件為size==capacity，隊空條件為size==0。擴容時創(chuàng)建新數(shù)組，將原隊列元素按順序復制到新數(shù)組，front=0，rear=size?？s容邏輯類似。關鍵操作代碼（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--;//縮容檢查：元素數(shù)小于容量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)時間，但由于容量變化是指數(shù)級的，每個元素被復制的次數(shù)為O(logn)，均攤后每個操作的時間復雜度仍為O(1)。7.給定一個字符串，判斷其是否為有效的括號序列。要求支持三種括號：()、[]、{}，且允許嵌套（如"([{}])"有效），但不允許交叉（如"([)]"無效）。需用棧實現(xiàn)。解答：遍歷字符串，遇到左括號壓棧；遇到右括號時，若?？栈驐ｍ斪罄ㄌ柌黄ヅ鋭t返回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;}擴展問題：若字符串包含其他字符（如字母、數(shù)字），需忽略非括號字符。修改遍歷邏輯，僅處理括號字符即可。8.實現(xiàn)一個隊列，支持在O(1)時間復雜度內獲取最大值。要求push、pop、getMax操作均為O(1)均攤時間。解答：使用雙端隊列維護可能的最大值候選。主隊列存儲所有元素，輔助雙端隊列存儲遞減序列（隊頭為當前最大值）。push時，將輔助隊列尾部所有小于當前元素的節(jié)點彈出，然后加入當前元素；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.用棧模擬遞歸過程，實現(xiàn)二叉樹的后序遍歷。要求不使用遞歸，僅用顯式棧結構。解答：后序遍歷順序為左-右-根，可通過標記法實現(xiàn)。棧中存儲節(jié)點及訪問標記（是否已處理）。首次訪問節(jié)點時標記為未處理，壓入棧；彈出時若標記為未處理，則重新壓入（標記為已處理），然后壓入右子節(jié)點（未處理）、左子節(jié)點（未處理）。若標記為已處理，則訪問該節(jié)點。代碼（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關鍵點：通過標記區(qū)分節(jié)點是首次訪問（需壓入左右子節(jié)點）還是二次訪問（需記錄值）。時間復雜度O(n)，空間復雜度O(n)（棧最大深度為樹高）。10.設計一個緩存系統(tǒng)，要求支持最近最少使用（LRU）策略。需用哈希表和雙向鏈表實現(xiàn)，保證put和get操作的時間復雜度為O(1)。解答：雙向鏈表維護訪問順序（最近訪問的節(jié)點放在頭部），哈希表存儲鍵到鏈表節(jié)點的映射。get時若鍵存在，將節(jié)點移到頭部；put時若鍵存在則更新值并移到頭部，若不存在則創(chuàng)建新節(jié)點（若容量滿則刪除尾部節(jié)點并從哈希表移除），然后將新節(jié)點加入頭部并更新哈希表。關鍵代碼（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);/