DAY11 栈与队列part02

逆波兰式求值

代码随想录 (programmercarl.com)

 1 class Solution {
 2 public:
 3     int evalRPN(vector<string>& tokens) {
 4     stack<long long> st;
 5     for(int i=0;i<tokens.size();i++)
 6     {
 7         
 8         if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")//双引号
 9         {
10             long long nums1=st.top();
11             st.pop();
12             long long nums2=st.top();
13             st.pop();
14             long long res;
15             if(tokens[i]=="+") res=nums1+nums2;
16             if(tokens[i]=="-") res=nums1-nums2;
17             if(tokens[i]=="*") res=nums1*nums2;
18             if(tokens[i]=="/") res=nums2/nums1;//这里注意两个数的顺序
19             st.push(res);
20         }
21         else
22         {
23             st.push(stoll(tokens[i]));//表示long long精度转化
24         }
25     }
26     return (int)st.top();
27 }
28 }；

滑动窗口最大值

代码随想录 (programmercarl.com)

 1 class Solution {
 2 private:
 3     class MYQUE{
 4         deque<int> que;
 5         public:
 6         void pop(int val)
 7         {
 8             if(!que.empty()&&que.front()==val) que.pop_front();
 9         }
10         void push(int val)
11         {
12             while(!que.empty()&&val>que.back())//这里不加等号，que里面某些数需要重复出现，否则窗口滑动会导致仅有的最大值弹出
13                 que.pop_back();
14             que.push_back(val);
15         }
16         int front()
17         {
18             return que.front();
19         }//要加上不然没有front对象
20     };
21 public:
22     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
23         vector<int> res;
24         MYQUE  que;//类的写法
25         for(int i=0;i<k;i++)
26         {
27             que.push(nums[i]);
28         }
29         res.push_back(que.front());
30         for(int i=k;i<nums.size();i++)
31         {
32             que.pop(nums[i-k]);
33             que.push(nums[i]);
34             res.push_back(que.front());
35         }
36         return res;
37     }
38 };

一、deque的简介
deque是一个双向队列（double-ended queue），可以在队列的两端进行元素的插入和删除操作。deque的全称是double-ended queue，翻译过来就是双端队列，也有人称之为双向队列，这两个名称都可以表示该数据结构。deque是C++STL（标准模板库）中的一种容器，可以用于存储各种类型的元素。deque的特点是可以在队列的两端进行元素的操作，并且可以高效地在队列的任意位置进行元素的插入和删除操作。
可以说deque几乎涵盖了queue（队列）、stack（堆栈）、vector（向量 ）等的全部用法，功能非常的强大。

使用queue时需要包含头文件：

#include<deque>

二、deque的常用成员函数

push_back()//在队列的尾部插入元素。
emplace_front()//与push_front()的作用一样 
push_front()//在队列的头部插入元素。
emplace_back()//与push_back()的作用一样 
pop_back()//删除队列尾部的元素。
pop_front()//删除队列头部的元素。
back()//返回队列尾部元素的引用。
front()//返回队列头部元素的引用。
clear()//清空队列中的所有元素。
empty()//判断队列是否为空。
size()//返回队列中元素的个数。
begin()//返回头位置的迭代器
end()//返回尾+1位置的迭代器
rbegin()//返回逆头位置的迭代器 
rend()//返回逆尾-1位置的迭代器 
insert()//在指定位置插入元素 
erase()//在指定位置删除元素