1 今日打卡题
用栈实现队列 232. 用栈实现队列 – 力扣（LeetCode）
用队列实现栈 225. 用队列实现栈 – 力扣（LeetCode）
有效的括号 20. 有效的括号 – 力扣（LeetCode）
删除字符串中的所有重复相邻项 1047. 删除字符串中的所有相邻重复项 – 力扣（LeetCode）
2 用栈实现队列
2.1 思路
栈 A（inStack）：只负责处理 “入队” 操作，所有新元素都先压入这个栈； 栈 B（outStack）：只负责处理 “出队 / 查看队首” 操作，避免每次出队都反转所有元素。 懒加载转移： 只有当 outStack 为空时，才把 inStack 的所有元素逐个弹出并压入 outStack（此时 inStack 的栈底元素会变成 outStack 的栈顶，正好是队列的队首）； 如果 outStack 不为空，直接从 outStack 弹出 / 查看元素，无需重复转移，提升效率。 判空逻辑： 队列是否为空，需要同时检查 inStack 和 outStack（两个栈都空，队列才空）。
2.2 实现代码
/**
* 用两个栈（Deque模拟栈）实现队列
* 核心思路：in栈负责入队，out栈负责出队，out空时将in的元素倒到out
*/
class MyQueue {
// in栈：专门接收新加入的元素（入队操作都往in栈塞）
private Deque<Integer> inStack;
// out栈：专门提供出队/查看队首元素（out空时，将in的元素全部倒过来）
private Deque<Integer> outStack;
/**
* 初始化两个空栈
*/
public MyQueue() {
// LinkedList实现Deque接口，支持栈的所有操作，效率高于传统Stack类
inStack = new LinkedList<>();
outStack = new LinkedList<>();
}
/**
* 入队操作：直接将元素压入in栈
* @param x 要入队的元素
*/
public void push(int x) {
// push()是Deque的栈操作：往栈顶添加元素（等价于addFirst()）
inStack.push(x);
}
/**
* 出队操作：移除并返回队列的队首元素
* @return 队列的队首元素
*/
public int pop() {
// 关键：如果out栈为空，先把in栈的所有元素转移到out栈（倒序）
transferInToOut();
// out栈的栈顶就是队列的队首，弹出栈顶即出队
return outStack.pop();
}
/**
* 查看队首元素：返回但不移除队列的队首元素
* @return 队列的队首元素
*/
public int peek() {
// 同样先检查out栈是否为空，空则转移in栈元素
transferInToOut();
// 查看out栈顶元素（不弹出）
return outStack.peek();
}
/**
* 判断队列是否为空
* @return 队列空返回true，否则false
*/
public boolean empty() {
// 只有in和out都为空时，队列才是空的
return inStack.isEmpty() && outStack.isEmpty();
}
/**
* 私有辅助方法：将in栈的所有元素转移到out栈（仅当out栈为空时调用）
* 转移后，in栈的栈底元素会变成out栈的栈顶，符合队列“先进先出”的特性
*/
private void transferInToOut() {
if (outStack.isEmpty()) {
// 循环弹出in栈的栈顶元素，压入out栈
while (!inStack.isEmpty()) {
// pop()弹出in栈顶元素，push()压入out栈顶
outStack.push(inStack.pop());
}
}
}
}
3 用队列实现栈
3.1 思路
只用一个队列，每次入队后，把除了新元素之外的所有元素重新入队（相当于把新元素 “挪” 到队首）； 这样队列的队首就是栈的栈顶，出队操作直接取队首即可。
3.2 实现代码
import java.util.LinkedList;
import java.util.Queue;
/**
* 用单个队列实现栈（最优解）
* 核心思路：入队后反转前面的元素，让新元素始终在队首（栈顶）
*/
class MyStack {
// 核心队列：模拟栈的所有操作
private Queue<Integer> queue;
/**
* 初始化空队列
*/
public MyStack() {
// LinkedList是Queue接口的常用实现，支持所有队列操作
queue = new LinkedList<>();
}
/**
* 入栈操作：将元素压入栈顶
* @param x 要入栈的元素
*/
public void push(int x) {
// 1. 先把新元素入队（此时新元素在队尾）
queue.offer(x);
// 2. 获取当前队列的大小（新元素入队后的长度）
int size = queue.size();
// 3. 把除了新元素之外的所有元素（前size-1个）重新入队
// 目的：让新元素从队尾挪到队首（栈顶）
for (int i = 0; i < size – 1; i++) {
// 弹出队首元素，重新压入队尾
queue.offer(queue.poll());
}
}
/**
* 出栈操作：移除并返回栈顶元素
* @return 栈顶元素
*/
public int pop() {
// 队首就是栈顶，直接出队即可
return queue.poll();
}
/**
* 查看栈顶元素：返回但不移除栈顶元素
* @return 栈顶元素
*/
public int top() {
// 查看队首元素（栈顶）
return queue.peek();
}
/**
* 判断栈是否为空
* @return 栈空返回true，否则false
*/
public boolean empty() {
// 队列空则栈空
return queue.isEmpty();
}
}
4 有效的括号
4.1 思路
1. 栈的核心作用 括号匹配的本质是 “最近匹配”—— 最内层的左括号必须最先被匹配，而栈的 “先进后出（LIFO）” 特性完美适配这一需求： 遇到左括号时，记录 “预期要匹配的右括号”； 遇到右括号时，检查是否与 “最近记录的预期右括号” 一致； 最终栈为空则所有括号匹配成功，否则存在未闭合的左括号。 2. 反向映射的巧妙设计 传统思路会用哈希表存储 “右括号→左括号” 的映射，而最优思路是反向存储预期值： 遇到左括号（(/[/{）时，直接将对应的右括号（)/]/}）压入栈； 遇到右括号时，只需对比栈顶元素是否等于当前右括号（无需额外查表）； 该思路省去哈希表的额外空间开销，逻辑更紧凑。 3. 边界条件全覆盖 解题时需重点处理 3 类无效场景： 场景 1：遇到右括号但栈为空（无左括号匹配，如输入 ")"）； 场景 2：右括号与栈顶的预期括号不匹配（如输入 "(]"）； 场景 3：遍历结束后栈非空（有未闭合的左括号，如输入 "(()"）。
4.2 实现代码
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public boolean isValid(String s) {
// 初始化栈：用于存储“预期匹配的右括号”，Deque比传统Stack更高效
Deque<Character> stack = new LinkedList<>();
// 遍历字符串中的每个字符
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 情况1：遇到左括号 → 压入对应的右括号（记录预期匹配的字符）
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
}
// 情况2：遇到右括号 → 检查是否匹配
else {
// 边界1：栈空（无左括号匹配） 或 栈顶预期值≠当前右括号 → 直接返回false
if (stack.isEmpty() || stack.peek() != c) {
return false;
}
// 匹配成功 → 弹出栈顶的预期右括号（完成一次有效匹配）
stack.pop();
}
}
// 边界2：栈为空 → 所有括号都匹配；栈非空 → 有未闭合的左括号
return stack.isEmpty();
}
}
5 删除字符串中的所有重复相邻项
5.1 思路
初始化一个空栈，用于存储 “未被消除的字符”； 遍历字符串的每个字符： 若栈非空且当前字符 = 栈顶字符 → 弹出栈顶（消除重复项）； 否则 → 将当前字符压入栈； 遍历结束后，栈中剩余字符即为 “无相邻重复” 的结果； 将栈中字符按顺序拼接成字符串（栈是逆序存储，需调整顺序）。
5.2 实现代码
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public String removeDuplicates(String s) {
// 1. 初始化双端队列作为栈（Deque比传统Stack更高效，Java推荐写法）
Deque<Character> stack = new LinkedList<>();
char ch; // 存储当前遍历的字符
// 2. 遍历字符串中的每个字符
for(int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
// 核心逻辑：栈非空 且 当前字符与栈顶字符重复 → 弹出栈顶（消除重复项）
if(!stack.isEmpty() && ch == stack.peek()) {
stack.pop();
} else {
// 无重复 → 将当前字符压入栈中
stack.push(ch);
}
}
// 3. 将栈中剩余字符转换为字符串（栈是逆序存储，需从后往前填充）
int len = stack.size();
char[] sArr = new char[len]; // 字符数组存储结果
// 栈弹出的是“最后压入的字符”，需填充到数组末尾
for(int i = len – 1; i >= 0; i–) {
sArr[i] = stack.pop();
}
// 4. 字符数组转字符串返回
return new String(sArr, 0, len);
}
}
