스택과 힙

스택 (Stack)

스택은 메모리의 일부로, 코드 블록 내에서 지역 변수 및 함수 호출의 매개 변수와 반환 값과 같은 임시 데이터를 저장하는 데 사용됩니다. 이러한 데이터는 Last-In-First-Out (LIFO) 방식으로 처리됩니다. 스택은 메모리의 상위 주소에서 낮은 주소로 확장되며, 일반적으로 메모리 할당이 비교적 적고 빠른 속도로 작동합니다. 그러나, 스택에 할당된 메모리는 코드 블록이 끝날 때 자동으로 해제되므로, 저장된 데이터는 코드 블록 내에서만 유효합니다.

스택의 장단점

장점

• 메모리 할당이 비교적 적고 빠른 속도로 작동합니다.
• 데이터 처리 방식이 LIFO 방식으로 간단합니다.
• 데이터의 유효 범위가 코드 블록 내에서만 유지되기 때문에 변수 이름의 충돌이나 데이터 누수를 방지할 수 있습니다.

단점

• 메모리 할당량이 제한적입니다.
• 스택 프레임이 지속되는 동안 데이터가 유지되기 때문에, 재귀 호출과 같은 깊이가 깊은 구조에서는 스택 오버플로우(스택이 가득 차서 더 이상 데이터를 저장할 수 없는 상태)가 발생할 수 있습니다.
• 전체 데이터를 사용하려면 스택의 최상위부터 데이터를 모두 꺼내야 하기 때문에, 중간에 있는 데이터에 접근하기 번거로울 수 있습니다.
• 스택을 사용하여 코드를 작성할 때는 스택 프레임을 계산하고 스택 오버플로우를 방지하기 위해 스택의 크기를 고려해야합니다. 또한, 중간에 있는 데이터에 접근이 필요한 경우에는 스택 대신 다른 데이터 구조를 사용하는 것이 좋습니다.

# 빈 리스트 생성
stack = []

# 원소 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 최상위 원소 출력 후 제거
print(stack.pop()) # 3

# 최상위 원소 출력
print(stack[-1]) # 2

힙 (Heap)

힙은 메모리의 다른 부분으로, 크기와 수명이 프로그램 실행 중 동적으로 결정되는 데이터에 대한 메모리를 할당하는 데 사용됩니다. 힙은 메모리의 하위 주소에서 상위 주소로 확장되며, 일반적으로 스택보다 큰 메모리 할당이 가능합니다. 그러나, 힙 할당은 스택 할당보다 느리고 메모리 할당 후에도 메모리 해제를 수동적으로 처리해주어야 하기 때문에 작업이 복잡합니다. 힙은 프로그램에서 전역 변수, 정적 변수 및 동적 할당에 사용됩니다.

힙의 장단점

장점

• 스택보다 큰 메모리 할당이 가능합니다.
• 데이터를 추가하거나 제거할 때 일반적으로 스택보다 빠릅니다.
• 데이터의 유효 범위가 제한되지 않으므로, 전역 변수, 정적 변수, 동적 할당 등 프로그램 전반에서 사용될 수 있습니다.

단점

• 메모리 할당이 비교적 느리고 복잡합니다.
• 메모리 할당 후에도 메모리 해제를 수동적으로 처리해주어야 합니다.
• 데이터 처리 방식이 LIFO 방식이 아니므로, 중간에 있는 데이터에 접근하는 것이 번거로울 수 있습니다.

import heapq

# 빈 리스트 생성
heap = []

# 원소 추가
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 2)

# 최소값 출력 후 제거
print(heapq.heappop(heap)) # 1

# 최소값 출력
print(heap[0]) # 2