一道非常经典的队列题
队列的最大值
题目来源：剑指offer59
今天的题目还是挺有意思的，该题目是剑指offer上面的经典题目，主要考察面试者的知识迁移能力，下面我们先来看一下题目描述。
请定义一个队列并实现函数 max_value 得到队列里的最大值，若队列为空，pop_front(出队操作) 和 max_value (获取队列最大值)需要返回 -1
示例 1：
输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]
示例 2：
输入: ["MaxQueue","pop_front","max_value"] [[],[],[]] 输出: [null,-1,-1]
输入的第一行代表的执行函数，第二行代表的是输入的值，该题中只有我们的push_back传入了参数，输出代表的为执行该函数时，函数的返回值。
个人认为这个题目还是很不错的，而且也有一定的难度，大家可以试着实现一下。
为保证严谨性，文章中的所有代码都经过测试，大家可以放心食用
暴力解法
暴力法，是因为我们的max值通过每次遍历我们的动态数组来获得。思路很简单，我们创建一个动态数组，我们每次执行max_value函数时，通过遍历数组获得最大值，入队操作则用add,出队操作则用remove(0)，去除动态数组的头元素。我们在文章《希望这篇文章能合你的胃口》中提到了队列和栈的实现方式，忘记的小伙伴可以复习一下，思路很简单我们直接看代码吧。
题目代码：
class MaxQueue {
//动态数组
ArrayList<Integer> arr = new ArrayList<>();
public MaxQueue() {
}
public int max_value() {
//为空的情况
if(arr.size() == 0){
return -1;
}
//初始化max
int max = Integer.MIN_VALUE;
//遍历动态数组，获取最大值
for(int i = 0;i<arr.size();i++){
if(arr.get(i)>max){
max = arr.get(i);
}
}
return max;
}
public void push_back(int value) {
//添加元素
arr.add(value);
}
public int pop_front() {
//队列为空时，执行该函数返回-1
if(arr.size() == 0){
return -1;
}else{
return arr.remove(0);
}
}
}
利用双端队列
deque （double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。
我们了解了双端队列之后，是不是感觉很实用，很灵活，但实际上在应用程序中远不及栈和队列有用。我们了解双端队列之后，我们来聊一下我们的做题思路吧
这个思路也很简单，我们充分利用双端队列的性质，因为它可以两头出队，那我们在双端队列中仅保存队列中每一段的最大值即可，见下图。
我们分成了三段，第一段的最大值为9，第二段为8，第三段为7。那么我们这个段是怎么分的呢？
我们看第一段最大值为9前面没有其他数字，第二段最大值为8，前面的三个数字都小于8，但是它小于第一段的最大值，同理第三段也是。如果第三段的元素为6，10的话，那我们的双端队列中只有10啦，因为它大于它之前的所有值。
废话不多说下面我们直接看动图吧。
题目代码：
class MaxQueue {
Queue<Integer> queue ;
Deque<Integer> deque;
public MaxQueue() {
queue = new LinkedList<Integer>();
deque = new LinkedList<Integer>();
}
//返回最大值，此时返回的为depue的第一个元素
public int max_value() {
if(deque.isEmpty()){
return -1;
}
int max = deque.getFirst();
return max;
}
//入队操作
public void push_back(int value) {
//普通队列直接入队
queue.offer(value);
//双端队列需要先将该阶段小于value值的出队
while( !deque.isEmpty() && deque.getLast() < value){
deque.removeLast();
}
//入队value
deque.offer(value);
}
//出队操作，返回两种情况，队头小于当前阶段最大值，队头等于当前阶段最大值
public int pop_front() {
if(queue.isEmpty()){
return -1;
}
//普通队列出队
int temp = queue.poll();
//判断普通队列和双端队列的队头是否相等，两种返回情况
if(temp == deque.peekFirst()){
return deque.pollFirst();
}
else{
return temp;
}
}
}
个人感觉今天的题目很nice，考察范围很广，而且这也是一个面试常考题目，大家记得打卡啊！