1. 큐(Queue)란?

데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가진다. 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말한다. 사람들이 줄을 서는 것을 예시로 생각하면 된다.

Enqueue는 큐 맨 뒤에 데이터 추가, Dequeue는 큐 맨 앞쪽의 데이터 삭제를 말한다.

2. 큐(Queue)의 연산

연산	기능
create()	큐를 생성한다.
init()	큐를 초기화한다.
is_empty(q)	큐가 비어 있는지를 검사한다.
is_full(q)	큐가 가득 찼는지를 검사한다.
enqueue(q, e)	큐의 뒤에 요소를 추가한다.
dequeue(q)	큐의 앞에 있는 요소를 반환한 다음 삭제한다.
peek(q)	큐에서 삭제하지 않고 앞에 있는 요소를 반환한다.

3. 큐(Queue)의 시간복잡도

연산	시간복잡도
삽입	O(1)
삭제	O(1)
탐색	O(n)

4. 큐 사용법

1. 큐 선언

import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용

2. 큐 값 추가

Queue<Integer> stack = new LinkedList<>(); //int형 queue 선언
queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.offer(3);   // queue에 값 3 추가


// add : 삽입에 성공하면 true 반환, 그렇지 않으면 IllegalStateException 발생

3. 큐 값 삭제

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
queue.offer(3);     // queue에 값 3 추가
queue.poll();       // queue에 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove();     // queue에 첫번째 값 제거
queue.clear();      // queue 초기화

// poll : 큐가 비어있으면 null 반환

4. 큐에서 가장 먼저 들어간 값 출력

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
queue.offer(3);     // queue에 값 3 추가
queue.peek();       // queue의 첫번째 값 참조

// queue.isEmpty() : queue가 비어있는지 확인

5. 스택과 큐의 차이