力扣刷题总结 栈与队列
🔥博客主页:?A_SHOWY
🎥系列专栏:力扣刷题总结录?数据结构??云计算??数字图像处理??力扣每日一题_
一、栈和队列的基础知识
队列是先进先出,栈是先进后出。同时二者都是容器适配器而不是容器。
?二、题目实战
232.用栈实现队列 | easy | 基础操作 |
225.用队列实现栈 | easy | 基础操作 |
20.有效的括号 | easy | 碰到左括号存栈里,等右括号匹配 |
1047.删除字符串中所有的重复项 | mid | 匹配相邻元素消除 |
150.逆波兰式求和 | mid | 字符转换整型 |
239.滑动窗口的最大值 | hard | 双值队列的应用,巧妙 |
(1)232.用栈实现队列
232. 用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/我们知道栈是先进先出,队列是先进后出。所以要用栈来实现队列,需要一个输入栈一个输出栈(按输入的顺序倒叙存放)。这个题目有四个操作
1.第一个操作很容易就是一个入队列的操作和入栈一样?
?
void push(int x) {
stkIn.push(x);
}
2.第二个操作是出队列的操作,这个操作就有一定的难度,我们需要一个?输入栈和一个输出栈,当输出栈为空的时候,我们需要把输入栈的所有元素全部弹出到输出栈,这样从输出栈进行pop这个顺序满足先入先出。输出栈弹出的第一个元素就我们的结果。
int pop() {
//当out栈为空的时候
if(stkOut.empty()){
while(!stkIn.empty()){//把所有in栈里面的东西全部弹出给out,否则顺序不对
stkOut.push(stkIn.top());
stkIn.pop();
}
}
int res = stkOut.top();
stkOut.pop();
return res;
3.第三个操作是返回队列开头的元素,我们发现和第二个操作是大量重复代码相似的操作,所以我们可以直接复制第二问的代码,但是我们专业来说可以用this->来直接调用同一个类中的函数,调用结束后发现多弹出一个元素,我们再push回去就可以了。
int peek() {
//学会运用this->,这里发现和pop操作的代码大同小异
int res = this -> pop();
//发现这里多弹出了
stkOut.push(res);
return res;
}
第四个操作是?判断队列是否为空,直接判断入栈和出栈相与为空,说明两个栈都没有元素时为空既可。
bool empty() {
return stkIn.empty() && stkOut.empty();
}
?(2)225.用队列实现栈
225. 用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/这道题目其实就是用一个队列来实现栈,具体思路和上一题有很多相似之处。
1.首先第一个问题还是一个push操作,栈和队列的push操作是一样的,所以可以直接push
void push(int x) {
q.push(x);
}
2.第二个pop操作还是整个题目最需要思考的。当一个队列的时候,我们的整体思路是把size-1个元素取出来然后重新push进入队列。再pop队列front的元素一次。
int pop() {
int size = q.size();
size--;
while(size--){
q.push(q.front());
q.pop();
}
int res = q.front();
q.pop();
return res;
}
3.第三个操作直接使用back就可以解决?
int top() {
return q.back();
}
4.第四个操作,空值操作
bool empty() {
return q.empty();
}
可以看出来整体思路还是比较简单的,除了pop操作需要多思考一下,其他小问的要求容易。
拓展:如果要求使用两个队列来满足栈的pop操作
将第一个队列的size-1个元素移动到第二个队列中 ,留下的最后一个元素就是要返回的值,再把第二个队列中的元素移动到第一个队列中即可。核心思想不变。但是记住要把q1最后清空。
int pop() {
// int size = q.size();
// size--;
// while(size--){
// q.push(q.front());
// q.pop();
// }
// int res = q.front();
// q.pop();
// return res;
int size = q.size();
size--;
while(size--){
q1.push(q.front());
q.pop();
}
int res = q.front();
q.pop();
q = q1;
//还要清空q1
while(!q1.empty())
{
q1.pop();
}
return res;
}
(3)20.有效的括号
20. 有效的括号https://leetcode.cn/problems/valid-parentheses/栈非常适合做这种匹配的问题,有一个小技巧,就是碰到左括号,就存一个右括号到栈里,再进行匹配。
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i = 0; i< s.size();i++){
if(s[i] == '(') st.push(')');
else if(s[i] == '{') st.push('}');
else if(s[i] == '[') st.push(']');
//第二种
else if(st.empty() || s[i] != st.top()) return false;
else st.pop();
}
return (st.empty());
}
};
(4)1047.删除字符串中所有重复项
1047. 删除字符串中的所有相邻重复项https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/?本题要删除相邻相同元素,相对于20. 有效的括号?(opens new window)来说其实也是匹配问题,20. 有效的括号是匹配左右括号,本题是匹配相邻元素,最后都是做消除的操作。用栈来存放,那么栈的目的,就是存放遍历过的元素,当遍历当前的这个元素的时候,去栈里看一下我们是不是遍历过相同数值的相邻元素。这种消除问题也是栈的经典题目。
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for(char x : s){
if(st.empty() || x != st.top()) st.push(x);//如果为空或者不相等直接push
else st.pop();//否则pop
}
//输出操作,栈先进后出,所以最好输出要反过来
string result = "";
while(!st.empty()){
result += st.top();
st.pop();
}
reverse(result.begin(),result.end());
return result;
}
};
(5) 150.逆波兰表达式求和
150. 逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/
本题也是一道和栈有关的题目,要求求逆波兰式的求值,对于这道题目,我们可以考虑到当在一个栈中栈顶为符号的时候,就从栈顶拿出来两个元素进行符号操作再放回栈顶。
需要注意的是这道题给的范围定义的long long的栈,最后字符串转换的时候要用long long的stoll
注意本题给的是tokens数组中全部都是字符串,所以在push的时候需要进行转化?
stoi 函数:将字符串转成 int 整数。 stol 函数:将字符串转成 long 整数。 stoll?函数:将字符串转成?long long 整数。?
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(int i = 0 ; i < tokens.size(); i++){
if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
int nums1 = st.top();
st.pop();
int nums2 = st.top();
st.pop();
if(tokens[i] == "+") st.push(nums2 + nums1);
if(tokens[i] == "-") st.push(nums2 - nums1);
if(tokens[i] == "*") st.push(nums2 * nums1);
if(tokens[i] == "/") st.push(nums2 / nums1);
}
else st.push(stoi(tokens[i]));
}
return st.top();
}
};
(6)239.滑动窗口的最大值
239. 滑动窗口最大值https://leetcode.cn/problems/sliding-window-maximum/这道题目是一个hard题目,思路确实很难,对于本题,我们需要一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。
队列没有必要维护窗口里的所有元素,只需要维护有可能成为窗口里最大值的元素就可以了,同时保证队列里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列,即单调递减或单调递增的队列。
我们用到的自定义的队列是一个deque,双向队列,也就是左右都能进出。我们先考虑push函数,在我们每次push的时候,当要push的元素比前面的都大时,把前面的元素全部删除,因为我们不需要维护所有的元素,我们只需要保证最大元素即可,可能有人就迷惑了,你把前面的元素都卷走了,那pop操作怎么办。pop操作就更为巧妙了,当要pop的元素和队列的front相等的时候,才是真正要pop 的时候。但是对于push和pop函数队列操作不要忘记队列不为空的判断,front函数就简单了,直接返回队列的front就可以。
在实现函数部分,先把前k个元素push进队列,找到最大的值,然后从第k+1个元素进行push,pop,front操作。最后放到数组里面返回。
class Solution {
private:
class MyQueue{
public:
deque<int> que;
void pop(int value){
if(!que.empty() && que.front() == value){
que.pop_front();
}
}
void push(int value){
while(!que.empty() && value > que.back()){
que.pop_back();
}
que.push_back(value);
}
int front(){
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> res;
for(int i = 0 ; i < k; i++){
que.push(nums[i]);//先把前k个push进去
}
res.push_back(que.front());//记录前k个元素的最大值
for(int i = k; i < nums.size();i++){
que.pop(nums[i-k]);
que.push(nums[i]);
res.push_back(que.front());
}
return res;
}
};
这道题目的重点是我们要确定维护的是大的元素,前面的元素较小在push操作时候就会被顶出。
本期总结了道题目,后续如果有相关题目会继续总结添加。?
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!