栈和队列及表达式求值问题
栈和队列及表达式求值问题
- 栈、队列及其常见变形、实战应用
- 栈(stack)
- 队列(queue)
- 双端队列(deque)
- 优先队列(priority queue)
- 时间复杂度
- 实战
- 表达式求值系列问题
栈、队列及其常见变形、实战应用
栈(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等技术内容，立即学习