当前位置：首页 > news >正文

代码随想录算法训练营 Day09 | 栈与队列 part01

news 2026/3/27 2:39:30

232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现MyQueue类：
void push(int x)将元素 x 推到队列的末尾
int pop()从队列的开头移除并返回元素
int peek()返回队列开头的元素
boolean empty()如果队列为空，返回true；否则，返回false

class MyQueue { public: // 双栈设计：st1=输入栈，st2=输出栈 stack<int>st1,st2; // 构造函数：初始化空栈 MyQueue() { } // 入队：直接压入输入栈st1 void push(int x) { st1.push(x); } // 出队：核心操作 int pop() { // 关键：输出栈为空时，才将输入栈所有元素倒入 if(st2.empty()){ while(!st1.empty()){ st2.push(st1.top()); st1.pop(); } } // 输出栈栈顶就是队首元素 int val=st2.top(); st2.pop(); return val; } // 获取队首元素：【巧妙复用pop函数】，代码极简 int peek() { int val=pop(); // 先弹出 st2.push(val); // 再压回，不改变队列结构 return val; } // 判断队列空：两个栈都为空才是空队列 bool empty() { return st1.empty()&&st2.empty(); } };

总结

1. 设计思想

用两个栈模拟队列，利用栈先进后出的特性，反转元素顺序，实现队列先进先出：

输入栈st1：专门接收新元素（push）；
输出栈st2：专门弹出 / 查看队首元素（pop/peek）；
倒数据规则：仅当st2为空时，才将st1所有元素一次性倒入st2。

入队：1 → 2 → 3

全部压入st1：st1=[1,2,3]，st2=[]
执行pop：st2空，将st1倒入st2→st2=[3,2,1]
弹出st2栈顶1，实现队首出队，符合 FIFO

2. 重点

核心难点：为什么必须等st2空了再倒数据？如果st2不为空就倒数据，会破坏元素的先后顺序，无法实现 FIFO；
关键规则：倒数据必须一次性把st1全部元素倒入st2；
结构不变性：peek复用pop后要重新压入，保证队列结构不被修改。
复用优化：peek直接复用pop函数，弹出后再压回，完全消除重复代码，是面试推荐的优雅写法；

3. 复杂度分析

时间复杂度：O(1) 每个元素只会入栈 2 次、出栈 2 次，平均操作复杂度为常数；
空间复杂度：O(n) 用两个栈存储所有元素，无额外冗余空间。

225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop和empty）。
实现MyStack类：
void push(int x)将元素 x 压入栈顶。
int pop()移除并返回栈顶元素。
int top()返回栈顶元素。
boolean empty()如果栈是空的，返回true；否则，返回false。

class MyStack { public: // 单队列模拟栈，极简设计（最优解） queue<int>que; MyStack() { } // 入栈：直接向队列尾部添加元素 void push(int x) { que.push(x); } // 出栈：核心操作 int pop() { // 保留最后1个元素（栈顶），将前面所有元素重新入队 int n = que.size() - 1; while(n--){ que.push(que.front()); // 队头元素移到队尾 que.pop(); } // 此时队头就是栈顶元素，弹出返回 int val = que.front(); que.pop(); return val; } // 获取栈顶元素：极致优化！直接取队列尾部元素 int top() { return que.back(); } // 判断栈空：直接判断队列空 bool empty() { return que.empty(); } };

总结

1. 设计思想

用单个队列模拟栈，利用队列先进先出的特性，通过循环移动元素实现栈先进后出：

入栈：直接将元素加入队列尾部；
出栈：将队列前 size-1 个元素依次移到队尾，此时队头元素就是栈顶，直接弹出；
取栈顶：队列尾部元素就是栈顶元素。

执行流程示例

入栈：1 → 2 → 3
队列：[1,2,3]
出栈操作：移动前 2 个元素 → 队列变为[3,1,2]
弹出队头3（栈顶），完成出栈。

2. 重点

核心逻辑：pop时为什么要移动size-1个元素？队列只能从队头删除，移动前size-1个元素后，原队尾的栈顶元素会变到队头，才能弹出；
关键优化：top函数直接调用que.back()获取队尾元素（栈顶），完全消除冗余循环，时间复杂度 O(1)；

3. 复杂度分析

push/empty/top：时间复杂度 O(1)，直接操作；
pop：时间复杂度 O(n)，需要移动元素；
空间复杂度：O(n)，用单个队列存储所有元素。

20. 有效的括号
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

class Solution { public: bool isValid(string s) { stack<int>st; // 遍历字符串中的每个字符 for(char c:s){ // 遇到左括号，直接将【对应的右括号】入栈 if(c=='(') st.push(')'); else if(c=='{') st.push('}'); else if(c=='[') st.push(']'); // 遇到右括号：匹配栈顶元素则出栈 else if(!st.empty() && c==st.top()) st.pop(); // 栈空/不匹配，直接返回false else return false; } // 最终栈必须为空！否则有多余的左括号未匹配 return st.empty(); } };

总结

1. 设计思想

利用栈解决括号匹配问题，是栈最经典的应用场景，核心逻辑：

左括号入栈：遇到左括号，直接压入对应的右括号（省去后续复杂匹配）；
右括号匹配：遇到右括号，检查是否与栈顶元素一致：
- 一致：弹出栈顶（完成匹配）；
- 不一致 / 栈为空：括号不合法，直接返回false；
最终校验：遍历完成后，栈必须为空，代表所有左括号都匹配完成。

s = "()[]{}"

(→ 压入)
)→ 匹配栈顶)，弹出
[→ 压入]
]→ 匹配栈顶]，弹出
{→ 压入}
}→ 匹配栈顶}，弹出栈空 → 返回true

2. 重点

优化：遇到左括号直接压对应右括号，无需存储左括号再做判断，代码量减少一半；
边界处理完美
- 栈空时遇到右括号，直接返回false；
- 遍历结束校验栈是否为空，处理多余左括号的情况；
易错点：遍历结束必须判断栈是否为空（例如输入"("，遍历完栈不为空，不合法）；

4. 复杂度分析

时间复杂度：O(n) 仅遍历一次字符串，每个元素入栈 / 出栈各一次；
空间复杂度：O(n) 最坏情况（全是左括号），栈存储所有字符。

1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在s上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

class Solution { public: string removeDuplicates(string s) { string ans; // 用字符串直接模拟栈，back()=栈顶，push_back=入栈，pop_back=出栈 for(char c : s){ // 当前字符与字符串最后一个字符重复 → 删除最后一个字符（出栈） if(!ans.empty() && c == ans.back()) ans.pop_back(); // 不重复 → 追加字符（入栈） else ans.push_back(c); } // 字符串本身就是正序，直接返回 return ans; } };