PriorityQueue / Deque

*PriorityQueue

  Queue 인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이 있다. null은 저장할 수 없고 NullPointerException이 발생한다. 저장공간으로 배열을 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장한다. (힙은 이진트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다.)

 

import java.util.*;

public class PriorityQueueExam {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Queue<String> pq = new PriorityQueue<String>();
		  
        // Adding items to the pQueue using add() 
		pq.add("d"); 
		pq.add("c"); 
		pq.add("a");
		pq.add("b");
		
		for(String val : pq) {
			System.out.println(val); // a b c d
		}
	}

}

 

 백준 4485 / 녹색 옷 입은 애가 젤다지?

  BFS와 다익스트라를 이용해 최단거리를 찾는다.

 

  배열의 최솟값을 업데이트 해주기 위해서 전체 배열 값을 Integer.MAX_VALUE로 정하는 것은 하나의 팁이다. 

 

Queue vs PriorityQueue

  위에가 Queue, 아래가 PriorityQueue사용 했을 때 메모리와 시간이다. PriorityQueue를 사용했을 때 정렬의 효과 때문에 훨씬 시간을 단축시켰다. 

 

import java.util.*;

public class DequeExam {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Deque<String> dq = new ArrayDeque<String>();
		  
        // Adding items to the pQueue using add() 
		dq.addFirst("qwer"); //[qwer]
        dq.addLast("zxcv"); //[qwer,zxcv]
		dq.removeFirst();  //[zxcv]
		dq.addLast("abc"); //[zxcv, abc]
		dq.removeLast(); //[zxcv]
		dq.addFirst("abc"); //[abc,zxcv]
		
		for(String val : dq) {
			System.out.println(val);
            
            
            
            
            
            
		}
	}

}

*Deque

  Queue의 변형으로, 한쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Deque은 양쪽 끝에 추가/삭제가 가능하다. Deque의 조상은 Queue이며, 구현체는 ArrayDeque와 LinkedDeque 등이 있다.

사진 출처 : https://www.javatpoint.com/post/cpp-deque

 

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()
peekLast()	-	peek()

  addFirst(), addLast(), removeFirst(), removeLast(), getFirst(), getLast() 가 직관적으로 이해가 더 쉽다. 이 메소드들은 예외를 발생시킨다는 것 빼고는 표에 있는 메소드들과 차이가 없다.

 

백준 11003 / 최솟값 찾기

슬라이딩 윈도우 + deque로 문제를 해결한다.

슬라이딩 윈도우의 성질 상 맨 앞과 맨 뒤의 요소를 넣고 빼는 반복작업이 많은데 deque의  addFirst(), addLast(), removeFirst(), removeLast() 메소드들을 잘 활용하여 쉽게 조작 할 수 있도록 한다.