认识栈与队列

栈是一种遵循先入后出逻辑的线性数据结构。
在栈中，堆叠元素的顶部称为栈顶，底部称为栈底。将元素添加到栈顶的操作叫做入栈，删除栈顶元素的操作叫做出栈。

/* 初始化栈 */
Stack<Integer> stack = new Stack<>();
/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);
/* 访问栈顶元素 */
int peek = stack.peek();
/* 元素出栈 */
int pop = stack.pop();
/* 获取栈的长度 */
int size = stack.size();
/* 判断是否为空 */
boolean isEmpty = stack.isEmpty();

队列是一种遵循先入后出规则的线性数据结构。队列头部称为队首，尾部称为队尾，将元素加入队尾的操作叫做入队，删除队首元素的操作叫做出队。

/* 初始化队列 */
Queue<Integer> queue = new LinkedList<>();
/* 元素入队 */
queue.offer(1);
queue.offer(3);
queue.offer(2);
queue.offer(5);
queue.offer(4);
/* 访问队首元素 */
int peek = queue.peek();
/* 元素出队 */
int pop = queue.poll();
/* 获取队列的长度 */
int size = queue.size();
/* 判断队列是否为空 */
boolean isEmpty = queue.isEmpty();

栈和队列的实现，既可以采用基于链表的实现，也可以采用基于数组的实现。

用栈实现队列

力扣题目链接
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作
每次 pop 或 peek 时，若输出栈为空，则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;
    public MyQueue() {
        inStack = new ArrayDeque<Integer>();
        outStack = new ArrayDeque<Integer>();
    }
    public void push(int x) {
        inStack.push(x);
    }
    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }
    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

滑动窗口最大值

力扣题目链接
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

设置双端队列存储最大值，队列降序排列，一轮遍历，先把窗口塞满，然后这时就可以返回最大值（队头）了，但返回前要做两件事，首先，要加入数组当前下标到队尾，并保证是单调的，其次，如果队头这是已经到了窗口左边，就移除队头
遍历的 i 是尾部数字的索引，i + 1 - k 是头部数字的索引，若队列头部的索引已经比 i + 1 - k 小，则 poll

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
            if (queue.peek() < i + 1 - k) {
                queue.poll();
            }
            if (i + 1 >= k) {
                res[i + 1 - k] = nums[queue.peek()];
            }
        }
        return res;
    }
}