[Python] 스택(stack)과 힙(heap)

목차

1. 스택(stack)
2. 힙(heap)

---

스택(stack)

스택은 LIFO(Last In First Out) 원칙을 따르는 선형 데이터 구조입니다. 즉, 스택에 추가된 마지막 요소가 제거되는 첫 번째 요소입니다. 스택은 스택의 맨 위에서 항목이 추가(푸시)되거나 제거(팝)되는 항목 모음으로 시각화할 수 있습니다. LIFO 특성으로 인해 스택은 상위 요소에 대한 액세스만 허용하고 하위 요소는 허용하지 않습니다.

스택과 관련된 두 가지 기본 작업이 있습니다.

• Push: 스택 맨 위에 요소를 추가합니다.
• Pop: 스택에서 맨 위 요소를 제거합니다.

스택에는 다음과 같은 보조 작업도 있을 수 있습니다.

• Peek 또는 Top: 스택의 맨 위 요소를 제거하지 않고 반환합니다.
• IsEmpty: 스택이 비어 있는지 확인합니다.
• Size: 스택의 요소 수를 반환합니다.

다음은 목록을 사용하여 Python에서 간단한 스택 구현의 예입니다.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

# Using the stack
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek())  # Output: 2
print(stack.is_empty())  # Output: False
print(stack.size())  # Output: 2

 

이 예에서는 목록을 사용하여 요소를 저장하는 Stack 클래스를 만들었습니다. 이 클래스에는 푸시, 팝, 엿보기, 스택이 비어 있는지 확인, 스택 크기 찾기 등의 메서드가 있습니다. 그런 다음 스택을 사용하여 LIFO 원칙에 따라 다양한 작업을 수행할 수 있습니다.

---

힙(heap)

힙은 힙 속성을 충족하는 특수 트리 기반 데이터 구조입니다. 완전한 이진 트리입니다. 즉, 왼쪽에서 오른쪽으로 채워지는 마지막 수준을 제외하고 트리의 각 수준이 완전히 채워집니다. 힙에서 각 노드의 키는 자식 키보다 크거나 같거나(max-heap) 작거나 같습니다(min-heap).

힙에는 두 가지 유형이 있습니다.

• 최대 힙(Max-heap)
  최대 힙에서 부모 노드는 자식 키보다 크거나 같은 키를 가집니다. 가장 큰 키는 루트 노드에 있습니다.
  
  
• 최소 힙(Min-heap)
  최소 힙에서 부모 노드는 자식 키보다 작거나 같은 키를 가집니다. 가장 작은 키는 루트 노드에 있습니다.

힙은 일반적으로 우선 순위 큐를 구현하는 데 사용되며 우선 순위가 가장 높거나 낮은 요소에 효율적으로 액세스할 수 있습니다. 힙의 가장 일반적인 응용 프로그램은 힙 데이터 구조를 사용하여 요소를 정렬하는 힙 정렬 알고리즘입니다.

힙과 관련된 몇 가지 일반적인 작업은 다음과 같습니다.

• 삽입(Insert): 힙 속성을 유지하면서 요소를 힙에 추가합니다.
• 추출(Extract): 힙에서 루트 요소(최대 또는 최소)를 제거하고 반환한 다음 힙 속성을 유지하도록 힙을 재구성합니다.
• Peek: 루트 요소(최대 또는 최소)를 제거하지 않고 반환합니다.

Python에서 heapq 모듈은 최소 힙이 있는 힙 데이터 구조의 구현을 제공합니다. 다음은 heapq 모듈을 사용하여 최소 힙을 만드는 예입니다.

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

print(heap)  # Output: [1, 3, 2]

smallest_element = heapq.heappop(heap)
print(smallest_element)  # Output: 1
print(heap)  # Output: [2, 3]

# Peek at the smallest element without removing it
smallest_element = heap[0]
print(smallest_element)  # Output: 2

 

이 예제에서는 heapq 모듈을 사용하여 최소 힙을 만듭니다. heappush 함수를 사용하여 요소를 힙에 삽입하고 heappop 함수를 사용하여 가장 작은 요소를 제거합니다. 제거하지 않고 가장 작은 요소를 살펴보려면 목록의 첫 번째 요소(인덱스 0)에 액세스하면 됩니다. heapq 모듈은 최대 힙 구현을 제공하지 않지만 값을 삽입하기 전과 추출한 후에 값을 부정하여 최대 힙을 생성할 수 있습니다.