[Section 3] 파이썬 큐 모듈 사용법 _ 복잡도 분석&비교

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

큐 자료 구조는 이전에 제시한 원형 배열 이외에도 리스트 자료구조를 사용하거나, 큐 모듈을 이용하는 방법이 있다. 어떤 자료를 사용하느냐에 따라 효율이 달라지니, 큐 모듈을 사용하는 방법을 알아 두도록 하자.

1.  큐 모듈 호출하기 _ import queue

파이썬에는 큐 모듈이 내장되어있어서, 간단한 큐 자료구조는 큐 모듈 호출을 이용하여 사용하기로 하자. 큐 모듈을 호출하는 코드는 import queue이다. 큐 모듈의 호출이 완성되었다면, 큐 모듈 사용법을 익혀보자.

 

가장 먼저 큐 선언과 큐가 비었는지 확인하는 코드는 다음의 예시 코드를 참조하자.

 

예시 코드:

import queue

Q=queue.Queue()

Q.empty()

 

위의 코드는 큐의 사이즈가 고정되어있지 않은 큐이다. 만약 고정적 사이즈를 가지는 큐를 선언하고 싶다면, 큐를 선언할 때 큐의 고정 사이즈를 정수 타입으로 같이 선언하자. 

 

예시 코드:

Q=queue.Queue(10)

 

2.  큐 인큐와 디큐 사용법 _ put(data) , get()

큐 모듈에서 인큐에 해당하는 코드는 put(data)이다. 그리고 get()은 디큐에 해당하는데, 삭제된 데이터를 반환하는 기능 또한 가지고 있다. 1부터 5까지 인큐 하고 디큐 하는 과정을 다음과 같은 예시 코드로 확인해보자.

 

예시 코드:

from queue import Queue

Q=Queue()

Q.empty()

Q.put(1)

Q.put(2)

Q.put(3)

Q.put(4)

Q.put(5)

Q.get()

Q.get()

Q.get()

Q.get()

Q.get()

 

코드 결과:

큐 모듈 사용 예시

 

* 먼저 들어간 데이터가 먼저 나오는 구조이다. 

 

3.  어떤 큐 알고리즘을 사용해야하는가? _ 시간 복잡도 비교

큐를 리스트 형태 그대로 사용하는 것은 디큐 과정에서 O(n)의 시간 복잡도를 가진다. 이는 데이터의 디큐 과정에서 생기는 공백을 메우기 위해 모든 데이터들이 한 자리씩 이동하는 과정에서 생기는 복잡도이다. 반면에 위의 모듈을 사용하면, 디큐의 시간 복잡도는 O(1)이다. 그렇다면, 리스트 큐는 필요가 없는 것인가? 

 

데이터의 접근 측면으로 따지면 시간 복잡도 관계는 역전된다. 리스트 큐의 데이터 접근 시간 복잡도는 O(1)인 반면에 큐 모듈의 데이터 접근 시간 복잡도는 O(n)이기 때문이다. 따라서 어떤 상황에서 적절한 알고리즘을 선택하는 것은 사고를 동반해야 하는 과정이라고 볼 수 있다.