[Algorithm] 05. 큐 (Queue)

큐 (Queue)

 

큐(Queue)는 먼저 저장한 데이터가 먼저 출력되는 선입선출(FIFO) 방식으로 데이터를 저장하는 자료구조이다.

큐의 앞에서 데이터를 출력하는 것을 dequeue, 큐의 뒤에 데이터를 추가하는 것을 enqueue라고 한다.

 

큐(Queue)는 Queue 인터페이스를 사용한다.

큐(Queue)를 구현하는 방법에는 Linked List를 기반으로 한 방법과 Deque를 기반으로 한 방법이 있다.

 

 

 

Linked List 기반의 Queue

 

Linked List를 기반으로 한 Queue는 선형 자료구조로 FIFO(First In Fist Out) 방식으로 요소를 처리한다.

이 구조는 삽입과 삭제가 빠르며, 메모리의 동적 할당이 가능하다.

Queue<Integer> q = new LinkedList<>();

 

 

 

Deque 기반이 Queue

 

ArrayDeque를 기반으로 한 Queue는 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다.

이 구조는 스택과 큐의 기능을 모두 지원하며, 양방향에서의 효율적인 삽입과 삭제가 가능하다.

Queue<Integer> q = new ArrayDeque<>();

 

※  Linked List 기반 vs ArrayDeque 기반

ArrayDeque의 양쪽 끝에서는 삽입과 삭제 연산을 $O(1)$의 시간 복잡도로 지원한다.
따라서 특별한 이유가 없다면 ArrauDeque 기반의 Queue를 사용하는 것이 좋다.

 

 

 

Queue 연산

 

Queue<Integer> q = new ArrayDeque<>();

// enqueue
q.add(1);                                // q = [1]
q.add(2);                                // q = [1, 2]
q.add(3);                                // q = [1, 2, 3]

// deque
System.out.println(q.peek());            // 출력 = 1   // q = [1, 2, 3]
System.out.println(q.poll());            // 출력 = 1   // q = [2, 3]
System.out.println(q.remove());          // 출력 = 2   // q = [3]

 

※  Peek  vs  Poll  vs  Remove

peek(), poll(), remove() 세 가지 함수 가장 먼저 추가된 요소를 반환하는 기능을 하지만 차이가 존재한다.

	peek ()	poll ()	remove ()
요소 반환	O	O	O
요소 제거	X	O	O
null 반환	X	X	O

 

 

 

Queue 사용 시기

 

1. BFS (너비 우선 탐색)

 

그래프나 트리의 시작 노드부터 시작해 인접한 노드를 먼저 탐색하고, 그 다음 인접한 노드를 탐색하는 방법이다.

큐는 이 과정에서 탐색할 노드를 차례로 저장하고, 먼저 들어온 노드를 먼저 탐색하는데 사용된다.

• 최단 경로 찾기 : 최단 거리를 찾는 문제에서 탐색 순서를 관리하기 위해 큐를 사용한다.

 

2. 데이터 순차적 처리

 

데이터가 들어온 순서대로 처리되어야 하는 경우 큐를 사용한다.

• 주문 처리 시스템 : 먼저 들어온 주문부터 처리하기 위해 큐를 사용한다.