今天又是栈与队列的一天！（但也是最后一天）
题目链接：150. 逆波兰表达式求值
状态：多次尝试后未果，看解析才AC
看到题目时第一想法：没有一点点思路，勉强能理解逆波兰表达式的含义以及其在计算机领域应用的意义，但是并不能把它实现为算法。
于是就只好看解析。看完发现是真妙哇。其实操作并不麻烦，就是当遇到数字时，就把数字放入栈中，当遇到加减乘除时，就取出两个数进行相应的运算。需要注意的是做减法和做除法时要注意：先弹出来的是被减数/被除数，而加法和乘法不需要担心这个问题是因为加法交换律和乘法交换律的存在。以下是完整代码：
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList();
for(String s : tokens){
// notice the order of two nums when it is "-" and "/"
if("+".equals(s)){
stack.push(stack.pop() + stack.pop());
}else if("-".equals(s)){
stack.push(-stack.pop() + stack.pop());
}else if("*".equals(s)){
stack.push(stack.pop() * stack.pop());
}else if("/".equals(s)){
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
}else{
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}
复杂度分析：
时间复杂度：O(n). 因为for循环遍历了字符串的每一个元素是O(n)，其他步骤都是O(1)了
空间复杂度：O(n). 因为输入的是合规的逆波兰表达式，所以数字和字符的占比分别为n:n-1，因此大约是O(n/2)，即便不是2也没关系，总归是一个接近于2的常数。因此栈的操作数量大约为O(n/2).所以综合来说 空间复杂度是O(n)级别
题目链接：239. 滑动窗口最大值
状态：看解析后跟着代码敲才逐渐AC
看到题目时第一想法：没有一点点思路，暴力解法是一目了然，但是O(n*k)的时间复杂度让我望而却步，从而开始看解析然后才发现有优化方法但是思路比较难想。
解析是使用了一种叫“单调队列”的方式，该方式的队列有poll，add，peek三个方法。其中add方法就保证每次加入进来的新元素的时候，把小于新元素的值全部pop走，从而保证当前窗口内最大的元素在队列顶端peek的位置。poll方法则是当窗口要移动走了的时候，如果最大值仍是在顶端处，则pop走，否则什么也不做。peek方法则是获取顶端处的值，也就是最大值（在add的保证下，顶端的值就是最大值）具体更详细的分析参考此处
完整代码如下：
class Solution { // Java
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 1){
return nums;
}
int len = nums.length - k + 1;
// store the result
int[] res = new int[len];
int num = 0;
MyQueue myQueue = new MyQueue();
// First, put the first k elements into the queue
for(int i = 0; i < k; i++){
myQueue.add(nums[i]);
}
res[num++] = myQueue.peek();
for(int i = k; i < nums.length; i++){
// handle with the rest elements
myQueue.poll(nums[i - k]);
myQueue.add(nums[i]);
res[num++] = myQueue.peek();
}
return res;
}
}
class MyQueue { // Custom Queues
Deque<Integer> deque = new LinkedList<>();
// when poping elements, only if element == deque.peek(), we pop
void poll(int val){ // other situations will be handled in the next function
if(!deque.isEmpty() && val == deque.peek()){
deque.poll();
}
}
// when adding val, we pop all elements that are smaller than val
// so that we can make sure that the queue elements are monotonically decreasing
void add(int val){
while(!deque.isEmpty() && val > deque.getLast()){
deque.removeLast();
}
deque.add(val);
}
// after adding, deque.peek() are always the largest element
int peek(){
return deque.peek();
}
}
复杂度分析：
时间复杂度：O(n). 主要是每个元素都遍历了一次，其余都是O(1)
时间复杂度：O(n). 结果数组res需要O(n-k+1)，滑动窗口对应的队列需要O(k),所以综合就是O(n)
栈与队列总结：
栈（Stack）
基本概念
定义：栈是一种线性数据结构，遵循后进先出（LIFO，Last In, First Out）的原则。即最后入栈的元素最先出栈。
主要操作：
push：将元素压入栈顶。
pop：将栈顶元素弹出。
peek/top：返回栈顶元素但不弹出。
isEmpty：检查栈是否为空。
size：返回栈中的元素个数。
实现方式
数组：栈可以使用动态数组来实现。
链表：栈可以使用单向链表来实现。
队列（Queue）
基本概念
定义：队列是一种线性数据结构，遵循先进先出（FIFO，First In, First Out）的原则。即最先入队的元素最先出队。
主要操作：
offer/add：将元素添加到队列尾部。
poll/remove：将队列头部元素移除并返回。
peek/element：返回队列头部元素但不移除。
isEmpty：检查队列是否为空。
size：返回队列中的元素个数。
实现方式
数组：队列可以使用循环数组来实现。
链表：队列可以使用单向链表来实现。
双端队列（Deque）：队列可以用双端队列来实现，以便高效地在两端进行插入和删除操作。
双端队列（Deque）
基本概念
定义：双端队列是一种特殊类型的队列，允许在队列的两端进行插入和删除操作。
主要操作：
addFirst/offerFirst：在队列头部添加元素。
addLast/offerLast：在队列尾部添加元素。
removeFirst/pollFirst：移除并返回队列头部元素。
removeLast/pollLast：移除并返回队列尾部元素。
peekFirst/getFirst：返回队列头部元素但不移除。
peekLast/getLast：返回队列尾部元素但不移除。
实现方式
循环数组：双端队列可以使用循环数组来实现。
双向链表：双端队列可以使用双向链表来实现。
