[JAVA]큐(Queue)&PriorityQueue 와 연결리스트(LinkedList) 란?

프로그래머스 문제를 풀면서 큐에 대해 다시 한번 정리를 하면 좋겠다고 생각해서 글로 남겨보려고 한다.

 

 

 

먼저 자료구조의 종류를 살펴보면 아래의 사진처럼 종류가 다양하다.

 

그중에서도 Queue에 관해 알아보려고 한다.

 

|  큐(Queue)

 

Java에서 제공하고 있는 Queue는 interface 형태로 연결 리스트(LinkedList) 를 통해서 생성합니다.

그렇기 때문에 사이즈가 가변적이고, 쉽게 늘어납니다.

Data 구조의 양쪽 단에서만 저장/접근 할 수 있는 컬렉션입니다.

 

 

특징

-선입선출 방식인 FIFO(First In First Out)으로 먼저 들어온 데이터가 먼저 출력되는 자료구조로 쓰는 것이 가장 큰 특징입니다.

 

 

생성 방법

Queue q  = new LinkedList();

 

Queue의 메소드 종류

 

메소드설명

메소드	설명
boolean add(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입함. 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킴.
E element()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.
boolean offer(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입함.
E peek()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함. 만약 큐가 비어있으면 null을 반환함.
E poll()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함. 만약 큐가 비어있으면 null을 반환함.
E remove()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거함.

 

 

| 연결 리스트 (LinkedList) 

 

-자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 구조이다.

 

특징

- 노드의 삽입,삭제 작업이 용이하다.

- 기억 공간이 연속적으로 놓여 있지 않아도 저장이 가능하다.

- 연결이 위한 포인터(링크) 부분이 필요하기 때문에 순차 리스트에 비해 기억공간 이용 효율이 좋지 않다.

- 연결을 위한 포인터를 찾는 시간이 필요하기  때문에 접근 속도가 느리다.

- 중간 노드가 연결이 끊기면 그 다음 노드를 찾기 힘들다.

- 희소 행렬을 링크드 리스트로 표현, 기억장소가 절약된다.

- 트리를 표현할 때 가장 적합한 구조이다.

 

 

| 우선순위큐 (Priority Queue) 

 

우선순위 큐(Priority Queue)는 말 그대로 큐의 성질을 가졌으나, 각 데이터가 우선순위를 갖고 있어 우선순위가 높은 순서대로 나오게 해주는 큐 입니다.

만약 우선순위가 동일하다면 큐에서 그들의 순서에 의해 처리됩니다.

 

Queue인터페이스의 구현체 중 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼내게 된다는 특징이 있다.

null을 저장하면 NullPointException이 발생한다. PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장한다.

 

어떤 객체의 내부 속성에 대해 특별한 기준으로 정렬을 하고 싶다면 COmparable 인터페이스의 compareTo 메소드를 구현하면 됩니다.

정렬 기준의 순서대로 PriorityQueue에서 poll()하는 경우 우선순위가 높은 것부터 나오게 됩니다.

 

즉 , 삽입 후 조회를 하면 순서가 엉켜서 들어가도 poll()을 이용하여 데이터를 뽑아내면 우선순위가 높은 Data부터 출력이 됩니다.

 

만일, 우선순위를 역순(내림차순)으로 뽑아내고 싶다면 

new PriorityQueue(Collections.reverseOrder())

위와 같이 Collections.reverseOrder()를 사용해줌으로써 최대값 기준으로 우선순위가 정렬이 됩니다.

 

ex) 1,4,3,2,6 삽입을한 뒤 poll() 하면 -> 6,4,3,2,1 로 뽑힙니다.

 

사용예

PriorityQueue<Integer> queue = new PriorityQueue<>(); //PriorityQueue를 생성합니다.

가장 가중치가 낮은 순서로 poll,peek()을 할 수 있는 자료구조입니다.

Min Heap으로 데이터를 sort 시켜놓고 데이터를 출력하는 자료구조입니다.

 

MinHeap일때 의 예)

 

MinHeap으로 데이터를 정렬시켜 놓기 때문에 13254를 출력합니다.

또한 poll이나 peek을 할 경우에 자료구조의 가장 작은 데이터를 출력할 수 있는 것을 확인할 수 있습니다.