[TIL] 알고리즘&자료구조: 스택과 큐, 우선순위 큐

1. 스택 (Stack) & 큐 (Queue)

1-1. 스택 자료구조

• 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)

• 입구와 출구가 동일한 형태, 상자쌓기로 시각화 가능

• DFS 등 다양한 알고리즘에서 사용되는 자료구조

• 시간복잡도는 항상 O(1)

• 파이썬에서는 리스트 형식을 그대로 사용

📌 구현 예제

stack = []

# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1])	# 최상단 원소부터 출력
print(stack)	# 최하단 원소부터 출력

1-2. 큐 자료 구조 (a.k.a. 공평한 자료구조)

• 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)

• 입구와 출구가 모두 뚫려 있는 터널과 같은 형태, 대기열로 시각화 가능

• 파이썬에서 큐를 구현할 때에는 리스트 형식을 사용하면 시간복잡도가 더 높기 때문에 deque 라이브러리 사용

• 데이터 삽입은 append() , 데이터 삭제는 popleft() 를 사용하므로 해당 메소드의 시간복잡도는 O(n)이지만 관행적으로 사용

📌 구현 예제

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)	# 먼저 들어온 순서대로 출력
queue.reverse()	# 역순으로 바꾸기
print(queue)	# 나중에 들어온 원소부터 출력

2. 우선순위 큐 (Priority Queue)

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용
• 자료구조 비교표

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높으 데이터

• 구현 방법

  1. 리스트로 구현
  2. 힙(heap)으로 구현

• 시간 복잡도

  우선순위 큐 구현 방식	삽입 시간	삭제 시간
  리스트	O(1)	O(N)
  힙(Heap)	O(log N)	O(log N)

  단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업 = 힙 정렬

  시간 복잡도: O(N log N)

  👉 따라서 힙의 시간 복잡도가 리스트보다 더 낮음!

힙(Heap)의 특징

• 완전 이진 트리 자료구조

  루트노드➡왼쪽 자식 노드➡오른쪽 자식 노드 차례로 데이터가 삽입되는 트리

• 항상 루트 노트(root node) 제거

• 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에 사용된다.

• 최소 힙(min heap)

  • 루트 노드가 가장 작은 값을 가진다.
  • 값이 가장 작은 데이터가 우선적으로 제거된다.

• 최대 힙(max heap)

  • 루트 노드가 가장 큰 값을 가진다.
  • 값이 큰 데이터가 우선적으로 제거된다.

최소 힙 구성 함수: Min-Heapify()

• 상향식: 부모 노드로 거슬러 올라가며 부모보다 자신의 값이 더 작은 경우에는 부모와 자신의 위치를 교체
• 새 원소가 삽입되었을 때에는 O(log N)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.
• 힙에서 원소를 제거할 때에도 O(log N)의 시간 복잡도로 힙 성질 유지가 가능하다.
  1. 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.
  2. 루트 노드에서 하향식으로 Heapify() 진행

📌 구현 예제

import sys
import heapq	# 파이썬의 힙 라이브러리
input = sys.stdin.readLine

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입 (-1을 인자에 넣으면 max heap 가능)
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 (-1을 인자에 넣으면 max heap 가능)
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

n = int(input())
arr = []

for i in range(n):
    arr.append(int(input()))

res = heapsort(arr)

for i in range(n):
    print(res[i])