#PriorityQueue of Java queue series

In the previous article, I used a diagram to sort out the relationship between various queues in Java. Here is the PriorityQueue. PriorityQueue is located in the Java util package. The word priority in the first half of its name means priority. In fact, this queue has "priority". Since it has the characteristics of priority, there must be a "rule" to sort before and after. Therefore, the class it accepts needs to implement the comparable interface.

API

1. Constructor

PriorityQueue()
PriorityQueue(Collection<? extends E> c)
PriorityQueue(int initialCapacity)
PriorityQueue(int initialCapacity,Comparator<? super E> comparator)
PriorityQueue(PriorityQueue<? extends E> c)
PriorityQueue(SortedSet<? extends E> c)

2. Common function

Usage example

As mentioned above, there is a priority, so here is an example. When I was in high school, I was divided into classes once a month. The teacher would give each student priority to choose his favorite seat according to the results of this month's test. All the students here are a queue; Every time a person is called in to choose a seat, this is the right operation; From top to bottom, this is the priority strategy.

public class PriorityQueueTest {
	public static void main(String[] args) {
        		
		final PriorityQueue<Student> queue=new PriorityQueue<>();

		Student p1=new Student(95,"张三");
		Student p2=new Student(89,"李四");
		Student p3=new Student(89,"李四");
		Student p4=new Student(67,"王五");
		Student p5=new Student(92,"赵六");
		queue.add(p1);
		queue.add(p2);
		queue.add(p3);//add 和offer效果一样。
		queue.offer(p4);//add 方法实现，其实就是调用了offer
		queue.offer(p5)

		for (Student Student : queue) {
			System.out.println(Student.toString());
		}
		
		System.out.println("---------------------");
		while(!queue.isEmpty()){
			System.out.println(queue.poll());
		} 	    
	}

}
class Student implements Comparable{
	private int score;
	private String name;
	
	public Student(int age,String name){
		this.score=age;
		this.name=name;
	}
	public int getscore() {
		return score;
	}
	public void setscore(int score) {
		this.score = score;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public String toString(){
		return "姓名："+name+"-"+score+"分";
	}

	@Override
	public int compareTo(Object o) {
		Student current=(Student)o;
		if(current.getscore()>this.score){
			return 1;
		}else if(current.getscore()==this.score){
			return 0;
		}
		return -1;
	}
}

It can be seen from the output of the first part that students do not join the team in order, but leave the team in order when the poll comes out. Here, the effect of giving priority to seats with high scores is indeed realized. The poll method always returns the highest score among the remaining students in the queue.

Security

Looking at the source code of the PriorityQueue class, you will find that the addition operation is not an atomic operation. No locks were used. Then, if it is in a multithreaded environment, it must be unsafe. The following is an example. Open multiple threads and call the same method to add elements to the queue. Then output the results.

public class PriorityQueueTest {

	static final PriorityQueue<Integer> queue=new PriorityQueue<>();
	/**
	 * 向队列中插入元素
	 * @param number
	 */
	public  void add(int number){
		if(!queue.contains(number)){
			System.out.println(Thread.currentThread()+"："+number);
			queue.add(number);
		}
	}	

public static void main(String[] args) throws InterruptedException {
	final PriorityQueueTest qt=new PriorityQueuetest();
		final Random r=new Random();
		Thread t1=new Thread(){
			public void run(){
				System.out.println("t1开始运行...");
				for(int i=0;i<10;i++){
					qt.add(r.nextInt(10));
				}
			}
		};
		Thread t2=new Thread(){
			public void run(){
				System.out.println("t2开始运行...");
				for(int i=0;i<10;i++){
					qt.add(r.nextInt(10));
				}
			}
		};
		Thread t3=new Thread(){
			public void run(){
				System.out.println("t3开始运行...");
				for(int i=0;i<10;i++){
					qt.add(r.nextInt(10));
				}
			}
		};
		t1.start();
		t2.start();
		t3.start();
		t1.join();
		t2.join();
		t3.join();
		System.out.println("------ 运行结果 ---------");
		while(!queue.isEmpty()){
			System.out.println(queue.poll());
		}
	}
}

In the result, we can see that there are two 1's and two 9's This is not in line with our expectations. We expect not contains to be inserted. Now there are duplicates. The above example only needs to lock the add method to achieve the desired effect. Therefore, PriorityQueue is non thread safe. [1]: http://www.cnblogs.com/demingblog/p/6474865.html

Working for 6 years and unemployed for 19 days, java8 series - how to use java8 stream API to find your favorite girlfriend java8 series - how to use java8 stream API for data extraction and collection

How does spring start? This paper describes how spring MVC works during the startup process, the working principle of spring MVC and spring exception handling in combination with the spring source code. Analyze 400 exception handling process and solutions combined with spring source code

How to find the implementation class of mybatis mapper interface - source code analysis using netty to implement HTTP server netty to implement heartbeat mechanism netty series