2026.02.06 第十天
232 用栈实现队列
比较简单的一道题，知道栈先入后出的原理后使用两个栈进行配合即可实现队列。
一个栈专门用于入队，一个栈专门用于出队，当出队栈中没有元素之后将入队栈的元素全部转移到出队栈即可。
代码实现：
class MyQueue {
public:stack<int> staIn;stack<int> staOut;MyQueue() {}void push(int x) {staIn.push(x);}int pop() {if(staOut.size() == 0) {int num = staIn.size();for(int i = 0; i < num; i++) {staOut.push(staIn.top());staIn.pop();}}int temp = staOut.top();staOut.pop();return temp;}int peek() {staOut.push(this->pop());return staOut.top();}bool empty() {return staOut.size() == 0 && staIn.size() == 0;}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/
225 用队列实现栈
不算难，但是实现方式感觉不优雅~
一个队列的实现方式：
入栈就按照队列进行入队，出队时将前面的n-1个元素以此出队再入队，就将队尾元素移到了队首，对于连续出队不友好。
class MyStack {
public:queue<int> que;MyStack() {}void push(int x) {que.push(x);}int pop() {int num = que.size();for(int i = 0; i < num - 1; i++) {que.push(que.front());que.pop();}int temp = que.front();que.pop();return temp;}int top() {int num = que.size();for(int i = 0; i < num - 1; i++) {que.push(que.front());que.pop();}int temp = que.front();for(int i = 0; i < num + 1; i++) {que.push(que.front());que.pop();}return temp;}bool empty() {return que.size() == 0;}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/
20 有效的括号
栈的简单应用，遇到左括号入栈，遇到右括号就检查栈顶元素是否匹配当前右括号即可。
最后检查栈是否空，防止有多余的左括号。
函数最开始可以判断字符串中字符数量，是奇数则绝对做不到完全匹配。
class Solution {
public:bool isValid(string s) {if(s.size() % 2 == 1) {return false;}stack<char> sta;for (int i = 0; i < s.size(); i++) {if (s[i] == '(' || s[i] == '[' || s[i] == '{') {sta.push(s[i]);}else if(sta.size() == 0) {return false;}else if (sta.top() == '(' && s[i] == ')') {sta.pop();}else if (sta.top() == '[' && s[i] == ']') {sta.pop();}else if (sta.top() == '{' && s[i] == '}') {sta.pop();}else {return false;}}return sta.empty();}
};
1047 删除字符串中的所有相邻重复项
注意是相邻重复项，如果有三个及以上的奇数个连续重复项也要保留最后一个。
我的写法：
class Solution {
public:string removeDuplicates(string s) {stack<char> sta;for(int i = 0; i < s.size(); i++) {if(sta.empty() != true && s[i] == sta.top()) {sta.pop();continue;}else {sta.push(s[i]);}}string result = "";while(sta.empty() != true) {result += sta.top();sta.pop();}reverse(result.begin(), result.end());return result;}
};
上面的代码额外使用了栈，最后还要将栈转换为字符串并反转，额外耗费了时间和空间，如果直接将字符串作为栈来使用，时间和内存效率大幅提升：
class Solution {
public:string removeDuplicates(string S) {string result; // 用作“栈”：模拟删除过程for(char s : S) {if(result.empty() || result.back() != s) { // 栈空 或 栈顶 ≠ 当前字符 → 入栈result.push_back(s);}else {result.pop_back(); // 栈顶 == 当前字符 → 相邻重复！弹出栈顶（相当于删除这一对）}}return result; // 最终栈中剩下的就是结果}
};
时间复杂度：O(n)
每个字符最多入栈一次、出栈一次，总操作 ≤ 2n。
空间复杂度：O(n)
最坏情况下（无重复），result 存储全部 n 个字符。
这段代码的精妙之处在于：
用一个字符串模拟栈，通过“入栈/出栈”自动处理了所有层级的相邻重复删除，一次遍历搞定！
这是解决“相邻消除类问题”的标准模板，类似题目还有：
删除 k 个相邻重复（LeetCode 1209）
表达式求值（如括号匹配）
🧠 核心思想：栈天然适合处理“成对抵消”或“回退”类问题。