큐(Queue)

---

<큐 노트 정리>

큐는?

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out)의 자료구조다.

큐의 주요 연산과 시간복잡도

삽입(Enqueue)과 꺼내기(Dequeue) - 각각 큐의 맨 뒤(rear)와 맨 앞(front)에서만 이루어진다. -> O(1)
탐색 - 배열, 스택과 마찬가지로 전체 원소를 하나하나 차례대로 조회한다. -> O(n)

큐의 주요 사용처

• 먼저 들어온 순서대로 데이터의 처리가 필요한 곳
• 프린터 출력 대기표
• 그래프의 너비 우선 탐색(BFS, Breadth First Search)

---

JAVA에서의 큐 사용 예시

import java.util.ArrayDeque;

또는

import java.util.LinkedList;

주요 메소드(ArrayDeque)

출처

메소드	타입	설명
offer(E e)	boolean	큐의 맨 뒤(rear)에 원소를 삽입(add(E e)와 같음)
poll()	E	큐의 가장 앞(front)의 원소를 큐에서 삭제한 후 반환(removeFirst()와 같음)
peek()	E	큐의 가장 앞(front)의 원소를 삭제하지 않고 반환(getFirst()와 같음)
contains(Object o)	boolean	큐가 o를 원소로 가지고 있는 경우 true, 아닐 시 false 반환
isEmpty()	boolean	큐가 비어있는 경우 true, 아닐 시 false 반환

예시 코드

ArrayDeque<Integer> queue = new ArrayDeque<>();

queue.offer(1);
queue.offer(3);
queue.offer(5);
queue.offer(7);
queue.offer(9);    
System.out.println(queue);				// [1, 3, 5, 7, 9]
        
System.out.println(queue.poll());		// 1
System.out.println(queue.poll());		// 3
System.out.println(queue.poll());		// 5
System.out.println(queue);				// [7, 9]

System.out.println(queue.contains(7));	// true
System.out.println(queue.contains(5));	// false
System.out.println(queue.poll());		// 7
System.out.println(queue.poll());		// 9
System.out.println(queue);				// []