728x90
반응형
▷ 큐(Queue)이란?
큐(Queue)는 FIFO(퍼스트 인 퍼스트 아웃) 원리를 기반으로 구성된 요소들의 집합을 나타내는 추상적인 데이터 유형이다.
큐는 스택과 다르게 양방향 자료구조이다. 즉 출구, 입구가 따로 따로 존재한다는 것이다.
스택의 삽입,삭제가 top에서 모두 이루어진다면
큐는 -큐의 가장 앞 부분을 가리키는 front
-큐의 가장 뒷 부분을 가리키는 rear 에서 삽입, 삭제가 이루어진다.
큐에서 수행되는 작업은 다음과 같다.
큐의 rear에 데이터를 추가하는 add/offer,
큐의 front의 데이터를 제거하고 null값으로 채우는 poll, 제거만 하는 remove, 초기화하는 clear
큐의 맨 앞(front)에 있는 요소를 제거하지 않고 액세스하는 peek
▷ 큐(Queue)의 특징?
큐 구조는 줄을 선 사람들과 같다.
- FIFO(First-In First-out)
> 큐에 맨 처음 추가된 요소가 가장 먼저 제거 (줄을 먼저 선 사람이 먼저 빠짐)
- 스택의 양쪽 끝에서 액세스 가능
> 큐는 'rear'라고 하는 맨 뒤에서 삽입되고 'front'라고 하는 맨 앞에서 삭제된다.
- 일정한 시간 복잡성
> 빅오 표기법을 따라 O(1)의 일정한 시간으로 수행 가능 (O(n))
- BFS(넓이 우선 탐색)에 사용
> 알고리즘 그래프 구현 시 넓이 우선 탐색(BFS)에 사용되는 자료 구조이다.
- 동적 크기
> 큐는 연결리스트를 사용하여 구현한다. (LinkedList)
▷ 자바에서 큐(Queue) 을 어떻게 쓰나?
import java.util.Queue; <- 먼저 호출은 필수! LinkedList를 기본적으로 이용하기 때문에
import java.util.LinkedList; <- 함께 호출해줍니다.
기초적인 실습을 통해 큐 구조를 익혀보자.
public class MyQueue {
Queue<Element> queue = new LinkedList<Element>();
//값의 삽입(Enqueue)
public void push(element) {
queue.offer(element) //값이 꽉 찼을 경우 false 반환
queue.add(element) //값이 꽉 찼을 경우 IllegalStateException 예외 발생
}
//값의 제거(Dequeue)
public pop() {
return queue.poll() //비어있을 경우 null 반환
//return queue.remove() //비어있을 경우 NoSuchElementException 발생
}
public peek() {
return queue.peek() //비어있을 경우 null 반환
//return queue.element() //비어있을 경우 NoSuchElementException 발생
}
public int size() {
return queue.size();
}
}
보면 알 수 있듯이 자바 Queue 클래스는 큐의 Enqueue와 Dequeue기능을 기본적으로 제공한다.
다음은 자바에서 Queue 클래스를 활용한 예시다.
지금까지 큐 자료 구조를 자바에서 어떻게 구현하는 지 예시를 통해 알아봤다.
큐와 함께 거론되는 스택과 함께 알고 있으면 좋다.
다음에는 우선순위 큐(Queue)에 대해 기회가 되면 정리해 보겠다.
>참고하기 좋은 글
반응형
'Programming Languages > Java' 카테고리의 다른 글
[JAVA/자료구조] Iterator와 반복문 / 자바에서 Iterator 사용하기 (0) | 2023.05.28 |
---|---|
[JAVA/자료구조] 자바 연결리스트 사용법 (Linked List) 구현 / 예제 정리 (0) | 2023.05.23 |
[JAVA] 문자열 String | StringBuffer | StringBuilder 각 차이점 - 성능의 차이! (2) | 2023.05.20 |
[JAVA/자료구조] 자바 Stack 사용법 / 스택 예시 총 정리 - 문자열 뒤집기, 괄호 짝 맞추기 (2) | 2023.05.08 |
[JAVA] 자바 정수형 사용하기 / int형과 long형의 정확한 차이점 (0) | 2023.05.07 |