1. 큐의 개념과 LinkedList 사용
큐는 FIFO(선입선출) 구조 형식의 자료구조입니다.
ex) 줄 선 순서대로 입장
// 자바에서 큐 선언
Queue<자료형> 변수명 = new LinkedList<>();
Queue<Integer> queue = new LinkedList<>();(여기서 <자료형> 을 생략하면 어떤 자료형이든 넣을 수 있습니다.)
큐는 LinkedList를 사용한다는 것이 특징인데, 이는 ArrayList보다 삽입/삭제 연산에서 유리하다는 장점이 있습니다
ArrayList는 배열 기반이라 삽입 연산에서 배열의 끝에 추가하는 것은 O(1)이 소요되지만, 배열의 크기가 가득 차면 기존 요소들을 새 배열로 복사하는 크기 조정 과정이 필요할 수 있는데, 이는 O(n)의 시간이 소요됩니다. 큐는 삭제 연산시 첫 번째 데이터를 삭제하므로 매번 빈 공간을 채우기 위해 데이터 복사가 발생하게 되는데, 이 또한 O(n)의 시간이 소요됩니다.
반면에 노드를 이용하는 LinkedList는 큐의 삽입/삭제 연산에서 모두 O(1)의 시간복잡도를 가지게 되어 빠르고 효율적입니다.
2. 자바에서 큐의 메서드
-
삽입
queue.add(값): 성공 시 true, 실패 시 Exception이 발생
queue.offer(값): 성공 시 true, 실패 시 false 반환 -
삭제
queue.remove(): 성공 시 삭제된 값 반환, 공백 큐이면 Exception("NoSuchElementException") 발생
queue.poll(): 성공 시 삭제된 값 반환, 공백 큐이면 null 반환 -
확인
queue.peek(): 큐의 첫번째 값 반환, 공백 큐이면 null 반환 -
그 외
queue.clear(): 큐 초기화
queue.size(): 큐의 크기 반환
queue.isEmpty(): 공백 큐인지 true/false 반환
`queue.contains(값) : 큐에 해당 값이 들어있는지 true/false 반환
Ref.
https://kwin0825.tistory.com/157
https://devlog-wjdrbs96.tistory.com/246
Java/Collection/Queue/Queue가 ArrayList대신 LinkedList 사용하는 이유.md
