큐(Queue)
- 큐(queue)는 선입선출, FIFO(First In First Out) 기반의 매우 유명한 자료 구조
- 큐를 사용하면 데이터를 추가한 순서대로 제거할 수 있기 때문에 스트리밍(streaming), 너비 우선 탐색(breath first search) 등 소프트웨어 개발에서 널리 응용되고 있습니다.
- FIFO Queue : First In First Out = 선입선출
- LIFO Queue : Last In Last Out = 후입선출
아래 예시는 python에서 list를 활용한 "뒤로 들어오고 앞에서 빠져나가는 구조"
>>> queue = []
>>> queue.append(4)
>>> queue.append(5)
>>> queue.append(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]아래 예시는 python에서 list를 활용한 "앞으로 들어오고 뒤에서 빠져나가는 구조"
>>> 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]- 이렇게 list를 큐 자료 구조의 효과를 내기 위해서 사용하는 것은 성능 측면에서 추천되지 않습니다. 파이썬의 list는 다른 언어의 배열처럼 무작위 접근(random access)에 최적화된 자료 구조이기 때문에 pop(0)또는 insert(0, x)는 성능적으로 매우 불리한 연산입니다. 이 두 연산은 시간 복잡도는 O(N)이기 때문에 담고 있는 데이터의 개수가 많아질 수록 느려집니다. 왜냐하면 첫 번째 데이터를 제거한 후에는 그 뒤에 있는 모든 데이터를 앞으로 한 칸식 당겨줘야 하고, 맨 앞에서 데이터를 삽입하려면 그 전에 모든 데이터를 뒤로 한 칸씩 밀어줘야 하기 때문입니다.
collections 모듈의 deque
- collections 모듈의 deque는 double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료 구조
- deque는 list에는 없는
popleft()라는 메서드를 제공하는데요. 이 메서드를 사용하면 첫 번째 데이터를 제거할 수 있습니다. 데이터의 흐름은 list 객체의pop(0)메서드를 사용할 때 처럼 뒤에서 앞으로 흐르게 됩니다
>>> 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])- deque는 appendleft(x)라는 메서드도 제공하는데요. 이 메서드를 사용하면 데이터를 맨 앞에서 삽입할 수 있습니다. 이 경우, 데이터의 흐름은 list 객체의 insert(0, x) 메서드를 사용할 때 처럼 앞에서 뒤로 흐르게 됩니다.
>>> 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])- deque의 popleft()와 appendleft(x)메서드는 모두 O(1)의 시간 복잡도를 가지기 때문에, 위에서 살펴본 list의 pop(0)와 insert(0, x) 대비 성능 상에 큰 이점이 있습니다.
- 하지만, 모든 자료 구조가 그러하듯 deque도 단점이 있습니다. 바로 무작원 접근(random access)의 시간 복잡도가 O(N)이라는 것입니다. 내부적으로 linked list를 사용하고 있기 때문에 i 번째 데이터에 접근하려면 맨 앞/뒤부터 i 번 순회(iteration)가 필요하기 때문입니다.
queue 모듈의 Queue 클래스
- 이 방법은 주로 멀티 쓰레딩(threading) 환경에서 사용되며, 내부적으로 라킹(locking)을 지원하여 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있습니다.
- deque와 달리 방향성이 없기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리됩니다. 따라서, 데이터가 추가하려면
put(x) 메서드를 사용하고, 데이터를 삭제하려면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스택(Stack)
- 데이터의 추가와 삭제가 한쪽 방향에서 일어나는 구조
- 스택도 저장공간의 제한이 있기 때문에 스택에 데이터가 가득 차 있는 경우 데이터를 추가하려고 하면 문제가 발생
- Stack overflow : 가득 찬 스택에 PUSH를 하는 경우
- Stack underflow : 스택이 비어있는 상태에서 POP하는 경우
python에서 list이 append(), pop()으로 스택처럼 활용 가능
>>> queue = []
>>> queue.append(4)
>>> queue.append(5)
>>> queue.append(6)
>>> queue.append(7)
>>> queue.append(8)
>>> queue
[4, 5, 6, 7, 8]
>>> queue.pop()
8
>>> queue.pop()
7
>>> queue
[4, 5, 6]References
oneofakindscene