스택(Stack)과 힙(Heap)은 프로그래밍에서 중요한 메모리 구조임
이들은 데이터를 저장하고 관리하는 데 사용되며, 주로 컴퓨터 프로그램의 실행 중에 데이터를 저장하는 데 쓰임
여기에서는 이 두 가지 구조의 기본적인 개념과 차이점에 대해 설명할 예정
스택(Stack)
스택은 후입선출(LIFO, Last In, First Out)의 구조를 가진 메모리 영역
이는 마치 접시를 쌓는 것처럼, 마지막에 들어온 데이터가 먼저 처리되는 구조
- 특징
- 구조: 스택은 선형 자료구조로, 데이터가 일렬로 쌓여있는 형태로, 맨 위에 있는 요소에만 접근 가능
- 연산: 스택에는 데이터를 스택에 추가하는 "push"와, 스택에서 데이터를 꺼내는 "pop"이라는 두 가지 연산이 존재
- 메모리 할당방식: 정적 메모리 할당을 사용하여 크기가 컴파일 시에 결정됨
- 용도: 함수 호출 시에 지역 변수, 매개변수, 반환 주소 등을 저장하는 데 사용되며, 재귀 알고리즘의 실행 흐름을 관리하는 데에도 사용
- 장점
- 빠른 접근 속도: 메모리에 연속적으로 저장되어 있으므로, 데이터에 빠르게 접근 가능
- 간편한 관리: 후입선출구조로인해 데이터의 추가와 삭제가 간단하며 메모리 관리에 용이
- 스택프레임: 함수 호출 시에 지역변수와 매개변수를 저장하는 스택 프레임을 통해 함수의 호출과 반환을 효율적으로 관리 가능
- 단점
- 크기 제한: 스택의 크기는 컴파일 시에 결정되므로 런타임 시에 동적으로 조정이 불가 → 정적으로 할당된 메모리의 한계로 인해 스택오버플로우가 발생 가능
- 임시저장만 가능: 스택은 임시데이터를 저장하는 데 사용되므로, 장기적인 데이터 보관에는 적합하지 않음
# 파이썬 리스트를 이용한 스택 구현 예시
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if self.is_empty():
return None
return self.stack.pop()
def peek(self):
if self.is_empty():
return None
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
# 스택 테스트
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
# 스택은 무조건 가장 나중에 삽입한 값부터 반환함
print("스택의 맨 위 항목:", stack.peek()) # 출력: 3
print("스택에서 팝된 항목:", stack.pop()) # 출력: 3
print("스택의 맨 위 항목:", stack.peek()) # 출력: 2
힙 (Heap)
힙은 메모리의 동적 할당 영역으로 데이터의 저장 및 관리를 위해 사용됨
힙은 데이터를 임의의 순서로 저장하며 메모리가 동적으로 할당되고 해제됨
맨 위의 요소에만 접근 가능한 스택과는 달리, 힙은 임의의 요소에 접근이 가능함
- 특징
- 구조: 힙은 트리 형태의 자료구조로, 노드들이 부모-자식 관계로 연결되며, 각 노드는 일반적으로 특정한 데이터를 저장
- 연산: 힙은 데이터를 삽입하는 "insert" 연산과, 삭제하는 "delete" 연산이 존재
- 메모리 할당방식: 동적 메모리 할당을 사용하여 런타임 중에 크기가 결정됨
- 용도: 동적으로 크기가 변하는 데이터 구조를 관리하는 데 사용되며, 주로 동적으로 할당된 객체나 배열, 그래프 등을 저장하기 위해 활용
- 장점
- 동적 할당: 힙은 런타임 중에 메모리를 동적으로 할당하므로, 유연한 데이터 구조를 생성 가능하며 크기제한이 없음
- 오랜 기간 데이터 보존 가능: 힙은 데이터의 수명이 프로그램의 실행 시간 동안 지속되므로, 장기적인 데이터 보존이 가능함
- 단점
- 메모리 누수: 메모리 해제를 제대로 처리하지 않으면 메모리 누수가 발생할 수 있음
- 접근 시간: 힙은 트리 구조로 데이터에 접근하는 데에 추가적인 시간이 소요될 수 있음
- 효율성: 동적할당 및 해제 작업은 상대적으로 오버헤드가 크므로, 스택에 비해 느릴 수 있음
# 파이썬 heapq 모듈을 이용한 힙 구현 예시
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 7)
# 마지막 삽입한 값이 아닌 값 반환 가능 (heapq.heappop 함수는 힙에서 가장 작은 값을 삭제하고 반환)
print("힙에서 팝된 최소 항목:", heapq.heappop(heap)) # 출력: 2
print("힙에서 팝된 최소 항목:", heapq.heappop(heap)) # 출력: 5