99클럽 코테 스터디 8일차 TIL + Queue

학습 키워드

- Queue

 

공부한 내용

Queue

• Queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미한다. 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조로 데이터의 추가와 삭제를 순서대로 처리한다.
• 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태이다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말한다.

→ 큐의 맨 끝에서 데이터를 추가하고(Enqueue) 큐의 맨 앞에서는 데이터가 삭제(Dequeue)된다.

Queue의 특징

• FIFO(First In First Out) 구조, 먼저 들어간 자료가 먼저 나오는 구조이다.
• 큐의 맨 앞은 프런트(front)로 정하여 삭제 연산만 수행한다.
• 큐의 맨 뒤는 리어(rear)로 정하여 삽입 연산만 수행한다.
• Queue는 null 값의 삽입을 허용하지 않는다.(요소가 없다는 의미로 값을 반환하기 때문에 허용하지 않음)
• 그래프의 넓이 우선 탐색(BFS), 네트워크 관리, 시스템 대기열, 프린터 스케줄링, 데이터 스트림 처리 등 다양한 분야에서 널리 사용된다.

Queue 구현 클래스

LinkedList

• LinkedList는 이중 연결 리스트 데이터 구조를 이용해 Queue 인터페이스를 구현한다.
• FIFO 자료구조이다.
• 이중 연결 리스트는 노드로 이루어져 있는데 이 노드는 데이터 부분과 주소 부분을 별도로 가지고 있다.
• LinkedList에 객체를 추가하거나 삭제하면 앞, 뒤 주소만 변경되고 나머지는 변경되지 않는다. 그러나 인덱스가 없기 때문에 특정 요소에 접근하기 위해서는 순차 탐색이 필요하므로 탐색 속도가 떨어진다는 단점이 있다.

PriorityQueue

• PriorityQueue는 자바의 Queue 인터페이스의 구현 클래스이다. 일반적인 Queue(큐)의 FIFO(First-In-First-Out)를 따르지만 우선 순위에 따라 요소를 정렬하여 우선 순위가 가장 높은 요소 먼저 처리되도록 한다.
• Priority Heap을 통해 구현 : 각 요소들을 힙(heap) 자료구조에 저장하며, null 값은 저장할 수 없다.

LinkedList vs PriorityQueue

LinkedList 장점

• 요소의 추가 및 제거가 빠르다.
• 저장 공간을 효율적으로 사용한다.

단점

• 중간에 있는 요소를 검색 또는 수정하는 데 느리다.

PriorityQueue 장점

• 우선순위에 따라 자동 정렬된다.
• 정렬된 상태를 유지하면서 데이터를 빠르게 추가한다.

단점

• 추가 및 삭제할 때의 시간 복잡도가 상대적으로 느리다.

 

회고

발생한 문제

- 코딩 문제 풀이 중에 Queue에 대한 공부가 부족하여 문제 풀이가 막히는 문제가 생겼다.

 

해결 방법

- Queue에 대한 공부를 진행했다. 

 

알게된 내용

- Queue의 대표적인 구현 클래스 중에 LinkedList와 PriorityQueue에 대해 알게 되었다.

 

 

 

참고 자료

- https://velog.io/@db_jam/%EC%9E%90%EB%B0%94-%ED%81%90Queue-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC

- https://imyena.tistory.com/99