Queue interface List란? (Deque, LinkedList, ArrayDeque, PriorityQueue)

Queue 큐 interface List란?

- Queue interface는 선형 자료구조로 주로 순서가 있는 데이터를 기반으로 선입선출(FIFO)을 위해 만들어진 인터페이스이다.

- 제일 앞쪽의 데이터 위치를 head라고 하고, 가장 뒤에 있는 것을 tail 이라고 한다.

- Queue는 단방향 삽입삭제가 가능한 반면, Queue를 상속하고 있는 Deque은 양방향이 가능하다. (큐에서 확장)- 

- Deque은 카드를 생각하면 좋다. 중간에서 카드를 뺄 수는 없지만, 맨 아래, 맨 위에서 접근이 모두 가능하다.

 

 

Queue Deque interface 를 구현하는 클래스

1. LinkedList

2. ArrayDeque

3. PriorityQueue

 

Queue / Deque interface에 선언된 대표적인 메소드

- 큐와 덱은 거의 동일하지만, 덱이 양방향에서 데이터 삽입 삭제가 되기 때문에 메소드가 그 만큼 늘어났다.

 

LinkedList

- LinkedList는 리스트를 구현하기도 하지만, Deque을 구현하기도 한다. Deque은 또 Queue를 상속받는다.

- 그래서 LinkedList는 리스트, 덱, 큐 세 가지를 구현할 수 있다.

 

Public class LinkedList<E>
	extends AbstarctSequentialList<E>
    implemets List<E>, Deque<E>, Cloneable, java.io.Serializable
{

- ArryaList와 LinkedList의 차이점은 object[] 배열로 관리하느냐, Node라는 객체를 연결하여 관리하느냐 차이다.

https://mrlazydev.tistory.com/entry/%EC%9E%90%EB%B0%94-%EC%BB%AC%EB%A0%89%EC%85%98-%ED%94%84%EB%A0%88%EC%9E%84%EC%9B%8C%ED%81%AC

 

- 마찬가지로 Deque와 Queue를 LinkedList처럼 Node 객체로 연결해서 관리하길 바라면, LinkedList를 사용하면 되는 것이다.

- 반대로 ArrayList처럼 Object[] 배열로 구현되어 있는 것은 ArrayDeque이다.

- 일반적인 Queue를 사용하기를 원한다면, 보통 LinkedList를 사용하면 된다.

Queue<T> queue = new LinkedList<>();
Deque<T> queue = new LinkedList<>();

 

PriorityQueue

- priorityQueue는 우선순위 큐라고 해서, 기본적으로 선입선출이라는 형태로 짜여진 Queue와는 조금 다르게, '데이터 우선순위'에 기반하여 우선순위가 높은 데이터가 나온다.

- 따로 정렬방식을 지정하지 않으면 낮은 숫자가 높은 우선순위를 갖는다.

- 주어진 데이터 중, 최댓값과 최솟값을 가지고 오는 데 유용하지만, 사용자가 정의한 객체를 타입으로 한다면 Comparator나 Comparable을 통해 정렬 방식을 구현해주어야 한다.