[자료구조] 큐, 스택, 힙

스택 (Stack)

후입선출(LIFO, Last In First Out)

사용

리스트로 구현

# define stack
stack = []

# add
stack.append(item)

# pop (가장 마지막에 in된 item return하며 stack에서 제거)
stack.pop()

큐 (Queue)

선입선출(FIFO, First In First Out)

사용

collections 모듈의 deque 사용하여 구현
deque 양방향 연결 리스트로 구성

# import library
from collections import deque

# define queue
queue = deque()

# add
queue.append(item)

# add left
queue.appendleft(item)

# insert
queue.insert(idx, item)

# pop 가장 마지막(오른쪽)에 append된 item 리턴 후 제거
queue.pop()

# pop left 가장 처음(왼쪽)에 append된 item 리턴 후 제거
queue.popleft()

# convert deque to list
list(queue)

힙 (Heap)

우선순위큐 (priority queue, 우선 순위가 높은 데이터부터 return)를 위한 자료구조
노드가 왼쪽부터 채워지는 완전이진트리 형태

Min Heap

      1
     / \
    3   2
   / \ / \
  5  4 8  7
 / \
9  6

작은 수를 우선 순위에 둠
자식 노드보다 부모 노드의 값이 작음

Max Heap

      9
     / \
    8   7
   / \ / \
  6  4 3  2
 / \
1  5

큰 수를 우선 순위에 둠
자식 노드보다 부모 노드의 값이 큼

사용

# import heapq module
import heapq

# define heap
heap = []

# insert node
heapq.heappush(heap, item)

# delete node 제일 우선순위가 높은 item return
heapq.heappop(heap)

---

들숨에 알고리즘! 날숨에 알고리즘!

---

References

https://velog.io/@gillog/Python-Stack-Queue-%EA%B8%B0%EB%B3%B8-module-%EC%82%AC%EC%9A%A9-%EC%A0%95%EB%A6%AC
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
https://velog.io/@gnwjd309/data-structure-heap