两队列模拟插入排序 题解 2328:谁考了第k名

解题思路: 每次都排序，没意思。整点新玩意，有插入排序那个意思。
                Deque双端队列，既有队列的特性，又有栈的特性。

                res和tempDeque保存的数据始终有序，从高到底。

                每次从res队尾插一个元素，就与res中的队尾比较，

                    1.如果插入元素比队尾元素小，直接插入

                    2.如果插入元素比队尾元素大，将res队尾元素尾插到tempDeque中，继续走1.

                    3.插入完该元素后，将tempDeque中的元素从对头到队尾依次尾插到res中，res依然有序

注意事项:

参考代码:

import java.util.*;

/**
 * @author fzy
 * @create 2021/10/9 15:28
 **/
public class t2328 {
    static class Node{
        Integer no;
        Double score;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();//n个学生
        int k = sc.nextInt();//第k名

        Deque<Node> res=new LinkedList<Node>();
        Deque<Node> tempDeque=new LinkedList<Node>();
        for (int i=0;i<n;i++){
            Node node = new Node();
            node.no=sc.nextInt();//学号
            node.score=sc.nextDouble();//成绩

            if(res.isEmpty()){
                res.offerLast(node);//队尾加入
            }else{
                while (true){
                    //查看队尾元素 如果队列无元素 返回null
                    Node lastNode = res.peekLast();
                    if(lastNode !=null && node.score>lastNode.score){
                        tempDeque.offerLast(res.pollLast());//弹出队尾元素 将其加入临时队列尾
                    }else{
                        res.offerLast(node);//队空时或当前插入结点小于res中尾结点时 直接加入尾部
                        break;
                    }
                }
                while (!tempDeque.isEmpty()){
                    res.offerLast(tempDeque.pollLast());
                }
            }
        }
        int count=0;
        for (Node re : res) {
            if(count==k-1){
                System.out.println(re.no+" "+re.score);
                break;
            }
            count++;
        }


    }
}