Python - Stack & Queue & Heap

스택 Stack

• 쌓는다는 의미로 데이터를 한쪽에서만 넣고 빼는 자료구조

• 후입선출 방식, LIFO(Last-in First-out)

Stack 사용

• 괄호 매칭

• 함수 호출(재귀 호출)

• 백트래킹

• DFS, 깊이 우선 탐색

큐 Queue

• 한쪽 끝에서 데이터를 넣고 다른 한쪽에서 데이터를 뺄 수 있는 자료구조

• 선입선출 방식, FIFO(First-in First-out)

• dequeue : 큐의 맨 앞 데어터를 가져오는 행위

• enqueue : 큐의 맨 뒤에 데이터를 삽입하는 행위

Queue 사용

• 순서와 대기

• 프로세스 관리(데이터 버퍼)

• 클라이언트/서버(Message Queue)

• BFS(너비 우선 탐색)

• 다익스트라-우선순위큐

리스트 큐

리스트를 이용한 큐에서는 앞의 데이터가 빠지면서 인덱스가 하나씩 당겨짐, 데이터가 많을 경우 비효율적

덱 Deque(Double-Ended Queue)

: 양 방향으로 삽입과 삭제가 자유로운 큐

• 양 방향 삽입 추출이 모두 리스트 큐보다 빠름

• 데이터의 삽입/추출이 많은 경우 시간을 크게 단축시킬 수 있음

from collections import deque

queue = deque(range(1, 5))
queue.append(5)
queue.popleft()
print(*queue)   # 2 3 4 5

힙 Heap

우선순위 큐 Priority Queue

• 우선순위를 기준으로 가장 우선순위가 높은 데이터가 가장 먼저 나가는 방식

• 순서가 아닌 우선순위(중요도, 크기 등)를 기준으로 가져올 요소를 결정

  • 가중치가 있는 데이터
  • 작업 스케줄링
  • 네트워크

• 우선순위 큐 => 힙 큐

힙의 특징

• 최대값, 최소값을 빠르게 찾아내도록 만들어진 데이터구조(큐와의 차이점)

• 완전 이진트리의 형태로 느슨한 정렬상태를 지속적으로 유지

• 데이터가 지속적으로 정렬되어야 하는 경우, 데이터 삽입/삭제가 빈번한 경우 사용

파이썬의 heapq 모듈

• Minheap(최소힙)으로 구현되어 있음

• Maxheap을 구현하고 싶으면 heap에 데이터를 넣고 뺄 때 '-'를 붙이면 됨

  heapq.heappush(list, -x)
  print(-heapq.heappop(list))

• 삽입, 삭제, 수정, 조회 연산의 속도가 리스트보다 빠름

  연산 종류	힙	리스트
  Get item	O(1)	O(1)
  Insert item	O(logN)	O(1)/O(N)
  Delete item	O(logN)	O(1)/O(N)
  Search item	O(N)	O(N)

• heapq.heapify(list) : list를 heap으로 변환

• heapq.heappush(heap, item) : item값을 heap으로 push, 튜플일 경우 첫번째인자-두번째인자 순으로 비교

• heapq.heappop(heap) : heap에서 가장 작은 항목 반환 후 삭제

• heapq.heappushpop(heap, item) : item을 push 후 가장 작은 항목 반환 후 pop

• heapq.heapreplace(heap, item) : 가장 작은 항목 반환 & pop 한 후 item을 push