点击打开链接

Problem Description

Input

Output

Sample Input

GET
PUT msg1 10 5
PUT msg2 10 4
GET
GET
GET

Sample Output

EMPTY QUEUE!
msg2 10
msg1 10
EMPTY QUEUE!

题意：

依据操作指令进行操作，也就是出队，还是入队。而在出队时。要注意。保证优先级低的先出来，要是优先级一样的话。就先入队的先出来。从题目就非常easy看出要用优先队列做，恰好java包中有个PriorityQueue类，就是现成的优先队列。

解题过程：首先依据题意，能够建一个Message类，这里面包含mesg的一些信息，主要包含，优先级和进队的序列号（这个序列号必需要，也就是第几个进队的，后面就知道了）。然后依据指令一步一步的操作，就能够得到答案。

注意：

1、PriorityQueue类与普通队列最基本的差别就是多了个比較器。普通情况下，都是自己通过实现Comparator接口写一个比較器，在new 优先队列时将这个比較器丢进去就ok了，

构造方法中就有 PriorityQueue(int initialCapacity, Comparator<?

super E> comparator) 

           使用指定的初始容量创建一个 PriorityQueue，并依据指定的比較器对元素进行排序。

2、尽管优先队列在放入元素时，会通过当中的比較器进行比較后，放到对应的位置。可是至于它内部是怎么比較的，怎么放的。我还没去深究，可是在这里我知道。尽管题目是说先通过优先级进行存放，然后通过进队顺序存放，听起来仅仅要考虑

优先级排序即可了。主观上就会以为仅仅要优先级同样时，也就是compare返回0。它就会放在同一优先级。但先进来的元素后面。事实上不然，并非这种，这里必需要通过进队的序列号来比較后才干达到想要的目的。

代码实现：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class P1509 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		PriorityQueue<Message> priorityQue=new PriorityQueue<Message>(6000,new MesCmp());//优先队列
		Message messg;//messg类
		int count=0;
		while(sc.hasNext()){
			String operate=sc.next();
			if(operate.charAt(0)==‘G‘){//出队
				if(priorityQue.isEmpty()){
					System.out.println("EMPTY QUEUE!");
				}else{
					System.out.println(priorityQue.poll());
				}
			}else{//入队
				messg=new Message(sc.next(), sc.nextInt(), sc.nextInt(),count++);
				priorityQue.add(messg);
			}
		}
	}

}

class Message{
	String name;
	int value;
	int priority;
	int id;
	public Message(String name, int value, int priority,int id) {
		this.name = name;
		this.value = http://www.mamicode.com/value;" " + value;
	}
}
class MesCmp implements Comparator<Message>{

	public int compare(Message m1, Message m2) {
		if(m1.priority<m2.priority){
			return -1;
		}else if(m1.priority>m2.priority){
			return 1;
		}else{
			//这里假设没有id的比較，那顺序就会出错
			if(m1.id<m2.id){
				return -1;
			}else if(m1.id>m2.id){
				return 1;
			}else{
				return 0;
			}
		}
	}
}