栈与队列
栈
概念
栈是操作受限的线性表，只允许在表的同一端进行插入和删除操作。
进行插入、删除的一端叫“栈顶 (top)” 另一端叫”栈底 (bottom)“ 没有元素称为“空栈” 插入元素叫“入栈（压栈 push）”；删除元素叫“出栈（弹栈 pop）”
特性
“后进先出”：后放进去的元素，最先拿出来。
常见应用
函数调用栈、表达式求值、括号匹配、递归、回溯。
实现
可以用数组（顺序栈）、链表（链栈）实现。
队列
概念
队列也是操作受限的线性表：只能在一端插入，另一端删除。
插入的一端叫“队尾 ” 删除的一端叫“队头” 无元素叫空队列 插入：“入队"；删除："出队"
特性
先进先出：先进入队列的元素，最先出去。
常见应用
任务排队、消息队列、广度优先搜索 BFS、打印任务调度。
分类
1. 普通队列 2. 循环队列：解决顺序队列假溢出问题 3. 双端队列 Deque：两端都可以入队、出队
实现
数组（循环队列）、链表（链队列）。
对比
| 对比项 | 栈 | 队列 |
| 操作规则 | 后进先出 | 先进先出 |
| 插入删除位置 | 同一端（栈顶） | 两端：队尾插入，队头删除 |
| 主要操作 | push 入栈、pop 出栈、top 取栈顶 | enqueue 入队、dequeue 出队、front 取队头 |
| 空条件 | 栈中无元素 | 队中无元素 |
| 典型场景 | 递归、函数调用、括号匹配 | BFS、任务排队、消息处理 |
共同点：都是线性结构；都不支持中间位置插入删除，操作受限
LeetCode 20
括号匹配是栈的经典应用 栈的特性：后进先出，最后遇到的左括号，要最先被对应的右括号闭合。
建立字典 `mapping`：key 为右括号，value 为对应的左括号，用来做匹配对照。
遍历字符串每一个字符： 1. 如果当前字符是右括号（存在于 mapping 中）： 如果栈不为空，弹出栈顶元素；栈为空就弹出一个占位符`#`。 把弹出的栈顶，和该右括号对应的左括号对比，如果不相等，说明匹配失败，直接返回`False`。 2. 如果当前字符是左括号：压入栈中。
遍历结束：如果栈为空，说明全部左括号都找到了匹配，返回`True`；栈不为空代表还有未匹配的左括号，返回`False`。
LeetCode 225
单队列：即使用队列本身实现栈
队列是先进先出，栈是后进先出。 只用一个队列模拟栈： `push`：直接把元素加到队列尾部。 `pop`：栈顶是队列最后加入的元素。把队列前面 `n‑1` 个元素全部出队，再重新加到队列尾部；此时队列头部就是原来最后加入的元素，直接弹出。 `top`：复用`pop()`拿到栈顶值，再把这个值重新压回队列，返回该值。 `empty`：直接判断队列是否为空。
LeetCode 232
输入输出分开处理：初始化空的输入输出栈，输入栈负责输入，输出栈负责输出
队列的入操作：直接放进输入栈即可 队列的出操作：直接将输出栈的元素出栈即可（输出栈不为空），若输出栈为空，则将输入栈的元素出栈，一个个放入输出栈（此时输出顺序颠倒，符合队列的先进先出特性），再将输出栈的栈顶元素输出
队列的首元素获取：执行队列的出操作获取首元素，然后放回输出栈保持原状即可 队列的为空判断：输入输出栈都为空即可
