「代码随想录算法训练营」第九天 | 栈与队列 part1
232. 用栈实现队列
题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/
题目难度：简单
文章讲解：https://programmercarl.com/0232.用栈实现队列.html
视频讲解：https://www.bilibili.com/video/BV1nY4y1w7VC
题目状态：看视频讲解后通过
思路：
通过两个栈来实现队列。
- 创建两个栈
stackIn和stackOut； - 当入队的时候，直接把元素入
stackIn栈中即可； - 当出队的时候，若
stackOut中没有元素时，先将stackIn中的元素入stackOut中，再从stackOut中出栈； - 当返回队头时，直接调用出队的代码即可；
- 当判断是否为空队的时候，只需要判断两个栈是否都为空即可。
代码实现：
class MyQueue {
public:
stack<int> stackIn;
stack<int> stackOut;
MyQueue() {
}
void push(int x) {
stackIn.push(x);
}
int pop() {
if(stackOut.empty()) {
while(!stackIn.empty()) {
stackOut.push(stackIn.top());
stackIn.pop();
}
}
int res = stackOut.top();
stackOut.pop();
return res;
}
int peek() {
int res = this->pop();
stackOut.push(res);
return res;
}
bool empty() {
return stackIn.empty() && stackOut.empty();
}
};
/**
* 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. 用队列实现栈
题目链接：https://leetcode.cn/problems/implement-stack-using-queues/
题目难度：简单
文章讲解：https://programmercarl.com/0225.用队列实现栈.html
视频讲解：https://www.bilibili.com/video/BV1Fd4y1K7sm
题目状态：看代码随想录思路后通过
思路一（两个队列）：
- 创建两个队列，一个是用来各种操作的队列
que1，一个用来存储元素的辅助队列que2； - 入栈：将元素压入
que1中即可； - 出栈：将
que1中除了最后一个元素以外的其他元素压入que2中，并将que1中的最后一个元素输出，最后将que2中的元素再返给que1并清空que2； - 输出栈头：返回
que1的队尾； - 判断栈是否为空：返回
que1队列是否为空。
代码实现：
class MyStack {
public:
queue<int> que1;
queue<int> que2;
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
size--;
while(size--) {
que2.push(que1.front());
que1.pop();
}
int res = que1.front();
que1.pop();
que1 = que2;
while(!que2.empty()) {
que2.pop();
}
return res;
}
int top() {
return que1.back();
}
bool empty() {
return que1.empty();
}
};
/**
* 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();
*/
思路二（一个队列）
- 创建一个队列
que； - 入栈：将元素压入
que中即可； - 出栈：将
que中除了最后一个元素以外的其他元素重新压入que中，并将que刚开始的最后一个元素（现在是第一个元素）弹出； - 输出栈头：返回
que的队尾； - 判断栈是否为空：返回
que队列是否为空。
代码实现：
class MyStack {
public:
queue<int> que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();
size--;
while(size--) {
que.push(que.front());
que.pop();
}
int res = que.front();
que.pop();
return res;
}
int top() {
return que.back();
}
bool empty() {
return que.empty();
}
};
/**
* 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. 有效的括号
题目链接：https://leetcode.cn/problems/valid-parentheses/
题目难度：简单
文章讲解：https://programmercarl.com/0020.有效的括号.html
视频讲解：https://www.bilibili.com/video/BV1AF411w78g
题目状态：看代码随想录思路后通过
思路：
- 若字符串中元素的个数为奇数，说明括号肯定不匹配，直接返回
false； - 创建一个栈；
- 如果遍历的元素是括号的左半部分，将对应的右半部分压入到栈中；
- 如果遍历到的元素是括号的右半部分，则判断栈中的元素是否和该括号对应，若不对应，说明两个括号无法匹配，则返回
false； - 若栈中元素和遍历到的元素匹配且最终栈为空，则返回
true。
代码实现：
class Solution {
public:
bool isValid(string s) {
if(s.size() % 2 != 0) return false;
stack<char> st;
for(auto &sElem : s) {
if(sElem == '(') st.push(')');
else if(sElem == '{') st.push('}');
else if(sElem == '[') st.push(']');
else if(st.empty() || st.top() != sElem) return false;
else st.pop();
}
return st.empty();
}
};
1047. 删除字符串中的所有相邻重复项
题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
题目难度：简单
文章讲解：https://programmercarl.com/1047.删除字符串中的所有相邻重复项.html
视频讲解：https://www.bilibili.com/video/BV12a411P7mw
题目状态：通过
个人思路：
- 创建一个栈来存放字符串中的元素；
- 遍历字符串；
- 若栈不为空且遍历到的字符串中的元素等于栈中的元素，将栈中元素弹出；
- 相反，若遍历到的元素不等于栈中的元素，则将元素压入栈中；
- 遍历完成后，将栈中的元素依次弹出，并存储在一个
string类型的变量res中； - 反转
res并返回。
代码实现：
class Solution {
public:
string removeDuplicates(string s) {
int size = s.size();
stack<char> st;
for(auto &sElem : s) {
if(!st.empty() && sElem == st.top()) st.pop();
else st.push(sElem);
}
string res;
while(!st.empty()) {
res += st.top();
st.pop();
}
reverse(res.begin(), res.end());
return res;
}
};