선형구조 - 큐
Queue
: 데이터를 일시적으로 쌓아놓는 자료구조이다.
특징
- FIFO: 선입선출
- 단방향 구조
- 한 번에 데이터 한 개만 삽입, 삭제
- 버퍼, BFS 등에서 사용
구성요소
- Element: 데이터 요소
- Front: 맨 앞 요소의 인덱스로 물리적이 아니라 논리적인 데이터 순서
- Rear: 맨 뒤 요소의 하나 뒤 인덱스로 물리적이 아니라 논리적인 데이터 순서
선언
- java.util.Queue 클래스에서 제공한다.
//ex Integer 형
Queue<Integer> queue = new Queue<>();
데이터 추가
1. add();
- 성공: true 반환
- 실패: false 반환
- 큐가 꽉 찬 경우 IllegalStateException 발생
Queue<Integer> queue = new Queue<>();
queue.add(6);
2. offer();
- 성공: true 반환
- 실패: false 반환
- 큐가 빈 경우 NoSuchElementException 발생
- 큐가 꽉 찬 경우 fasle 반환
Queue<Integer> queue = new Queue<>();
queue.offer(6);
데이터 제거
1. remove();
- front 항목 반환 및 제거
- 큐가 빈 경우 null 반환
Queue<Integer> queue = new Queue<>();
queue.add(1);
queue.add(2);
queue.add(3);
queue.remove();
2. poll();
- front 항목 반환 및 제거
- 큐가 빈 경우 NoSuchElementException 반환
Queue<Integer> queue = new Queue<>();
queue.add(1);
queue.add(2);
queue.add(3);
queue.poll();
다양한 메서드
| 메서드 | 설명 | 반환값 | 예시 |
| peek() | 큐의 front 항목 반환, 삭제x | 큐의 front 값 - 큐가 빈 경우: null 반환 |
queue.peek(); |
| element() | 큐의 front 항목 반환, 삭제x | 큐의 front 값 - 큐가 빈 경우: NoSuchElementException 발생 |
queue.element(); |
| clear() | 큐 비우기 | queue.clear(); | |
| size() | 큐 의 크기 반환 | 큐 의 크기 | queue.size(); |
종류
1. 선형 큐(Linear Queue)
: FIFO의 특징을 갖는 기본 큐
주요작업
- Enqueue: rear에 항목 추가
- Dequeue: front에서 항목 제거
특징
- front: 삭제 연산만 수행
- rear: 삽입 연산만 수행
- FIFO
- Underflow, Overflow 발생 가능
단점
- Dequeue 시 front에 값이 없기 때문에 한 칸씩 값 이동시켜야 한다 => 시간 복잡도 ↑
// 이동시키지 않는 경우 공백이 삭제로 인해 공백이 발생한다. => 그냥 값이 빈다.
2. 원형 큐(Circular Queue)
: 선형 큐의 단점을 보완한 큐
주요작업
- 초기 상태: 빈 상태: front = -1, rear = -1, 배열 크기 = n
- 첫 번째 Enqueue: front = -1, rear = 0 => front = 0, rear = 0
- 그 이후의 Enqueue: rear에 항목 추가, rear 포인터 + 1
- Dequeue: front에서 항목 제거, front 포인터 + 1
- 마지막 Dequeue: front = rear => front = rear = -1
특징
- 큐 다 차지 않는 이상 무한으로 데이터 삽입 삭제 가능
- 메모리 효율적으로 사용 가능
단점
- 초기화 시점에 배열 크기 결정해서 동적으로 크기 조절이 불가하다
3. 우선순위 큐(Priority Queue)
: 먼저 들어온 데이터가 아니라 우선순위가 높은 데이터가 먼저 나가는 구조
- 힙으로 구현한다.
- 비선형 자료구조이기 때문에 다른 게시글에서 설명하겠다.
4. 데 큐(De Queue)
: 양 끝이 front이자 rear인 구조
특징
- Stack과 Queue의 장점을 갖고 있다.
- FIFO, LIFO 유연하게 지원한다.
- 양쪽에서 data를 삽입, 삭제가 가능하다.
- front
- addFirst()
- offerFirst()
- rear
- addLast()
- offerLast()