栈、队列及其常见变形、实战应用
栈(stack)
队列(queue)
双端队列(deque)
优先队列(priority queue)
一般的队列是以“时间”为顺序的(先进先出)
优先队列按照元素的“优先级”取出
“优先级”可以是自己定义的一个元素属性
许多数据结构都可以用来实现优先队列,例如二叉堆、二叉平衡树等
时间复杂度
栈、队列
- Push (入栈、入队) : 0(1)
- Pop (出栈、出队) : 0(1)
- Access (访问栈顶、访问队头) : 0(1)
双端队列
- 队头、队尾的插入、删除、访问也都是0(1)
优先队列
- 访问最值: 0(1)
- 插入:一般是0(logN), 一些高级数据结构可以做到0(1)
- 取最值: O(logN)
实战
20.有效的括号
https://leetcode.cn/problems/valid-parentheses/
- 栈与“括号序列”
- 最近相关性
class Solution { public: //最近相关性,一般要想到栈 bool isValid(string s) { for(char ch:s){ if(ch=='(' || ch=='{' || ch=='[') { a.push(ch); }else{ if(a.empty()) return false; if(ch==')' && a.top()!='(') return false; if(ch==']' && a.top()!='[') return false; if(ch=='}' && a.top()!='{') return false; a.pop(); } } return a.empty(); } private: stack<char> a; };
155.最小栈
https://leetcode.cn/problems/min-stack/
- 前缀最小值
class MinStack { public: MinStack() { } void push(int val) { s.push(val); if(preMin.empty()) preMin.push(val); else{ preMin.push(min(val,preMin.top())); } } void pop() { s.pop(); preMin.pop(); } int top() { return s.top(); } int getMin() { return preMin.top(); } private: stack<int> preMin; stack<int> s; }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
表达式求值系列问题
150.逆波兰表达式求值
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
建立一个用于存数的栈，逐一扫描后缀表达式中的元素。
- 如果遇到一个数,则把该数入栈
- 如果遇到运算符,就取出栈顶的两个数进行计算,然后把结果入栈
扫描完成后，栈中恰好剩下一个数,就是该后缀表达式的值。
时间复杂度0(n)
class Solution { public: int evalRPN(vector<string>& tokens) { for(string& token:tokens){ if(token== "+" || token== "-" ||token== "*" || token== "/") { int y=s.top(); s.pop(); int x=s.top(); s.pop(); s.push(cal(x,y,token)); }else{ s.push(atoi(token.c_str())); } } return s.top(); } int cal(int x,int y,string token){ if(token=="+") return x+y; if(token=="-") return x-y; if(token=="*") return x*y; if(token=="/") return x/y; return 0; } private: stack<int> s; };
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> nums; for(int i=0;i<tokens.size();i++) { if(isNumber(tokens[i])) { int a=stoi(tokens[i]); nums.push(a); }else{ int num2=nums.top(); nums.pop(); int num1=nums.top(); nums.pop(); switch(tokens[i][0]){ case '+': nums.push(num1+num2); break; case '-': nums.push(num1-num2); break; case '*': nums.push(num1*num2); break; case '/': nums.push(num1/num2); break; } } } return nums.top(); } bool isNumber(string& token) { return !(token == "+" || token == "-" || token == "*" || token == "/"); } };
224.基本计算器
https://leetcode.cn/problems/basic-calculator/
建立一个用于存运算符的栈,逐一扫描中缀表达式中的元素。
- 如果遇到一个数,输出该数
- 如果遇到左括号，把左括号入栈
- 如果遇到右括号,不断取出栈顶并输出,直到栈顶为左括号,然后把左括号出栈
- 如果遇到运算符，只要栈顶符号的优先级>=新符号，就不断取出栈顶并输出，最后把新符号进栈。优先级顺序为乘除号>加减号>左括号
- 思考:如何辨别运算符是加减法运算还是正负号?
依次取出并输出栈中的所有剩余符号。
最终输出的序列就是一个与原中缀表达式等价的后缀表达式，再对后缀表达式求值。
时间复杂度0(n)
class Solution { public: int calculate(string s) { s +=" "; vector<string> tokens; string number=""; bool needsZero = true; for(char ch : s){ if(ch>='0' && ch<='9'){ number+=ch; needsZero = false; continue; }else{ if(!number.empty()){ tokens.push_back(number); number = ""; } } if(ch == ' ') continue; if(ch == '('){ ops.push(ch); needsZero = true; continue; } if(ch ==')'){ while(ops.top()!='('){ tokens.push_back(string(1,ops.top())); ops.pop(); } ops.pop(); needsZero = false; continue; } if((ch == '+' || ch =='-') && needsZero ){ tokens.push_back("0"); } int currRank=getRank(ch); while(!ops.empty() && getRank(ops.top()) >=currRank){ tokens.push_back(string(1,ops.top())); ops.pop(); } ops.push(ch); needsZero = true; } while(!ops.empty()){ tokens.push_back(string(1,ops.top())); ops.pop(); } return evalRPN(tokens); } public: int evalRPN(vector<string>& tokens) { for(string& token:tokens){ if(token== "+" || token== "-" ||token== "*" || token== "/") { int y=s.top(); s.pop(); int x=s.top(); s.pop(); s.push(cal(x,y,token)); }else{ s.push(atoi(token.c_str())); } } return s.top(); } int cal(int x,int y,string token){ if(token=="+") return x+y; if(token=="-") return x-y; if(token=="*") return x*y; if(token=="/") return x/y; return 0; } private: stack<int> s; private: stack<char> ops; int getRank(char ch){ if(ch =='*' || ch=='/' ) return 2; if(ch =='+' || ch=='-' ) return 1; return 0; } };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
