栈与队列经典算法题精讲（一）：循环队列·有效括号·面试高频原题全解析

个人主页黎雁作者简介C/C/JAVA后端开发学习者❄️个人专栏C语言、数据结构C语言、EasyX、JAVA、数据结构与算法JAVA、游戏、规划、程序人生✨ 从来绝巘须孤往万里同尘即玉京文章目录栈与队列经典算法题精讲文章摘要前置知识回顾1. 设计循环队列(1) 题目描述(2) 实现思路(3) 代码实现(4) 关键点说明2. 有效的括号(1) 题目描述(2) 思路一 栈匹配法(3) 代码实现(4) 思路二 暴力消除法(5) 代码实现(6) 两种思路对比核心考点总结设计循环队列有效括号写在最后栈与队列经典算法题精讲循环队列·有效括号·面试高频原题全解析文章摘要阅读时长18 分钟适合人群算法入门与刷题新手 重点掌握循环队列设计、有效括号解法面试备战同学 重点LeetCode 高频题思路、代码模板、最优写法数据结构进阶者 重点循环队列原理、栈的实际应用场景复习总结同学 重点代码结构、边界处理、时间复杂度分析本文内容全覆盖LeetCode 622 设计循环队列、LeetCode 20 有效括号两道高频面试题从原理讲解、思路分析、代码实现到细节优化一次性吃透栈与队列最经典算法题型。前置知识回顾学习本文前你需要掌握队列先进先出特性栈后进先出特性数组与链表基本操作Java 集合基础使用本文是栈与队列在算法题中的直接落地难度适中面试出现频率极高。1. 设计循环队列(1) 题目描述设计实现一个循环队列支持以下操作MyCircularQueue(k) 构造器设置队列长度为 kFront() 获取队首元素Rear() 获取队尾元素enQueue(value) 向队列插入元素deQueue() 从队列删除元素isEmpty() 判断队列是否为空isFull() 判断队列是否为满循环队列是一种线性数据结构遵循先进先出并且队尾连接在队首之后形成循环可以充分利用数组空间。(2) 实现思路使用数组实现循环队列定义两个指针front 指向队头rear 指向队尾的下一个位置为了区分空与满我们浪费一个数组空间判空条件front rear判满条件(rear 1) % 数组长度 front所有指针移动都使用取模运算实现循环(3) 代码实现classMyCircularQueue{publicintfront;publicintrear;publicint[]elem;publicMyCircularQueue(intk){elemnewint[k1];}publicbooleanenQueue(intvalue){if(isFull()){returnfalse;}elem[rear]value;rear(rear1)%elem.length;returntrue;}publicbooleandeQueue(){if(isEmpty()){returnfalse;}front(front1)%elem.length;returntrue;}publicintFront(){if(isEmpty()){return-1;}returnelem[front];}publicintRear(){if(isEmpty()){return-1;}intindex(rear0)?elem.length-1:rear-1;returnelem[index];}publicbooleanisEmpty(){returnrearfront;}publicbooleanisFull(){return(rear1)%elem.lengthfront;}}(4) 关键点说明数组长度为 k1浪费一个位置用于区分空与满rear 指向队尾元素的下一个位置方便插入获取队尾元素时需要特殊处理 rear0 的情况所有指针移动都使用取模实现循环避免越界时间复杂度 O(1)所有操作都是常数时间2. 有效的括号(1) 题目描述给定一个只包含()、{}、[]的字符串 s判断字符串是否有效。有效字符串满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合每个右括号都有对应的左括号(2) 思路一 栈匹配法这是最标准、最推荐、面试最优解法。核心思路遍历字符串遇到左括号直接入栈遇到右括号时如果栈为空直接返回 false取出栈顶元素判断是否匹配匹配则弹出栈顶不匹配返回 false遍历结束后栈必须为空才是有效括号(3) 代码实现classSolution{publicbooleanisValid(Strings){StackCharacterstacknewStack();for(inti0;is.length();i){charchs.charAt(i);if(ch(||ch{||ch[){stack.push(ch);}else{if(stack.isEmpty()){returnfalse;}charch2stack.peek();if((ch)ch2()||(ch}ch2{)||(ch]ch2[)){stack.pop();}else{returnfalse;}}}returnstack.isEmpty();}}(4) 思路二 暴力消除法思路非常简单直观适合理解但效率略低。核心思路不断消除字符串中最内层的合法括号对重复消除()、[]、{}直到无法消除为止最终字符串为空则有效否则无效(5) 代码实现classSolution{publicbooleanisValid(Strings){while(s.contains(())||s.contains([])||s.contains({})){ss.replace((),);ss.replace([],);ss.replace({},);}returns.isEmpty();}}(6) 两种思路对比栈匹配法时间复杂度 O(n)空间复杂度 O(n)面试推荐写法逻辑严谨暴力消除法代码极简时间复杂度较高适合理解思路不推荐面试优先写核心考点总结设计循环队列循环队列依靠取模实现循环结构判空 front rear判满 (rear1) % len front数组实现浪费一个空间区分空满高频面试手写题有效括号栈的最经典应用场景左括号入栈右括号匹配栈顶最终栈必须为空面试必须熟练掌握写在最后循环队列与有效括号是栈与队列中最经典、最高频的两道算法题几乎是数据结构面试必考题。循环队列考察你对队列、数组、指针、循环结构的理解。有效括号考察你对栈后进先出特性的实际运用。掌握这两道题代表你真正理解了栈与队列的核心思想能够在面试中轻松应对同类题型。后续我们将继续带来栈与队列的更多经典算法题最小栈、逆波兰表达式求值、滑动窗口最大值、用栈实现队列、用队列实现栈等高频面试题型。