Queue

Queue란?

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

 

Enqueue : 큐 맨 뒤에 데이터 추가
Dequeue : 큐 맨 앞쪽의 데이터 삭제

Queue의 특징

1. 먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In FIrst Out) 구조 
2. 큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함
3. 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행함  

4. 그래프의 넓이 우선 탐색(BFS)에서 사용
5. 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킴

 

 

 

Queue 사용법 

0. 선언

import java.util.Queue;

import java.util.LinkedList;

 

Queue<자료형> 변수명 = new LinkedList<>();

위 같은 경우는 자료형에 넣은 자료형만 삽입, 삭제 가능

Queue 변수명 = new LinkedList();

 위 같은 경우는 어떤 자료형이든 삽입, 삭제 가능(이전에 int형을 넣었어도 String형 삽입 가능)

 

 

1. 삽입                                                                       

q.add(삽입할 value);

  ㄴ 반환 값(boolean): 삽입 성공 시 true / 실패 시  Exception발생

 

q.offer(삽입할 value);

  ㄴ 반환 값(boolean): 삽입 성공 시 true / 실패 시 false 반환

 

2. 삭제                                                                       

q.remove();

  ㄴ 반환 값(삭제된 value의 자료형): 삭제된 value / 공백 큐이면 Exception("NoSuchElementException") 발생

 

q.remove(삭제할 value);

  ㄴ 반환 값(boolean): 큐에 해당 value가 존재하면 해당 값 삭제 후 true / 존재하지 않으면 false 반환

 

q.poll();

  ㄴ 반환 값(삭제된 value의 자료형): 삭제된 value / 공백 큐이면 null 반환

 

3. 큐의 front에 위치한 value 반환                                        

q.element();

  ㄴ 반환 값(큐 head에 위치한 value의 자료형): 큐 head에 위치한 value / 공백 큐이면 Exception("NoSuchElementException") 발생

 

q.peek();

  ㄴ 반환 값(큐 head에 위치한 value의 자료형): 큐 head에 위치한 value / 공백 큐이면 null 반환

 

4. 큐 초기화(= 공백 큐 만들기)                                         

q.clear();

  ㄴ 반환 값(void): X

 

5. 큐 크기                                                                      

q.size();

  ㄴ 반환 값(int): 큐 사이즈 반환

 

6. 큐에 해당 원소가 존재하는지?                                       

q.contains(찾을 value);

  ㄴ 반환 값(boolean): 해당 값이 존재할 때 true / 해당 값이 없을 때 false 반환

 

7. 공백 큐인가?                                                               

q.isEmpty();

  ㄴ 반환 값(boolean): 공백 큐이면 true / 공백 큐가 아니면 false 반환

 

Queue 종류 설명

아래 링크 참고

 

https://kwin0825.tistory.com/54

[자료구조] 큐(Queue)

 

Queue 시간 복잡도

큐 시간복잡도 Big O

- 삽입: Insertion O(1)

- 삭제: Deletion O(1)(dequeue) / O(N)(remove)

- 검색: Search O(N)

 

※큐의 삽입은 front에서만 일어나고 삭제는 항상 rear에서만 일어나므로 삽입과 삭제에 소요되는 시간복잡도는 O(1)로 고정

 

Queue 유사 메서드와의 차이

위 표는 추가,삭제,검사의 같은 기능을 하지만 차이를 갖는 유사한 메서드들을 비교한 표이다. add(), remove(), element() 메서드는 실행에 실패할 경우 예외를 발생시키지만 offer(), poll(), peek() 메서드는 실패할 경우null 또는 false를 리턴한다는 차이가 있다.

• enqueue : 성공시 공통적으로 true 리턴
  -add() : 실패시 예외 발생
  -offer() : 실패시 false 리턴
• dequeue : 성공시 공통적으로 제거한 값 리턴
  -remove() : 실패시 예외 발생
  -poll() : 실패시 null 리턴
• peek : 성공시 공통적으로 가장 먼저 들어간 값 리턴
  -element() : 실패시 예외 발생
  -peek() : 실패시 null 리턴

 

참고 링크 : 

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

[Java] 큐(Queue) 자료구조 정리

https://coding-factory.tistory.com/602

[Java] 자바 Queue 클래스 사용법 & 예제 총정리

https://kwin0825.tistory.com/157

[JAVA / 자바] Queue(큐) 클래스 사용법 및 함수(Method) 정리