LeetCode | 栈与队列：算法入门到进阶的全解析

栈和队列作为最基础的数据结构，不仅简单直观，还在算法世界中扮演着举足轻重的角色。无论是处理括号匹配问题、滑动窗口、还是实现先进先出的任务调度，栈与队列都是核心工具。

在本篇文章中，我们将以 LeetCode 中的经典题目为例，全面讲解栈与队列的使用场景、解题技巧以及优化方法。不管你是算法新手还是想巩固基础，这篇博客都能帮你快速掌握栈与队列的精髓！

1.理论

1.1.栈(Stack)

1.1.1.基本概念

一种后进先出(LIFO - Last In First Out)的线性数据结构
只允许在一端（栈顶）进行插入和删除操作
就像一摞盘子，只能从顶部放入或取出

1.1.2.基本操作

push：将元素压入栈顶
pop：移除并返回栈顶元素
peek/top：查看栈顶元素但不移除
isEmpty：检查栈是否为空
size：返回栈中元素个数

1.1.3.常见应用

函数调用栈
表达式求值
括号匹配
浏览器前进/后退功能
撤销操作(Undo)

1.2.队列(Queue)

1.2.1.基本概念

一种先进先出(FIFO - First In First Out)的线性数据结构
在一端(队尾)添加元素，另一端(队首)删除元素
类似排队买票，先到先得

1.2.2.基本操作

enqueue：在队尾添加元素
dequeue：移除并返回队首元素
front：查看队首元素但不移除
isEmpty：检查队列是否为空
size：返回队列中元素个数

1.2.3.常见应用

打印任务队列
消息队列
广度优先搜索(BFS)
进程调度
资源共享

总结

最优解的核心是利用栈来处理括号的先进后出特性，并通过映射表快速检查括号是否匹配。这种方法既简单又高效，是解决括号匹配类问题的通用模板。

2.真题

【Leetcode 20】有效的括号(Valid Parentheses)

题目描述

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

有效字符串的条件：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例：

输入：s = "()"，输出：true
输入：s = "()[]{}"，输出：true
输入：s = "(]"，输出：false

解题思路

括号匹配的映射关系：
- 创建一个哈希表 mapping，用来存储每种右括号对应的左括号。
- 如：mapping = {')': '(', '}': '{', ']': '['}。
使用栈：

遇到左括号时，将其压入栈中。
遇到右括号时：检查栈顶元素是否与其匹配;如果匹配，弹出栈顶元素；如果不匹配，返回 False。

3.遍历结束后检查栈：如果栈为空，说明所有括号都匹配成功；否则，返回 False。

class Solution:
    def isValid(self,s:str)->bool:
        stack=[]
        mapping={')':'(',']':'[','}':'{'}

        for char in s:
            if char in mapping:
                top_element=stack.pop() if stack else '#'
                if mapping[char]!=top_element:
                    return False

            else:
                stack.append(char)

        return not stack 
    
# top_element=stack.pop() if stack else '#'合并了检查栈是否为空和获取栈顶元素两个操作
## 如果栈为空，设置一个特殊字符 '#' 作为默认值
##  如果栈不为空，直接弹出栈顶元素

复杂度分析

时间复杂度：每个字符最多入栈或出栈一次;总时间复杂度为 O(n)，其中 n 是字符串的长度。

空间复杂度：最坏情况下，栈中需要存储所有左括号。空间复杂度为 O(n)。