[파이썬 | 자료구조] 3. 큐(Queue)

3. 큐(Queue)

선입선출, FIFO(First In, First Out) 방식을 사용하는 데이터 구조

먼저 넣은 데이터를 먼저 꺼내게 된다. 양방향 터널을 생각하면 된다.

Python에는 Queue 라이브러리를 제공한다. 하지만 Queue의 대부분의 기능은 기본 List로 구현할 수 있다.

알고리즘 문제를 풀때는 Queue나 Stack의 기능을 deque 라이브러리로 사용하는것이 제일 빠르다.

Python 기본 queue 라이브러리 사용

collections 라이브러리의 deque 사용하여 구현

deque 대신 기본 list를 사용해도 무방하지만 deque.popleft()는 O(1)이지만, list.pop(0)는 O(N)으로 시간복잡도 차이가 발생한다.

Priority Queue의 구현

일반적인 Queue의 Priority, 즉 우선순위는 시간이라고 할 수 있다.

즉 먼저들어온 자료가 가장 높은 우선순위를 가지는 것이라고 할 수 있다.

Priority Queue는 시간이 아닌, 데이터의 크기를 가지고 우선순위를 부여한다.

예를들어 1, 4, 2, 3 ,5 가 차례대로 Queue에 들어온다면

1의 우선순위가 가장높으므로 (가장 먼저들어왔으므로) 제일 앞쪽에 위치하게 된다.

하지만 1, 4, 2, 3, 5가 우선순위가 데이터의 크기가 클수록 높다고 설정된 Priority Queue에 들어온다면

5, 4, 3, 2, 1 로 위치하게 된다.

그렇다면 Priority Queue 를 구현하는 방법에서 신경써야 할 것은 두가지로 나눌 수 있다.

1. 삽입은 마구잡이로 하고, 꺼낼때 우선순위가 가장 높은 것을 찾는다.
2. 삽입할 때 우선순위대로 정렬하고, 꺼낼때 바로 꺼낸다.

1번 방법

일단 put으로 넣을때는 그냥 순서대로 리스트에 넣는다.

get으로 불러올때 Priority가 가장 큰것을 선형으로 탐색해서 찾아서 반환한다.

따라서 삽입은 O(1), 탐색 및 삭제는 O(N)이 된다.

2번 방법

put으로 넣을때 sort를 수행해서, 제일 큰 값이 deque의 맨 왼쪽에 정렬되도록한다.

get으로 불러올때는 단순히 popleft로 제일 우선순위가 높은것을 불러온다.

따라서 삽입은 O(N lg N), 탐색 및 삭제는 O(1)이 된다.

(Python의 sorted함수는 시간복잡도가 O(N lg N)로 알려져 있다. )