큐(queue)

참고

큐(queue) : 선입선출. FIFO(First In First Our) 기반의 자료구조이다.

큐를 구현하는 방법은 세 가지가 있다 : list, deque, Queue

1. list

가장 간단한 방법이지만 pop(0) 또는 insert(0, x)의 시간 복잡도가 O(N)이기 때문에 성능적으로 불리하다.

방향에 따라 다음과 같이 두 가지 형태로 표현할 수 있다. 

(1) append() : 뒤에서 데이터 추가, pop(0) : 앞에서 데이터 제거

>>> queue = [4, 5, 6]
>>> queue.append(7)
>>> queue.append(8)
>>> queue
[4, 5, 6, 7, 8]
>>> queue.pop(0)
4
>>> queue.pop(0)
5
>>> queue
[6, 7, 8]

(2) insert(0, x) : 앞에서 데이터 추가, pop() : 뒤에서 데이터를 제거하는 방식

>>> queue = [4, 5, 6]
>>> queue.insert(0, 3)
>>> queue.insert(0, 2)
>>> queue
[2, 3, 4, 5, 6]
>>> queue.pop()
6
>>> queue.pop()
5
>>> queue
[2, 3, 4]

2. deque

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

 

deque의 popleft()와 appendleft(x)메서드는 모두 O(1)의 시간 복잡도를 가지기 때문에, 위에서 살펴본 list의 pop(0)와 insert(0, x) 대비 성능 상에 큰 이점이 있다.

 

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

 

(1) append() : 뒤에서 데이터 추가, popleft() : 앞에서 데이터 제거

>>> from collections import deque
>>>
>>> queue = deque([4, 5, 6])
>>> queue.append(7)
>>> queue.append(8)
>>> queue
deque([4, 5, 6, 7, 8])
>>> queue.popleft()
4
>>> queue.popleft()
5
>>> queue
deque([6, 7, 8])

 

(2) appendleft(x) : 앞에서 데이터 추가, pop() : 뒤에서 데이터를 제거하는 방식

>>> from collections import deque
>>>
>>> queue = deque([4, 5, 6])
>>> queue.appendleft(3)
>>> queue.appendleft(2)
>>> queue
deque([2, 3, 4, 5, 6])
>>> queue.pop()
6
>>> queue.pop()
5
>>> queue
deque([2, 3, 4])

3. Queue

파이썬에서 큐를 사용하는 마지막 방법은 queue 모듈의 Queue 클래스를 사용하는 것이다.

deque와 달리 방향성이 없기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리된다. 따라서, 데이터가 추가하려면 put(x) 메서드를 사용하고, 데이터를 삭제하려면 get() 메서드를 사용한다.

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

 

put() : 데이터 추가, get() : 데이터 제거

>>> from queue import Queue
>>>
>>> que = Queue()
>>> que.put(4)
>>> que.put(5)
>>> que.put(6)
>>> que.get()
4
>>> que.get()
5
>>> que.get()
6