[java] Queue 클래스 메서드

Queue(큐)

• meaning: 줄을 서다
• 입력과 출력 공간이 따로 존재하는 선형 자료구조
• 가장 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 특징 → FIFO(First In First Out)
• 즉, 삽입과 삭제가 양방향에서! ↔️
• 줄서기 🏃🏻‍♂️🏃🏻‍♂️🏃🏻‍♂️ 생각하면 됨!

• 자바에서 Buffer가 큐를 사용 ㅎㅎ
• 너비 우선 탐색(BFS)에서 자주 사용

 

Queue 클래스 사용법

import java.util.Queue;

rear
: 큐에서 가장 끝 데이터

front
: 큐에서 가장 앞의 데이터

 

삽입

Boolean add(Object value)	rear 부분에 새로운 데이터 삽입, 성공 시 true, 실패 시 Exception (가득 차 있을 경우 예외 발생)
Boolean offer(Object value)	성공 시 true, 실패 시 false(가득 차 있을 경우에도 false)

 

삭제

Boolean remove()	삭제된 value 값 반환, 공백일 때 Exception("NoSuchElementException")
Object remove(Object value)	해당 value가 존재하면 삭제 후 true 반환, 실패 시 false
Object poll()	front 부분에 있는 데이터 삭제, 삭제된 value 값 반환, 공백일 때 null 반환

 

값 확인

Object element()	큐 front에 위치한 value 반환, 공백일 때 Exception("NoSuchElementException")
Object peek()	큐 front에 위치한 value 반환, 공백일 때 null 반환

⭐ 큐는 rear에 위치한 요소를 확인하는 함수를 제공하지 않음

 

초기화

Void clear()

 

큐 크기

Integer size()

큐 사이즈 반환

 

큐 검색

Boolean contains(Object value)

해당 값이 존재할 때 true, 없으면 false

 

큐 공백 여부 확인

Boolean isEmpty()

공백이면 true, 아니라면 false

• 쉽게 말하자면..
  • 값 넣기: offer
  • 값 빼기: poll
  • 값 확인하기: peek
  • 비었는지 확인하기: isEmpty
  • 검색하기: contains

⭐ 여기서 말하는 값은 front에 위치한 값이다! 가장 최근에 넣은 값은 rear(맨 뒤)로 가기 때문!!

 

큐 인터페이스를 구현하는 주요 클래스(구현체)

LinkedList(연결 리스트)

import java.util.PriorityQueue;
import java.util.Collections;

// 우선 순위: 낮은 숫자
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

// 우선 순위: 높은 숫자
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

• 이중 연결 리스트로 구현된 클래스
• 참조하는 원소에 따라 처음부터 정방향 또는 역순으로 순회
  • 순차적 접근 → 검색 속도 느림
• 배열의 단점을 보완
• 데이터 삽입 및 삭제 시 주소값만 변경해주면 됨!
• 중간 요소에 삽입 및 삭제하는 경우 이용

void addFirst(Object obj)	맨 앞에 객체 삽입
void addLast(Object obj)	맨 뒤에 객체 삽입
boolean add(Object obj)	맨 뒤에 객체 추가 후 성공하면 true
void add(int index, Object element)	지정된 index 위치에 객체 삽입
void addAll(Collection c)	맨 뒤에 주어진 컬렉션의 모든 객체 삽입
void addAll(int index, Collection c)	지정된 index 위치부터 컬렉션의 데이터 삽입
Object removeFirst()	첫번째 노드 삭제
Object removeLast()	마지막 노드 삭제
Object remove()	LinkedList 첫 번째 노드 삭제
Object remove(int index)	지정된 index에 있는 객체 제거
boolean remove(Object obj)	지정된 객체 제거 후 성공하면 true
void clear()	전체 삭제

• contains(), indexOf(), lastIndexOf(), get(), subList() ... 등 다양한 메소드 지원
• 참고
  • https://inpa.tistory.com/entry/JAVA-%E2%98%95-LinkedList-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%99%84%EB%B2%BD-%EC%A0%95%EB%B3%B5%ED%95%98%EA%B8%B0#linkedlist_vs_arraylist_%ED%8A%B9%EC%A7%95_%EB%B9%84%EA%B5%90

ArrayList vs. LinkedList

■ ArrayList
- 배열 이용
- 모든 데이터 상수 시간 접근

■ LinkedList
- 위치에 따라 이동시간 발생
- 노드 연결
- 데이터가 추가되거나 중간에 있는 데이터가 삭제되어도 땡겨지지 않음
- 노드의 참조를 변경하기만 하면 됨!

---

ArrayDeque(배열 양방향 큐)

Queue<Integer> q = new ArrayDeque<>();

• 가변 크기 배열을 사용하여 큐를 구현한 클래스
• 배열 기반으로 동작 → 삽입 또는 삭제의 속도가 빠름
• 큐의 앞과 뒤에 빠르게 요소 삽입 및 삭제 가능
  • LinkedList보다 성능 좋음

---

PriorityQueue(우선순위 큐)

import java.util.PriorityQueue;
import java.util.Collections;

// 우선 순위: 낮은 숫자
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

// 우선 순위: 높은 숫자
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

• 우선순위 큐를 구현한 클래스
• 일반적인 큐의 구조 + 우선 순위 높은 데이터순으로 출력
• Queue 인터페이스 + 우선순위순으로 관리
• 큐 설정에 따라 front에 항상 최댓값 or 최솟값 위치
  • 이때, 모든 노드의 값들이 정렬이 되는 것은 아님!
• 일반적으로 힙(heap)을 이용하여 구현(이진트리 구조)