자료구조 - 스택(Stack)과 큐(Queue) 그리고 힙큐(Heapq)

스택(Stack)

 

스택은 후입선출(LIFO, Last In First Out) 방식의 자료구조이다.

마지막에 삽입된 데이터가 가정 먼저 삭제되는 구조이다.

 

스택에서 쓸 수있는 메서드에는 push, pop, peek이 있다.

• push: 데이터를 스택에 추가
• pop: 스택에서 가장 최근에 추가된 데이터를 제거하고 반환
• peek: 스택의 가장 상단에 있는 데이터를 반환하지만 제거하지는 X

그림으로 이해해보자!

 

 

push

 

처음에 push(1)을 하였다.

다음에 push(2)를 하였다.

마지막으로 push(3)을 하였다.

 

그럼, 왼쪽과 같은 그림으로 표현할 수 있다.

 

 

 

 

 

 

pop

 

pop()을 하였더니 마지막으로 push했던 값 3이 제거되고 반환되었다.

 

 

 

 

 

 

 

peek

 

peek()을 하였더니 값이 제거되지는 않고 가장 마지막 값인 2가 반환되었다.

 

 

 

 

 

 

그럼 오른쪽 그림을 보면 어떤 값이 반환될까?

 

바로바로바로

 

1이다.

 

처음에 pop()을 하여 값 2가 제거되고 peek()을 하면 가장 마지막인 값 1이 반환된다.

 

 

보통 웹 브라우저의 뒤로가기 기능, 재귀 알고리즘 등이 스택 구조로 구현된다.

 

 

큐(Queue)

 

큐는 스택과 반대로 선입선출(FIFO, First In First Out) 방식의 자료구조이다.

먼저 삽입된 데이터가 먼저 삭제되는 구조이다.

 

큐에서 쓸 수있는 메서드에는 enqueue, dequeue, peek이 있다.

• enqueue: 데이터를 큐에 추가
• dequeue: 큐에서 가장 먼저 추가된 데이터를 제거하고 반환
• peek: 큐의 가장 앞에 있는 데이터를 반환하지만 제거하지 X

그림으로 이해해보자!

enqueue

처음에 enqueue(1)을 하였다.
다음에 enqueue(2)를 하였다.
마지막으로 enqueue(3)을 하였다.

그럼, 왼쪽과 같은 그림과 같다.

 

 

 

 

 

dequeue

dequeue()을 하였더니 처음에 enqueue했던 값 1이 제거되고 반환되었다.

 

 

 

 

 

peek

 

peek()을 하였더니 값이 제거되지는 않고 가장 처음 값인 2가 반환되었다.

 

 

 

 

 

 

 

그럼 오른쪽 그림을 보면 어떤 값이 반환될까?

 

바로바로바로

3이다.

 

처음에 dequeue()을 하여 값 2가 제거되고 peek()을 하면 가장 처음 값 3이 반환된다.

 

프린터의 인쇄 대기열, 은행의 대기 번호 시스템 등이 큐 구조로 구현된다.

 

 

힙큐를 설명하기 전에 먼저 우선순위 큐를 먼저 살펴보자.

 

 

우선순위 큐(Priority Queue)

 

우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지며, 우선순위에 따라 요소가 처리되는 특수한 큐 자료구조이다.

일반적인 큐가 선입선출(FIFO) 방식을 따르는 반면, 우선순위 큐는 우선순위가 높은 요소가 먼저 처리된다.

*우선순위 큐는 시스템이 다수의 작업을 효율적으로 처리해야 하는 상황에서 매우 유용한 자료구조이다.

 

우선순위 큐에서 쓰이는 메서드는 insert, delete, peek이 있다.

• insert: 큐에 요소를 넣는 메서드. 다만, 우선순위 정보도 같이 넣어줘야 한다.
• delete: 가장 우선순위가 높은 요소를 제거하고 반환
• peek: 가장 우선순위가 높은 요소를 반환

 

 

왼쪽 그림과 같이 큐가 있는데 가장 큰 값이 가장 우선순위가 높다고 가정해보자.

 

 

 

 

 

 

 

 

 

 

이 상태에서 delete()를 하게된다면?

가장 우선순위가 높은 30이 제거된다.

 

 

 

 

 

 

 

이상태에서 peek()을 한다면?

 

20과 5 중 우선순위가 높은 20이 반환된다.

 

 

 

 

 

우선순위 큐와 항상 같이 따라다니는 힙(Heap)이라는 것이 있다.

힙은 주로 이진 트리(Binary Tree) 기반으로 구현된다.

여기서 이진 트리는 부모-자녀처럼 계층적인 형태를 가지는 구조인데 자녀가 최대 두 개인 트리라 이진 트리라고 부른다.

아래 그림처럼 말이다.

 

 

 

 

 

힙은 max heap과 min heap이 있다.

• max heap: 부모 노드의 키(key)가 자식 노드들의 키(key)보다 크거나 같은 트리
• min heap: 부모 노드의 키(key)가 자식 노드들의 키(key)보다 작거나 같은 트리

 

 

그럼 min heap을 가진 이진트리에 0 값을 insert 한다면??

 

위 그림과 같이 처음엔 끝자리에 0이 insert 되었다가, 계속 부모노드와 비교를 하면서 스위칭되고..

결국엔 원래 1 자리로 insert가 된다.

 

 

 

힙큐(Heapq)

 

heapq는 Python의 내장 모듈로, 힙(Heap) 자료 구조를 효율적으로 관리하고 사용할 수 있도록 도와준다.

힙은 완전 이진 트리(Complete Binary Tree) 기반의 자료 구조로, 우선순위 큐(Priority Queue)를 구현하는 데 유용하다.

heapq 모듈은 기본적으로 최소 힙(Min-Heap)을 제공한다.

 

주요 기능은 다음과 같다.

 

1. heapq.heappush(heap, item):

• 힙에 요소(item)을 추가
• 새로운 요소를 힙에 추가한 후, 힙 속성을 유지하도록 자동으로 조정

2. heapq.heappop(heap):

• 힙에서 가장 작은 요소를 제거하고 반환
• 반환 후, 힙 속성이 유지되도록 재정렬
• 만약 힙이 비어 있으면 IndexError를 발생

3. heapq.heapify(x):

• 리스트 x를 힙으로 변환(기존 리스트를 힙으로 재구성하여 최소 힙 속성을 가지도록)

4. heapq.heappushpop(heap, item):

• item을 힙에 추가한 후, 힙에서 가장 작은 요소를 제거하고 반환
• 별도로 heappush()와 heappop()을 호출하는 것보다 효율적!!

5. heapq.heapreplace(heap, item):

• 힙에서 가장 작은 요소를 제거하고, 새로운 item을 힙에 추가
• heappushpop()과 유사하지만, 순서가 다르기 때문에 반환되는 값이 다를 수 있다.(이건 먼저 제거하고 추가)

6. heapq.nlargest(n, iterable, key=None):  <-----> heapq.nsmallest(n, iterable, key=None)

• iterable에서 가장 큰 n개의 요소를 반환
• 선택적 key 함수로 정렬 기준을 지정할 수 있다.

6번 사용예시

# nsmallest와 nlargest 사용
nums = [10, 20, 30, 40, 50]
print("3 smallest numbers:", heapq.nsmallest(3, nums))  # [10, 20, 30]
print("3 largest numbers:", heapq.nlargest(3, nums))  # [50, 40, 30]

 

힙큐는..

데이터의 일부를 빠르게 정렬하거나 특정 범위의 값들을 효율적으로 추출하는 데 유용하다.

그렇지만 파이썬은 기본적으로 최소힙을 제공하기 때문에 최대힙을 구현하려면 요소의 부호를 반전하여 저장해야 한다!!