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

🏠个人主页：黎雁
🎬作者简介：C/C++/JAVA后端开发学习者
❄️个人专栏：C语言、数据结构（C语言）、EasyX、JAVA、数据结构与算法（JAVA）、游戏、规划、程序人生
✨ 从来绝巘须孤往，万里同尘即玉京

栈与队列经典算法题精讲

循环队列·有效括号·面试高频原题全解析

文章摘要

阅读时长：18 分钟

适合人群

1. 算法入门与刷题新手 重点：掌握循环队列设计、有效括号解法
2. 面试备战同学 重点：LeetCode 高频题思路、代码模板、最优写法
3. 数据结构进阶者 重点：循环队列原理、栈的实际应用场景
4. 复习总结同学 重点：代码结构、边界处理、时间复杂度分析

本文内容
全覆盖LeetCode 622 设计循环队列、LeetCode 20 有效括号两道高频面试题，从原理讲解、思路分析、代码实现到细节优化，一次性吃透栈与队列最经典算法题型。

前置知识回顾

学习本文前你需要掌握

1. 队列先进先出特性
2. 栈后进先出特性
3. 数组与链表基本操作
4. Java 集合基础使用

本文是栈与队列在算法题中的直接落地，难度适中，面试出现频率极高。

1. 设计循环队列

(1) 题目描述

设计实现一个循环队列，支持以下操作：

• MyCircularQueue(k) 构造器，设置队列长度为 k
• Front() 获取队首元素
• Rear() 获取队尾元素
• enQueue(value) 向队列插入元素
• deQueue() 从队列删除元素
• isEmpty() 判断队列是否为空
• isFull() 判断队列是否为满

循环队列是一种线性数据结构，遵循先进先出，并且队尾连接在队首之后形成循环，可以充分利用数组空间。

(2) 实现思路

1. 使用数组实现循环队列
2. 定义两个指针：front 指向队头，rear 指向队尾的下一个位置
3. 为了区分空与满，我们浪费一个数组空间
4. 判空条件：front == rear
5. 判满条件：(rear + 1) % 数组长度 == front
6. 所有指针移动都使用取模运算实现循环

(3) 代码实现

classMyCircularQueue{publicintfront;publicintrear;publicint[]elem;publicMyCircularQueue(intk){elem=newint[k+1];}publicbooleanenQueue(intvalue){if(isFull()){returnfalse;}elem[rear]=value;rear=(rear+1)%elem.length;returntrue;}publicbooleandeQueue(){if(isEmpty()){returnfalse;}front=(front+1)%elem.length;returntrue;}publicintFront(){if(isEmpty()){return-1;}returnelem[front];}publicintRear(){if(isEmpty()){return-1;}intindex=(rear==0)?elem.length-1:rear-1;returnelem[index];}publicbooleanisEmpty(){returnrear==front;}publicbooleanisFull(){return(rear+1)%elem.length==front;}}

(4) 关键点说明

1. 数组长度为 k+1，浪费一个位置用于区分空与满
2. rear 指向队尾元素的下一个位置，方便插入
3. 获取队尾元素时需要特殊处理 rear=0 的情况
4. 所有指针移动都使用取模实现循环，避免越界
5. 时间复杂度 O(1)，所有操作都是常数时间

2. 有效的括号

(1) 题目描述

给定一个只包含()、{}、[]的字符串 s，判断字符串是否有效。

有效字符串满足：

1. 左括号必须用相同类型的右括号闭合
2. 左括号必须以正确的顺序闭合
3. 每个右括号都有对应的左括号

(2) 思路一 栈匹配法

这是最标准、最推荐、面试最优解法。

核心思路：

1. 遍历字符串
2. 遇到左括号直接入栈
3. 遇到右括号时：
   • 如果栈为空，直接返回 false
   • 取出栈顶元素，判断是否匹配
   • 匹配则弹出栈顶，不匹配返回 false
4. 遍历结束后，栈必须为空才是有效括号

(3) 代码实现

classSolution{publicbooleanisValid(Strings){Stack<Character>stack=newStack<>();for(inti=0;i<s.length();i++){charch=s.charAt(i);if(ch=='('||ch=='{'||ch=='['){stack.push(ch);}else{if(stack.isEmpty()){returnfalse;}charch2=stack.peek();if((ch==')'&&ch2=='(')||(ch=='}'&&ch2=='{')||(ch==']'&&ch2=='[')){stack.pop();}else{returnfalse;}}}returnstack.isEmpty();}}

(4) 思路二 暴力消除法

思路非常简单直观，适合理解，但效率略低。

核心思路：

1. 不断消除字符串中最内层的合法括号对
2. 重复消除()、[]、{}
3. 直到无法消除为止
4. 最终字符串为空则有效，否则无效

(5) 代码实现

classSolution{publicbooleanisValid(Strings){while(s.contains("()")||s.contains("[]")||s.contains("{}")){s=s.replace("()","");s=s.replace("[]","");s=s.replace("{}","");}returns.isEmpty();}}

(6) 两种思路对比

栈匹配法：

• 时间复杂度 O(n)
• 空间复杂度 O(n)
• 面试推荐写法，逻辑严谨

暴力消除法：

• 代码极简
• 时间复杂度较高
• 适合理解思路，不推荐面试优先写

核心考点总结

设计循环队列

1. 循环队列依靠取模实现循环结构
2. 判空 front == rear
3. 判满 (rear+1) % len == front
4. 数组实现，浪费一个空间区分空满
5. 高频面试手写题

有效括号

1. 栈的最经典应用场景
2. 左括号入栈，右括号匹配栈顶
3. 最终栈必须为空
4. 面试必须熟练掌握

写在最后

循环队列与有效括号是栈与队列中最经典、最高频的两道算法题，几乎是数据结构面试必考题。

循环队列考察你对队列、数组、指针、循环结构的理解。
有效括号考察你对栈后进先出特性的实际运用。

掌握这两道题，代表你真正理解了栈与队列的核心思想，能够在面试中轻松应对同类题型。

后续我们将继续带来栈与队列的更多经典算法题：最小栈、逆波兰表达式求值、滑动窗口最大值、用栈实现队列、用队列实现栈等高频面试题型。