class MyQueue {
    //用栈实现队列需要两个栈
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;
    //初始化队列——即用两个栈实现一个队列
    public MyQueue() {
        //入队往入队栈stackIn中入，出队从出队栈stackOut中出
        stackIn=new Stack<>();
        stackOut=new Stack<>();
    }
    public void push(int x) {
        stackIn.push(x);
    }
    //在出队栈中出栈实现出队列
    public int pop() {
        //出队列时，需要先从出栈队出元素，出栈队空了再把入队栈中【所有元素】按原有顺序(即按入队栈的出栈顺序push进出队栈)【移动】到出队栈中
        inToOut();
        return stackOut.pop();
    }
    public int peek() {
        //获取队列开头的元素等价于获取出队栈栈顶元素
        inToOut();
        return stackOut.peek();
    }
    public boolean empty() {
        //入队栈和出队栈都为空，则队列为空
        return stackIn.empty()&&stackOut.empty();
    }
        //★
    public void inToOut(){
        //为保证inToOut时元素的相对顺序，出队栈为空时才能往里放元素
        if(!stackOut.empty()){
            return;
        }
        //，同时要将此时入队栈中所有元素都放到出队栈中
        while(!stackIn.empty()){
            stackOut.push(stackIn.pop());
        }
    }
}

class MyStack {
    //一个双向队列模拟栈，First端是栈顶，Last端是栈底
    Deque<Integer> queue;
    public MyStack() {
        queue=new ArrayDeque<>();
    }
    public void push(int x) {
        queue.offerFirst(x);
    }
    public int pop() {
        return queue.pollFirst();
    }
    public int top() {
        return queue.getFirst();
    }
    public boolean empty() {
        return queue.isEmpty();
    }
}

class MyStack {
    Queue<Integer> queue;
    public MyStack() {
        queue=new LinkedList<>();
    }
    public void push(int x) {
        //每入栈一个元素x，就将队列中元素重新排列，将x放到队头(x原来在队尾，这样方便出栈时直接出队以及获取栈顶元素直接获取队头元素)
        queue.offer(x);
        int len=queue.size();
        while(len>1){
            queue.offer(queue.poll());
            len--;
        }
    }
    public int pop() {
        return queue.poll();
    }
    public int top() {
        return queue.peek();
    }
    public boolean empty() {
        return queue.isEmpty();
    }
}

public boolean isValid(String s) {
    char[] str=s.toCharArray();
    Stack<Character> stack=new Stack<>();
    //遍历字符串
    for(int i=0;i<str.length;i++){
        //如果是左括号，就将对应右括号入栈
        if(str[i]=='('){
            stack.push(')');
        }else if(str[i]=='{'){
            stack.push('}');
        }else if(str[i]=='['){
            stack.push(']');
            //情况③：如果遍历字符串时栈为空了，说明右括号多了，返回false
            //情况②：如果遍历得到的右括号与栈顶元素不同，说明左右括号不匹配，返回false
        }else if(stack.empty() || str[i]!=stack.peek()){
            return false;
        }else{//如果是右括号，且左右匹配，就将栈顶元素出栈
            stack.pop();
        }
    }
    //情况①：遍历完字符串如果栈不为空，说明左括号多了，返回false;为空，返回true
    return stack.empty();
}

public String removeDuplicates(String s) {
    char[] arr=s.toCharArray();
    Deque<Character> deque=new ArrayDeque<>();
    //遍历字符数组，如果字符与栈顶字符相同，则出栈；不同则进栈。
    for(int i=0;i<arr.length;i++){
        if(!deque.isEmpty()&&arr[i]==deque.peek()){
            //删除相邻重复项
            deque.pop();
        }else{
            deque.push(arr[i]);
        }
    }
    StringBuilder sb=new StringBuilder();
        //遍历完最后栈内元素就是删除相邻重复项后的字符串。
    while(!deque.isEmpty()){
        sb.append(deque.pop());
    }
    return sb.reverse().toString();
}

public String removeDuplicates(String s) {
    char[] arr=s.toCharArray();
    //★用结果字符串模拟栈，字符串左边是栈底，右边是栈口，即字符串最后一个元素是栈顶元素
    StringBuilder rslt=new StringBuilder();
    //top一直指向栈顶元素(字符串最后一个元素)，规定栈底下标从0开始(即字符串开头)，因为栈初始为空，所top要初始化为-1表示栈(字符串)空
    int top=-1;
    //遍历字符数组
    for(int i=0;i<arr.length;i++){
        //如果栈不为空且字符与栈顶字符rslt.charAt(top)相同，则出栈(即从rslt中删除top所指元素)
        if(top>=0&&arr[i]==rslt.charAt(top)){
            rslt.deleteCharAt(top);
            top--;
        }else{//栈为空或字符与栈顶字符不同，则进栈。
            rslt.append(arr[i]);
            top++;
        }
    }
    //遍历完后栈内剩的就是结果字符串。
    return rslt.toString();
}

public String removeDuplicates(String s) {
    char[] ch = s.toCharArray();
    int fast = 0;
    int slow = 0;
    while(fast < s.length()){
        // ★直接用fast指针覆盖slow指针的值
        ch[slow] = ch[fast];
        // 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
        if(slow > 0 && ch[slow] == ch[slow - 1]){
            slow--;
        }else{
            slow++;
        }
        fast++;
    }
    return new String(ch,0,slow);
}

public int evalRPN(String[] tokens) {
    //按从左到右的顺序压入栈中，并且按照遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果再入栈的原则来进行处理
    Deque<Integer> deque=new ArrayDeque<>();
    for(int i=0;i<tokens.length;i++){
        if(tokens[i].equals("+")){
            deque.push(deque.pop()+deque.pop());
        }else if(tokens[i].equals("-")){
            int n1=deque.pop();
            int n2=deque.pop();
            deque.push(n2-n1);//减法的特殊处理
        }else if(tokens[i].equals("*")){
            deque.push(deque.pop()*deque.pop());
        }else if(tokens[i].equals("/")){
            int n1=deque.pop();
            int n2=deque.pop();
            deque.push(n2/n1);//除法的特殊处理
        }else{
            deque.push(Integer.valueOf(tokens[i]));
        }
    }
    //遍历完字符串后栈顶元素(其实也只有栈顶一个元素)就是最终结果
    return deque.pop();
}

我们需要一个队列，随着窗口的后移一位，队列一进一出，每次移动之后，由队列告诉我们此时窗口的最大值是什么。那么这个队列应该有三个方法：每次窗口移动，调用pop方法移除窗口第一个元素，调用push方法将新元素加到窗口，调用front方法获取当前窗口最大值。

可惜的是没有现成的这种数据结构供我们使用，那么我们就需要自己来实现这种队列。
        我们先来分析一下这个队列，因为要获取窗口的最大值，那么我们可以让这个队列始终保持一个单调性，让最大值一直在队头。维护这个队列的单调性不是将所有的元素进行一个排序操作，而是应该在一进一出时来维护单调性。这种队列我们称之为单调队列。那么该如何在一进一出时维护其单调性呢？
         ★在自己设计单调队列时，pop和push操作要保持如下规则：
                · pop(value)：★如果窗口要移除的元素value等于单调队列的队头元素，那么队列就弹出元素；否则不用任何操作(其实是在push时已经移除了)。
                · push(value)：如果要加入的元素value大于队尾入口的元素，那么就将队尾入口的元素弹出，直到value小于等于队尾入口元素为止。(即★向队列中加入元素x时，将x前面比x小的所有元素移除后再把x加进去)
        保持以上规则(动画演示如下图)，每次窗口移动的时候，只要调用front()就可以返回当前窗口的最大值。

我们再以题目示例为例演示一下单调队列的规则，输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3，动画如下：
        
那么我们该用什么数据结构来实现单调队列呢？
        显然单调队列在队尾既要加入元素，又要移除元素，所以用双向队列Deque实现最合适。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //用来存放每次滑动窗口的最大值
        int[] rslt=new int[nums.length-k+1];
        //初始化单调队列
        MyQueue myQueue=new MyQueue();
        //先将第一个窗口的数字都放入单调队列
        for(int i=0;i<k;i++){
            myQueue.push(nums[i]);
        }
        int rsltIdx=0;
        //把第一个窗口的最大值放入rslt中
        rslt[rsltIdx++]=myQueue.getMax();
        //遍历nums，后移窗口
        for(int i=k;i<nums.length;i++){
            //把窗口第一个数字移除
            myQueue.poll(nums[i-k]);
            //把当前数字加入窗口
            myQueue.push(nums[i]);
            //获取当前窗口最大值
            rslt[rsltIdx++]=myQueue.getMax();
        }
        return rslt;
    }
}
//使用Deque模拟单调队列MyQueue
class MyQueue{
    Deque<Integer> deque=new ArrayDeque<>();
    //在单调队列中始终让当前窗口的最大值放在队头(这里以First作为队头)
    //★将窗口第一个数字x移除
    public void poll(int x){
        //★当要溢出的第一个数字x等于单调队列的队头数字时，说明要进行真正的移除操作
        if(!deque.isEmpty() && x==deque.peekFirst()){
            deque.pollFirst();
        }
        //▲当x不等于队头数字时，在往队列中加数字时已经移除了(因为要始终维护队头元素最大)
    }
    //将当前遍历到的数字x加入队列(注意始终保持队列的单调性)
    public void push(int x){
        //因为要始终维护队头元素最大，所以如果要加入队列的x比队尾数字大，就将队尾数字移除
                //★这里不需要把移除了的队尾数字重新入队了，因为题目要求找窗口的最大值，被移除了说明一定不是最大值了，直接丢弃即可(其实这里做了上面的▲的操作)
        while(!deque.isEmpty() && x>deque.peekLast()){
            deque.pollLast();
        }
        //将x加入队列
        deque.offerLast(x);
    }
    public int getMax(){
        //队头数字始终是窗口的最大值
        return deque.peekFirst();
    }
}

public int[] topKFrequent(int[] nums, int k) {
    int[] rslt=new int[k];
    //key-数组中的数字，value-数字出现的次数
    Map<Integer,Integer> map=new HashMap<>();
    for(int i:nums){
        //★getOrDefault(Object key, V defaultValue)：获取key对应的值，如果key不存在，则返回defaultValue
        //使用getOrDefault就不用判断key是否在map里了:如果i不在map里，返回默认给的0，然后+1，即map.put(i,1);
        map.put(i,map.getOrDefault(i,0)+1);
    }
    //使用优先队列实现小顶堆(小的靠近队头)
    //在优先队列中存储二元数组(key,value)：key-数组中的数字，value-数字出现的次数
    PriorityQueue<int[]> pq=new PriorityQueue<>((nums1,nums2)->nums1[1]-nums2[1]);
    for(Map.Entry<Integer,Integer> entry:map.entrySet()){
        int key=entry.getKey();
        int value=entry.getValue();
        //因为小顶堆只需要维持k个元素有序，所以当堆内元素个数小于k时，直接加进去
        if(pq.size()<k){
            pq.add(new int[]{key,value});
        }else{
            //维持k个元素有序
            //当前数字出现的次数大于小顶堆堆顶数字出现的次数
            if(value>pq.peek()[1]){
                //将堆顶二元数组弹出，将当前数字和次数加进来
                pq.poll();
                pq.add(new int[]{key,value});
            }
        }
    }
    //依次弹出小顶堆
    for(int i=0;i<k;i++){
        rslt[i] = pq.poll()[0];
    }
    return rslt;
}

public int[] topKFrequent1(int[] nums, int k) {
    Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
    for(int num:nums){
        map.put(num,map.getOrDefault(num,0)+1);
    }
    //出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
    PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);
    for(Map.Entry<Integer,Integer> entry:map.entrySet()){
               //大顶堆需要对所有元素进行排序
        pq.add(new int[]{entry.getKey(),entry.getValue()});
    }
    int[] ans = new int[k];
    for(int i=0;i<k;i++){
               //依次从队头弹出k个,就是出现频率前k高的元素
        ans[i] = pq.poll()[0];
    }
    return ans;
}