class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    private int front; //记录队首元素

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if(stack1.isEmpty()){
            front = x;
        }
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(empty()){
            return -1;
        }
        if(stack2.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            return front;
        }
        return stack2.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return (stack1.isEmpty()) && (stack2.isEmpty());
    }
}

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue1.offer(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if(empty()){
            return -1;
        }
        while (queue1.size()>1){
            queue2.offer(queue1.poll());
        }
        //交换着两个队列
        int num = queue1.poll();
        Queue<Integer> tmp = queue1;
        queue1 = queue2;
        queue2 = tmp;
        return num;
    }

    /** Get the top element. */
    public int top() {
        while (queue1.size()>1){
            queue2.offer(queue1.poll());
        }
        return queue1.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return (queue1.isEmpty()) && (queue2.isEmpty());
    }
}

//统计字符出现的次数
private int[] freq = new int[256];
//队列中只存储出现一次的字符，并且出队顺序就是入队顺序
private Queue<Character> queue = new LinkedList<>();
//Insert one char from stringstream
public void Insert(char ch) {
    freq[ch]++;
    queue.offer(ch);

    //队列中只存储出现一次的字符
    while (!queue.isEmpty() && freq[queue.peek()]>1){
        queue.poll();
    }
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
    return queue.isEmpty()? '#':queue.peek();
}

public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer> res=new ArrayList<>();

    //统计数组中元素出现次数
    HashMap<Integer,Integer> records=new HashMap<>();
    for(int num:nums){
        int freq=records.getOrDefault(num,0);
        records.put(num,++freq);
    }

    PriorityQueue<EleFreq> queue=new PriorityQueue<>(new Comparator<EleFreq>() {
        @Override
        public int compare(EleFreq o1, EleFreq o2) {
            int num=o1.freq-o2.freq;
            int num2=(num==0?o2.num-o1.num:num);
            return num2;
        }
    });

    for(Integer num : records.keySet()){
        int freq=records.get(num);
        queue.add(new EleFreq(num,freq));
        if(queue.size()==k+1){
            queue.poll();
        }
    }

    while(!queue.isEmpty()){
        res.add(queue.poll().num);
    }
    return res;
}

private class EleFreq{
    int num;
    int freq;
    public EleFreq(int num,int freq){
        this.num=num;
        this.freq=freq;
    }
}