[자료구조] 큐(Queue)

 

목차

 

큐(Queue)의 개념

큐는 FIFO 선입선출(First In First Out)의 구조를 가진다. 즉, 큐에서는 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. 한 예는 은행에 번호표가 있다. 은행에서 번호표를 먼저 뽑은 사람이 서비스를 먼저 받는다. 이러한 은행의 번호표의 체계가 큐(Queue)이다. 큐는 추가로 그래프의 넓이 우선 탐색(BFS)에서 사용된다.

 

Enqueue : 큐 맨 뒤에 데이터 추가

Dequeue : 큐 맨 앞쪽의 데이터 삭제

 

 

위의 그림에 나온 것처럼 큐는 앞뒤가 다른 역할을 수행한다. 큐의 앞부분은 front는 삭제 연산만 수행하고 큐의 뒷부분은 rear는 삽입 연산만 수행한다. 보통 컴퓨터 버퍼에서 주로 사용되고, 여러 개가 한꺼번에 입력이 들어올 때 대기열을 만들어 순차적으로 처리할 때 사용된다.

 

 

큐(Queue)의 연산

메서드	설명
boolean add(Object)	큐에 데이터 추가 성공하면 true 반환, 단 저장공간이 부족하면 IllegalStateExcepetion 발생
Object remove()	큐에서 객체를 꺼내 반환 비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어옴 peek과 달리 큐가 비어있으면 NoSuchElement 발생
boolean offer(value)	큐에 데이터 추가 성공하면 true, 실패하면 false 반환
Object poll()	큐에서 객채를 꺼네 반환 비어있으면 null 반환.
Object peek()	삭제 없이 요소를 읽어옴 큐가 비어있으면 null 반환

 

 

큐(Queue) 사용법

Queue는 Collection 프레임워크의 일부이고 java.util 패키지에 소속되어 있기 때문에 Queue를 사용하려면 먼저 다음과 같이 import를 해야 한다.

import java.util.Queue;
import java.util.LinkedList;

Queue는 연결 리스트로 보통 구현되기 때문에 LinkedList도 import 해야 된다.

만약에 이렇게 import 하는 걸 두 줄 쓰기 싫다면 다음과 같이 해도 된다.

import java.util.*;

java.util.* import 하면 java.util 패키지 전부를 import 한 거와 같다. 

 

 

Queue 선언

Queue<String> str = new LinkedList<String>(); // String타입 Queue 선언 
Queue<String> str2 = new LinkedList<>(); // new 부분 <String> 생략 가능
Queue<Character> ch = new LinkedList<Character>(); // Character타입 Queue 선언

 

Queue 값 추가

Queue<String> queue = new LinkedList<>();
queue.add("Hello"); //"Hello" 추가 
queue.offer("World"); //"World" 추가

 

Queue 값 삭제

Queue<String> queue = new LinkedList<>();
queue.add("Hello"); //"Hello" 추가
queue.offer("World"); //"World" 추가

queue.remove(); // "Hello" 반환
queue.poll(); // "World" 반환

queue.remove(); //NoSuchElementException 발생
queue.offer9); //null 반환

 

시간 복잡도 (Time complexity)

Operation	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Insert (add)	O(1)	O(1)
Delete (remove)	O(1)	O(1)