部分来源：Java数据结构中的栈和队列（带图解）_Owen_Xp的博客-CSDN博客_java队列 堆栈
栈（stack）什么是栈？
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
压栈：向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
出栈：从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈的使用
栈的工作原理：后进先出
操作：new（新建）push（入栈）pop（出栈）peek（获取栈顶元素）isEmpty（判断栈是否为空）
根据这些操作方法来使用栈
| 方法 | 功能 |
|---|---|
| Stack() | 构造一个空的栈 |
| push(E e) | 将e入栈，并返回e |
| pop() | 将栈顶元素出栈并返回，并删除它（出栈） |
| peek() | 获取栈顶元素，但是并不在堆栈中删除它（不出栈） |
| int size() | 获取栈中有效元素个数 |
| boolean empty() | 检测栈是否为空 |
从上图可以看出，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。
队列（Queue）
什么是队列？
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
队列的使用
在Java中，Queue是个接口，底层是通过链表实现的。
| 方法 | 功能 |
| add() | 从队尾压入元素，超出容量时，add()方法会对抛出异常 |
| offer() | 从队尾压入元素，超出容量时，offer()方法会返回false |
| poll()、remove() | 容量大于0的时候，删除并返回队头元素；在容量为0的时候，remove()会抛出异常，poll()返回false |
| peek()、element() | 容量大于0的时候，都返回队头元素，但是不删除；容量为0的时候，element()会抛出异常，peek()返回null |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
注意： Queue 是个接口，在实例化时必须实例化 LinkedList 的对象，因为 LinkedList 实现了 Queue 接口。
队列的分类
队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构 。
一、顺序队列
什么是顺序队列？
顺序队列是队列的一种，只是说队列的存在形式是队列中的元素是连续的，就像数组
顺序队列的实现方式
（1）队头不动，队尾动
在元素出队列时，队头不动，队尾动，每出一个元素，就把队列中剩余的元素往前搬移，从而队尾会跟着改变。
缺点：在出队列时，需要大量搬移元素，时间复杂度为O(N)
（2）队头动，队尾不动
在元素出队列时，队头往后移动一个位置，队尾一直保持不动。
优点：在出队列时，只需把队头往后移动一个位置就好，所以时间复杂度为O(1)。
缺点：因为在元素在出队列时只是移动队头，并没有把元素在内存上删除，所以就会出现元素把整个内存耗尽，并且此内存中的存储都是不合法的元素，从而造成假溢出。
假溢出：看似内存中再存储不了元素了，但是此内存在理论上是可以使用的，内存被一些不合法的元素使用完了，从而造成一种溢出现象，但是此溢出是假溢出。
循环队列什么是循环队列？
循环队列是首尾相接的顺序存储队列，顾名思义循环队列就是队列的内存可以循环使用
为什么会有循环队列？
在顺序队列中，出现了假溢出问题，那循环队列就是为了假溢出问题的，假溢出造成了内存浪费，循环队列可以使得内存得到有效的利用
循环队列的实现
给定两个指针，分别标记队头和队尾，标记队头的指针是front,标记队尾的是rear
1、空队列
开始时，front是队头指针，rear是队尾指针，空队列时front和rear指向同一位置
2、队列中有元素
在插入元素时，rear会随着元素的插入而向后移动，front不会动，如果删除元素的话，那rear会向前移动，front也还是不会动。
循环队列如何进行判断是否存满？或者为空呢？
1、少使用一个循环队列中的存储空间
在存储元素时，少用一个存储单元，那队列空的时候，front和rear指向同一位置，那随着插入元素，rear向后移动，最后一个存储单元不使用，所以队列满的时候，rear的下一个位置就是front指向的元素
队列为空时的判断条件：front==rear时 ，队列为空队列
队列为满时的判断条件：（rear+1）%M == front时，队列为满队列
ps：M是循环队列的空间大小，即就是M标记了循环队列中最多可以存储几个元素
本来rear+1就是front指向的位置，那为什么还要跟队列的空间大小取模呢？是因为当rear指向最后一个位置的时候，下标为7，那rear+1=8，而循环队列中没有下标为8的元素，如图可知，必须对相加的结果取模
2、给一个标记flag，默认flag为false
给一个标记flag ，默认此标记为false，当插入元素就把标记flag改为true，当删除元素就把标记改为false
ps：当队列为空的时候，front和rear指向同一位置，当队列为满的时候，front和rear也是指向同一位置
队列为空时的判断条件：front==rear&&flag==false
队列为满时的判断条件：front==rear&&flag==true
3、给一个计数器count
插入一个元素时count++，删除一个元素时count - -
队列为空时的判断条件：count==0
队列为满时的判断条件：count=M 或者（count>0 && rear==front）
综上述三种方法，第三种方法是最简单方便的
二、链式队列
什么是链式队列？
链式队列是队列的一种，与顺序队列的存储方式不一样，跟线性表的单链表一样，只是说只能从头出从尾进而已
链式队列的实现
class LinkQueue{ // 构造函数 offer poll peek empty size private Entry front; // 队头 private Entry rear; private int count; // 记录链表节点的个数 public LinkQueue(){ front= new Entry<>(null, null); } public void offer(T val) { Entry node = front; while(node.next != null){ node = node.next; } node.next = new Entry<>(val, null); count++; } public T poll() { if(empty()) return null; T val = front.next.data; front.next = front.next.next; count--; return val; } public T peek() { if(empty()) return null; return front.next.data; } public boolean empty(){ return front.next == null; } public int size(){ return this.count; } static class Entry { T data; Entry next; public Entry(T data, Entry next) { this.data = data; this.next = next; } } } public class LinkQueueTest { public static void main(String[] args) { LinkQueue ls = new LinkQueue<>(); ls.offer(1); ls.offer(2); ls.offer(3); ls.offer(4); System.out.println(ls.peek()); System.out.println(ls.size()); while(!ls.empty()){ System.out.print(ls.poll() + " "); } System.out.println(); } }
双端队列（Deque）
什么是双端队列？
双端队列又名double ended queue，简称deque，双端队列没有队列和栈这样的限制级，它允许两端进行入队和出队操作，也就是说元素可以从队头出队和入队，也可以从队尾出队和入队。
双端队列的实现
import java.util.List; // 模拟实现队列---底层使用双向链表---在集合框架中Queue是一个接口---底层使用的是LinkedList public class QueueJava中Queue和Deque 1.Deque是Queue的子接口；{ // 双向链表节点 public static class ListNode { ListNode next; ListNode prev; E value; ListNode(E value){ this.value = value; } } ListNode first; // 队头 ListNode last; // 队尾 int size = 0; // 入队列---向双向链表位置插入新节点 public void offer(E e){ ListNode newNode = new ListNode<>(e); if(first == null){ first = newNode; // last = newNode; }else{ last.next = newNode; newNode.prev = last; // last = newNode; } last = newNode; size++; } // 出队列---将双向链表第一个节点删除掉 public E poll(){ // 1. 队列为空 // 2. 队列中只有一个元素----链表中只有一个节点---直接删除 // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除 E value = null; if(first == null){ return null; }else if(first == last){ last = null; first = null; }else{ value = first.value; first = first.next; first.prev.next = null; first.prev = null; } --size; return value; } // 获取队头元素---获取链表中第一个节点的值域 public E peek(){ if(first == null){ return null; } return first.value; } public int size() { return size; } public boolean isEmpty(){ return first == null;
从源码中可以得知：Queue以及Deque都是继承于Collection，Deque是Queue的子接口。
public interface Deque2.Queue——单端队列；Deque——双端队列；extends Queue {}
从Deque的解释中，我们可以得知：Deque是double ended queue，我将其理解成双端队列，就是可以在首和尾都进行插入或删除元素。
而Queue的解释中，Queue就是简单的FIFO（先进先出）队列。所以在概念上来说，Queue是FIFO的单端队列，Deque是双端队列。
3.Queue常用子类——PriorityQueue；Deque常用子类——LinkedList以及ArrayDeque；Queue有一个直接子类PriorityQueue。
而Deque中直接子类有两个：LinkedList以及ArrayDeque。
PriorityQueue：
从源码中，明显看到PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的，具体请看PriorityQueue的grow方法。
LinkedList以及ArrayDeque：
从官方解释来看，ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。
而我们还能看到，ArrayDeque作为队列时的效率比LinkedList要高。
而在栈的使用场景下，无疑具有尾结点，不需判空的LinkedList更为高效。
其实ArrayDeque和LinkedList都可以作为栈以及队列使用，但是从执行效率来说，ArrayDeque作为队列，以及LinkedList作为栈使用，会是更好的选择。
- PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。
- ArrayDeque可以作为栈或队列使用，但是栈的效率不如LinkedList高，通常作为队列使用。
- LinkedList可以作为栈或队列使用，但是队列的效率不如ArrayQueue高，通常作为栈使用。
在java中，Queue被定义成单端队列使用，Deque被定义成双端队列使用。
而由于双端队列的定义，Deque可以作为栈或者队列使用；
而Queue只能作为队列或者依赖于子类的实现作为堆使用。
方法上的区别如下：
| Queue | Deque |
|---|---|
| add(将指定元素插入此队列尾部，成功返回true;当超出容量时add()会抛出异常 ) | addLast、offerLast(在队列尾部插入元素) |
| offer(将指定元素插入此队列尾部，成功返回true;当超出容量时offer()会返回false) | pollFirst、removeFirst、getFirst、peekFirst(获取头部元素) |
| remove(获取并移除队列的头部元素，队列为空抛出异常) | getLast、peekLast(获取但不移除队列最后一个元素) |
| poll(获取并移除队列的头部元素，队列为空返回null) | pollLast、removeLast(获取并移除双端队列最后一个元素) |
| element(获取但是不移除队列头部元素，队列为空抛出异常) | offerFirst(将指定元素插入队列开头) remove(Object o) 从双端队列中移除第一次出现的指定元素o |
| peek(获取但是不移除队列头部元素，队列为空返回null) | pop(从双端队列表示的堆栈中弹出一个元素) push(将一个元素推入双端队列表示的堆栈，即队列的头部。成功返回true，如果没有可用空间，抛出异常) |
| isEmpty(判断队列是否为空，为空返回true) | isEmpty(判断队列是否为空，为空返回true) |
| size(获取队列元素数量) | size(返回双端队列元素数) |
Deque中红色标记方法均和Queue中方法一一对应；且queue中的方法，deque中均可用。
用栈实现队列使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
下面动画模拟以下队列的执行过程如下：
执行语句：
queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();
在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。
class MyQueue {
Stack stackIn;
Stack stackOut;
public MyQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
}
public void push(int x) {
stackIn.push(x);
}
public int pop() {
dumpstackIn();
return stackOut.pop();
}
public int peek() {
dumpstackIn();
return stackOut.peek();
}
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
//复用方法：如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
private void dumpstackIn(){
if(!stackOut.isEmpty()){
return;
}
while(!stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
}
}
用队列实现栈
刚刚做过用栈实现队列的同学可能依然想着用一个输入队列，一个输出队列，就可以模拟栈的功能，仔细想一下还真不行！
队列模拟栈，其实一个队列就够了，那么我们先说一说两个队列来实现栈的思路。
队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。
所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。
但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用又来备份的！
如下面动画所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
模拟的队列执行语句如下：
queue.push(1); queue.push(2); queue.pop(); // 注意弹出的操作 queue.push(3); queue.push(4); queue.pop(); // 注意弹出的操作 queue.pop(); queue.pop(); queue.empty();
用两个单端队列（两个 Queue）实现方法：
class MyStack {
Queue queue1;// 和栈中保持一样元素的队列
Queue queue2;// 辅助队列
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
queue2.offer(x);
while(!queue1.isEmpty()){
queue2.offer(queue1.poll());
}
queue queueTemp; //将queue1中的元素赋值到queue2中（为了形成先入后出的情形）
queueTemp = queue1;
queue1 = queue2;
queue2 = queueTemp;
}
public int pop() {// 因为queue1中的元素已经和栈中的保持一致，所以这个和下面两个的操作只看queue1即可
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
}
用两个双端队列（两个 Deque）实现方法：
class MyStack {
// Deque接口继承了Queue 接口
// 所以Queue中的 add、poll、peek等效于Deque中的 addLast、pollFirst、peekFirst
Deque que1; // 和栈中保持一样元素的队列
Deque que2; // 辅助队列
public MyStack() {
que1 = new ArrayDeque<>();
que2 = new ArrayDeque<>();
}
public void push(int x) {
que1.addLast(x);//双端队列，将元素插入队列尾部
}
public int pop() {
int size = queq.size();
size--;
while(size-- > 0){
que2.addLast(que1.peekFirst);//获取que1中的元素并加入que2中
que1.pollFirst();//que1中删除获取的队列顶部元素
}
int res = que1.pollFirst();//res获取que1中删除的留下的最后一个元素
// 将 que2 对象的引用赋给了 que1 ，此时 que1，que2 指向同一个队列
que1 = que2;//获取元素后，再将que2中的元素赋值给que1
// 如果直接操作 que2，que1 也会受到影响，所以为 que2 分配一个新的空间
que2 = new ArrayDeque<>();
return res;
}
public int top() {
return que1.peekLast(); //双端队列，获取队列中顶部元素
}
public boolean empty() {
return que1.isEmpty();
}
}
用一个队列实现方法：（一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了）
class MyStack {
Deque que1;
public MyStack() {
que1 = new ArrayDeque<>();
}
public void push(int x) {
que1.addLast(x);
}
public int pop() {
int size = que1.size();
size--;
while(size-- > 0){
que1.addLast(que1.peekFirst());
que1.pollFirst();
}
int res = que1.pollFirst();
return res;
}
public int top() {
return que1.peekLast();
}
public boolean empty() {
return que1.isEmpty();
}
}
相关题目
一、有效的括号
先来分析一下 这里有三种不匹配的情况，
- 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
- 第二种情况，括号没有多余，但是 括号的类型没有匹配上。
- 第三种情况，字符串里右方向的括号多余了，所以不匹配。
我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出 动手之前分析好题目的重要性。
动画如下：
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。
分析完之后，代码其实就比较好写了，
但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
class Solution {
public boolean isValid(String s) {
Deque stack = new LinkedList<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(c == '('){
stack.push(')');
}else if(c == '['){
stack.push(']');
}else if(c == '{'){
stack.push('}');
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
}else if(stack.isEmpty() || stack.peek() != c){
return false;
}else{ //和栈顶元素匹配的右括号，删除
stack.pop();
}
}
// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
return stack.isEmpty();
}
}
二、删除字符串中所有相邻重复项
本题要删除相邻相同元素，其实也是匹配问题，相同左元素相当于左括号，相同右元素就是相当于右括号，匹配上了就删除。
那么再来看一下本题：可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。
如动画所示：
从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以在对字符串进行反转一下，就得到了最终的结果。
class Solution {
public String removeDuplicates(String s) {
Deque stack = new LinkedList<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(stack.isEmpty() || stack.peek() != c){
stack.push(c);
}else{
stack.pop();
}
}
String str = "";
while(!stack.isEmpty()){
str = stack.pop() + str;
}
return str;
}
}
字符串类本身就提供了类似「入栈」和「出栈」的接口，因此我们直接将需要被返回的字符串作为栈即可。
class Solution {
public String removeDuplicates(String s) {
StringBuilder res = new StringBuilder();
int top = -1; //top表示res的长度
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
// 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
if(top >= 0 && res.charAt(top) == c){
res.deleteCharAt(top);
top--;
// 否则，将该字符 入栈，同时top++
}else{
res.append(c);
top++;
}
}
return res.toString();
}
}
三、逆波兰表达式求值
class Solution {
public int evalRPN(String[] tokens) {
Deque stack = new LinkedList<>();
for(String c : tokens){
if("+".equals(c)){ // leetcode 内置jdk的问题，不能使用==判断字符串是否相等
stack.push(stack.pop() + stack.pop());
}else if("-".equals(c)){
stack.push(-stack.pop() + stack.pop());// 注意 - 和/ 需要特殊处理（所有运算都是后一个数对前一个数）
}else if("*".equals(c)){
stack.push(stack.pop() * stack.pop());
}else if("/".equals(c)){
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
}else{
stack.push(Integer.valueOf(c));
}
}
return stack.pop();
}
}
四、滑动窗口最大值（单调队列）
思路
这是使用单调队列的经典题目。
暴力方法，遍历一遍的过程中每次从窗口中在找到最大的数值，这样很明显是$O(n × k)$的算法。
有的同学可能会想用一个大顶堆（优先级队列）来存放这个窗口里的k个数字，这样就可以知道最大的最大值是多少了， 但是问题是这个窗口是移动的，而大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。
此时我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
这个队列应该长这个样子：
class MyQueue {
public:
void pop(int value) {
}
void push(int value) {
}
int front() {
return que.front();
}
};
每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值。
这么个队列香不香，要是有现成的这种数据结构是不是更香了！
可惜了，没有！ 我们需要自己实现这么个队列。
然后在分析一下，队列里的元素一定是要排序的，而且要最大值放在出队口，要不然怎么知道最大值呢。
但如果把窗口里的元素都放进队列里，窗口移动的时候，队列需要弹出元素。
那么问题来了，已经排序之后的队列 怎么能把窗口要移除的元素（这个元素可不一定是最大值）弹出呢。
其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队里里的元素数值是由大到小的。
那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列（单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列）。没有直接支持单调队列，需要我们自己来一个单调队列
不要以为实现的单调队列就是 对窗口里面的数进行排序，如果排序的话，那和优先级队列又有什么区别了呢。
来看一下单调队列如何维护队列里的元素。
动画如下：
对于窗口里的元素{2, 3, 5, 1 ,4}，单调队列里只维护{5, 4} 就够了，保持单调队列里单调递减，此时队列出口元素就是窗口里最大元素。
此时大家应该怀疑单调队列里维护着{5, 4} 怎么配合窗口经行滑动呢？
设计单调队列的时候，pop，和push操作要保持如下规则：
- pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
- push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。
为了更直观的感受到单调队列的工作过程，以题目示例为例，输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3，动画如下：
那么我们用什么数据结构来实现这个单调队列呢？
使用deque最为合适，可以在头尾入队和出队元素。
class Solution{
public int[] maxSlidingWindow(int[] nums, int k) {
Deque queue = new LinkedList<>(); //存放数组元素下标
int[] res = new int[nums.length - k + 1];
int resIndex = 0;
for(int i = 0; i < nums.length; i++){
//1.头：清理超期元素（清理i-k位置的元素）每次滑动窗口只能有3个值
if(!queue.isEmpty() && queue.peek() == i - k){
queue.poll();
}
//2.尾：维护单调递减队列（清除队列内<新入队的元素）
while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]){
queue.removeLast();
}
//3.尾：新元素入队
queue.add(i);
//4.头：获取滑动窗口最大值（返回头部元素，i>=k-1时）
if(i >= k - 1){ //因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
res[resIndex++] = nums[queue.peek()];
}
}
return res;
}
}
