파이썬 자료구조(심화)-2

스택(LIFO)

 

스택은 삽입과 삭제를 LIFO(후입 선출)방식으로 빠르게 처리해 주는 객체 컬렉션 입니다. 삽입과 삭제 작업은 주로 push와 pop으로 진행합니다.

스택이 활용 되는 곳은 런타임 메모리 관리, 트리나 그래프에서 깊이 우선 탐색(DFS)가 있습니다.

이제 파이썬에서 스택을 구현할 수 있는 방식을 살펴보겠습니다.

 

간단한 내장 스택 방식인 list

 

이 부분은 전에 list에 대해 설명한 파트가 있어서 URL을 통해 남겨두겠습니다.

list 개념

https://hyun-am-coding.tistory.com/entry/Python-List?category=778330

 

list 시간복잡도

https://hyun-am-coding.tistory.com/entry/Python-list-연산에-따른-시간-복잡도?category=778332

 

collections.deque를 이용한 빠르고 강력한 스택

 

deque 클래스는 O(1) 시간에 어느 쪽에서든 요소를 추가 및 삭제할 수 있는 데큐 입니다. 또한 이중 연결리스트 구조로 되어 있어서 요소를 삽입과 수정하는데 있어서 매우 빠릅니다.

 

from collections import deque

stack = deque()

stack.append("딸기")
stack.append("당근")
stack.append("수박")
stack.append("참외")
stack.append("메론")

print(stack)

for _ in range(len(stack)):
    print(stack.pop(),end="-")
# 출력 값
# deque(['딸기', '당근', '수박', '참외', '메론'])
# 메론-참외-수박-당근-딸기-

 

병렬 컴퓨팅을 위한 queue.LifoQueue

 

LifoQueue 스택 구현은 동기 방식이며 동시에 여러 생산자와 소비자를 지원하는 잠금 체계를 제공합니다.

자세한 정보는 파이썬 공식 문서를 참고하시면 되겠습니다.

https://docs.python.org/ko/3/library/queue.html?highlight=lifoqueue#queue.LifoQueue

 

사용 예시는 다음과 같습니다.

from queue import LifoQueue
s = LifoQueue()
s.put('eat')
s.put('drink')
s.put('running')
print(s)

print(s.get())
print(s.get())
print(s.get())
# print(s.get()) # Lifo에 값이 없어서 무한 대기 상태에 들어간다
print(s.get_nowait()) # 비어있으면 Empty를 출력 합니다.

# 출력 값
# running
# drink
# eat
# _queue.Empty

 

큐(FIFO)

 

큐는 선입선출(FIFO) 방식의 삽입과 삭제를 지원하는 객체 컬렉션 입니다.

큐가 활용 되는 곳은 트리나 그래프 데이터 구조에서 너비 우선 탐색(BFS) 또는 병렬 프로그래밍과 스케줄링 문제를 해결하는데 사용됩니다.

 

list로 구현한 매우느린 큐

 

리스트에서 다음과 같이 구현하면 O(n)의 시간이 걸리므로 list로 큐를 구현하는것은 추천하지 않습니다.

a =[1,2,3,4,5]
print(a.pop(0))
# 출력 값 
# 1

 

collections.deque로 구현한 빠르고 강력한 큐

 

deque는 popleft()로 O(1)의 성능으로 큐를 구현할 수 있습니다. 사용 예시는 아래와 같습니다.

from collections import deque

q = deque()
q.append("딸기")
q.append("당근")
q.append("수박")
q.append("참외")
q.append("메론")

for _ in range(len(q)):
    print(q.popleft(),end="-")
# 출력 값
# 딸기-당근-수박-참외-메론

 

queue.Queue로 구현한 병렬 컴퓨팅을 위한 잠금 체계

 

앞에서 스택에서 구현한 LifoQueue와 마찬가지로 큐도 이러한 병렬 컴퓨팅 큐가 있습니다.

사용법은 앞에서 구현한 LifoQueue와 같습니다.

from queue import Queue
s = Queue()

s.put(1)
s.put(2)
s.put(3)

print(s.get())
print(s.get())
print(s.get())
# print(s.get()) # 큐가 블록되어 영원히 기다립니다.
print(s.get_nowait())
# 출력 값
# 1
# 2
# 3
# _queue.Empty

 

우선순위 큐(heap)

 

우선순위 큐는 전 순서 집합으로 된 키(예를 들어 숫자 가중치)가 있는 레코드 집합을 관리하는 컨테이너 데이터 구조입니다. 그리고 레코드 집합에서 '가장 작은' 키 또는 '가장 큰' 키를 사용하여 레코드에 빠르게 접근할 수 있습니다.

우선순위 큐는 큐의 변형으로 생각하면 되겠습니다. 삽입 순서는 상관없이

'우선순위가 가장 높은'

순으로 제거됩니다.

우선순위가 사용되는 예시는 운영체제에서 작업 스케쥴러가 있습니다.

이제 우선순위 큐를 코드로 구현해보겠습니다.

 

수동으로 정렬된 큐 유지하기 (list로 구현)

 

list의 장점은 가장 작은 항목 또는 가장 큰 항목을 찾아서 삭제할 수 있습니다. 하지만 새로운 항목을 삽입할때 O(n)이 걸리는 단점이 있습니다.

예시는 다음과 같습니다.

q = []

q.append((2,'banana'))
q.append((1,'coke'))
q.append((3,'rock'))

# 주의 : 재정렬할 때마다
# 새 요소가 삽입됩니다.
# bisect.insort()를 이용해서 해결합니다.
q.sort(reverse=True)

while q:
    next_item = q.pop()
    print(next_item)

# 출력 값
# (1, 'coke')
# (2, 'banana')
# (3, 'rock')

 

리스트 기반 이진힙 (heapq로 구현)

 

일반 list를 뒷받침 해주는게 이진 힙 구현입니다. 그리고 가장 작은 항목의 삽입과 추출을 O(logn) 시간에 해냅니다.

이 모듈은 파이썬에서 우선순위 큐를 구현하기에 좋은 방법입니다. 또한 파이썬에서 heapq는 최소 힙 구현만 제공합니다.

예시는 다음과 같습니다.

import heapq
q = []
heapq.heappush(q,(2,'banana'))
heapq.heappush(q,(1,'coke'))
heapq.heappush(q,(3,'rock'))

while q:
    next_item = heapq.heappop(q)
    print(next_item)

# 출력 값
# (1, 'coke')
# (2, 'banana')
# (3, 'rock')

 

동기적이고 완벽한 우선순위 큐(queue.PriorityQueue)

 

이 우선순위 큐 구현은 내부적으로 heapq를 사용하고 동일한 시간과 공간 복잡성을 공유합니다.

이제 일반적인 heapq와 다른점은 PriorityQueue는 동기 방식이며 동시에 여러 생산자와 소비자를 지원하는 잠금 체계를 제공합니다.

예시는 다음과 같습니다.

 

from queue import PriorityQueue
q = PriorityQueue()
q.put((2,'banana'))
q.put((1,'coke'))
q.put((3,'rock'))

while not q.empty():
    next_item = q.get()
    print(next_item)
# 출력 값
# (1, 'coke')
# (2, 'banana')
# (3, 'rock')

 

 

Python list 연산에 따른 시간 복잡도

queue — 동기화된 큐 클래스 — Python 3.8.6rc1 문서

파이썬 List, Tuple의 개념