[queue] 큐(queue) 자료구조를 사용하는 3가지 방법

큐(queue)란?

선입선출, FIFO(First In First Out) 기반의 자료 구조로, 큐를 사용하면 데이터를 추가한 순서대로 제거할 수 있어 스트리밍, 너비우선 탐색 등 소프트웨어 개발에서 널리 사용된다.

 

파이썬에서는 큐 자료구조를 3가지 방법으로 사용할 수 있다.

1. list 

범용 자료구조인 list 를 사용한다.

append 함수로 객체를 추가한다.

list 객체의 pop(0) 함수를 호출하여 첫 번째 데이터를 제거한다.

만약 반대 방향으로 큐 자료구조를 사용하고 싶다면 insert(0, x) 함수를 사용하며 맨 앞에 데이터를 삽입할 수 있다.

>>> queue = [1, 2, 3]
>>> queue.append(4)
>>> queue.append(5)
>>> queue
[1, 2, 3, 4, 5]
>>> queue.pop(0)
1
>>> queue.pop(0)
2
>>> queue
[3, 4, 5]

>>> queue.insert(0, 1)
>>> queue.insert(0, 2)
>>> queue
[1, 2, 3, 4, 5]

하지만 list를 큐 자료구조처럼 사용하는 것은 비효율적이다. 

파이썬의 list는 무작위 접근(random access)에 최적화된 자료 구조이기 때문에 시간복잡도가 O(N)이다.

pop(0) 또는 insert(0, x) 연산의 경우 맨 앞 데이터를 제거 또는 추가한 후, 그 뒤의 모든 데이터를 한 칸씩 당기거나 밀어주어야 하기 때문에, 담고 있는 데이터의 개수가 많아질수록 느려진다. 

 

2. deque

이를 보완하기 위해 deque를 사용할 수 있다.

deque의 popleft()와 appendleft(x) 메서드는 모두 O(1)의 시간 복잡도를 가지기 때문에 리스트에 비해 훨씬 효율적이다.

 

collections 모듈의 deque는 'double-ended queue'의 약자로 데이터를 양방향에서 추가하고 제거할 수 있다.

popleft() 메서드를 제공하며, 이를 사용시 첫번째 데이터를 제거할 수 있다. 

appendleft(x) 메서드를 사용하면 데이터를 맨 앞에서 삽입할 수 있다.

>>> from collections import deque
>>>
>>> queue = deque([1, 2, 3])
>>> queue.append(4)
>>> queue.append(5)
>>> queue
deque([1, 2, 3, 4, 5])
>>> queue.popleft()
1
>>> queue.popleft()
2
>>> queue
deque([3, 4, 5])

from collections import deque

dque = deque()

dque.append(1)
dque.append(2)
dque.append(3)

print(dque)
# deque([1, 2, 3])

dque.popleft()
dque.appendleft(5)

print(dque)
# deque([5, 2, 3])

deque의 단점은 무작위 접근(random access)의 시간 복잡도가 O(N) 이라는 것이다. 내부적으로 linked list를 사용하기 때문에 i 번째 데이터에 접근하려면 맨 앞/뒤부터 i 번 순회해야 한다.

 

3. Queue

파이썬에서 queque 모듈의 Queue 클래스를 사용하여 큐를 사용할 수 있다.

이 방법은 주로 멀티 쓰레딩(threading) 환경에서 사용되며, 내부적으로 라킹(locking)을 지원하여 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있다.

deque와 달리 방향성이 없어서 데이터 추가와 삭제를 하나의 메서드로 처리할 수 있다.

put(x) 메서드로 데이터를 추가하고, get() 메서드로 데이터를 삭제한다.

>>> from queue import Queue
>>>
>>> que = Queue()
>>> que.put(1)
>>> que.put(2)
>>> que.put(3)
>>> que.get()
1
>>> que.get()
2
>>> que.get()
3

import queue
que = queue.Queue()
que.put(1)
que.put(2)
que.put(3)
que.put(4)
que.put(5)

print(que.empty())
# False

print(que.queue)
# deque([1, 2, 3, 4, 5])

que.get() # Remove and return an item from the queue.
print(que.queue)
# deque([2, 3, 4, 5])

que.get()
print(que.queue)
# deque([3, 4, 5])

que.get() 
print(que.queue)
# deque([4, 5])

que.get() 
print(que.queue)
# deque([5])

print(len(que))
# TypeError: object of type 'Queue' has no len()

print("qsize : {}".format(que.qsize()))
# qsize : 1

que.get() # Remove and return an item from the queue.
print(que.queue)
# deque([])

print(que.empty())
# True

Queue의 성능은 deque와 마찬가지로 데이터 추가/삭제는 O(1), 데이터 접근은 O(N) 의 시간 복잡도를 가진다.

 

 

 

참고자료

https://www.daleseo.com/python-queue/