[쓰면서 익히는 알고리즘과 자료구조](5) 큐(Queue)

FIFO(First In First Out) 구조다.

5.1.1 큐의 기본 연산들

큐도 스택과 비슷하게 데이터를 넣고(Enqueue) 꺼내는 (Dequeue) 연산이 기본이다.

• Enqueue : 큐에 새로운 아이템 추가, 시간 복잡도는 O(1)
• Dequeue: 가장 먼저 들어갔던 아이템을 큐에서 꺼낸다. 시간 복잡도는 O(1)
• Front: 큐의 처음 데이터를 확인한다.
• Roar: 큐의 마지막 데이터를 확인한다.

5.1.2 Python 에서 Queue 사용하기

1. 리스트 사용, append()와 pop()을 사용하면 큐 자료구조 표현 가능
   1. 리스트는 내부적으로 배열을 사용하기 떄문에 pop(0)을 통해 맨 앞 아이템을 계속 꺼내 배열을 정리하는 작업은 큐 자료구조로 이용가능하다
   2. 속도 면에서 효율적이지 못한 부분이 있어 추천하지 않는다
2. collections.deque 클래스를 이용하는 것이다.
   1. 리스트와는 다르게 내부적으로 이중 연결 리스트를 사용하기 떄문에, 큐 자료구조의 Enqueue / Dequeue 연산에는 적합하다
   2. 다만 collections.deque 클래스는 빌트인이 아니기 떄문에 코드에 import 를 해줘야 한다.
3. queue.Queue() 클래스를 이용하는 것이다.
   1. 이 클래스는 스레드 세이프(thread safe)한 운영에 적합하다. 알고리즘 문제 해결 방법에서는 크게 다루어질 일이 없다. 그와 비슷한 multiprocessing.Queue가 있다.
   2. 알고리즘 문제를 해결하는 과정에서 이 2가지 방법은 많이 사용되지 않기 때문에 자세한 설명은 생략하겠다.

5.2 큐 연습

큐 단독으로 문제를 해결하는 문제도 있지만 대게는 트리나 그래프의 너비 우선 탐색(Breadth First Search) 등에서 기본적으로 사용되는 자료구조다. 따라서 큐 자료구조 활용은 트리 혹은 그래프 챕터에서 활용해보겠다.