[파이썬] 스택, 큐, 힙

스택

후입선출, LIFO(Last in First Out)형식의 자료 구조.

파이썬에서는 리스트로 사용해도 될 것 같다.

넣을 때는 stack.append(num)을, 뺄 때는 .pop()을 사용한다.

큐

선입선출, FIFO(First in First Out)형식의 자료구조.

파이썬에선 collections 모듈의 deque를 이용한다.

생성 queue = deque()

요소 넣기 queue.append(요소)

요소 빼기 (queue.popleft())

힙

최소힙
최소힙은 완전이진트리로 구현된 자료구조이며, 부모 노드 값 > 자식값으로 저장한다. 그렇게 하면 root(최상위)노드는 입력된 값들 중 가장 작은 값이 저장된다.

최대힙

최대힙은 완전 이진트리로 구현된 자료구조이며, 부모 노드 값 < 자식값으로 저장한다. 그러면 root노드는 입력된 값들 중 가장 큰 값이 저장되게 된다.

파이썬에서의 힙의 사용은 heapq 모듈을 사용한다.

데이터 추가 heapq.heappush(힙, 넣을 배열)

데이터 삭제 heapq.heappop(힙) - 루트 노드를 삭제한다

리스트를 힙으로 변환 heapq.heapfy(list) - $O(N)$

heapq는 최소힙만 지원하므로 최대힙으로 구현하려면 요소에 -1을 곱한 값을 넣으면 된다.