추상 자료형 vs 구현: 계약과 기계장치

"자료형은 어떻게 지어졌냐가 아니라 뭘 약속하냐로 정의될 수 있어. 그 분리 — 계약 대 기계장치 — 가 소프트웨어 전체에서 가장 깊은 아이디어 중 하나야."

서로 다른 두 질문

스택 연산 하나 건드리기 전에, 이 구분을 체화해, 앞으로 올 모든 구조를 생각하는 방식을 다시 빚으니까:

추상 자료형 (ADT) 은 계약이야: 연산 집합이랑 그것들이 어떻게 행동하는지. 스택 ADT 는 push, pop, peek, is_empty 를 약속하고, pop 이 늘 가장 최근 push 된 항목을 반환한다는 규칙.
구현 은 기계장치야: 계약을 이행하는 실제 코드랑 저장소. 스택은 동적 배열로, 연결 리스트로, 뭔가 이국적인 걸로 지을 수 있어 — 그리고 push/pop 쓰는 호출자는 차이를 못 알아.

계약은 무엇; 구현은 어떻게. 분리 가능하고, 분리해두는 게 초능력이야.

왜 분리가 중요한가

기계장치가 아니라 계약에 대고 프로그래밍하면, 기계장치가 밑에서 바뀌어도 네 코드엔 영향 제로야. 배열 기반 스택으로 시작하고; 나중에 안정적 참조가 필요한 걸 알고 연결 리스트 기반으로 갈아끼워 — 모든 호출자가 계속 작동해, 계약만 알았으니까. 이게 정확히 아빠가 사방에서 보는 OOP 아이디어야: 인터페이스가 추상화고, 클래스는 하나의 구체적 실현이고, 넌 인터페이스에 의존해. 스택은 마지막에 들어온 게 먼저라는 개념 이고; 배열이나 연결 리스트는 그 개념을 진짜로 만드는 한 방법일 뿐이야.

ADT 는 계약 (연산 + 행동); 구현은 그걸 만족하는 기계장치. 계약에 대고 프로그래밍하면, 기계장치를 자유롭게 갈아끼워. 맞는 기계장치 전에 맞는 계약을 고르는 게 설계 한 수야.

같은 계약, 두 기계

아래 코드는 정확히 같은 스택 계약을 두 방식으로 지어 — 한 번은 Python 리스트로, 한 번은 연결 리스트로. 둘 다 동일한 push/pop/peek 를 노출해. 스택을 쓰는 함수는 어느 걸 받았는지 알 필요도 신경 쓸 필요도 없어. 그 교환 가능성이 핵심 전부야: 알고리즘을 "스택" 으로 추론하고, 네 제약 (메모리, 참조, 캐시) 에 맞는 구현을 따로 골라.

피파의 고백

난 "스택" 을 "Python 리스트" 랑 같은 것처럼 뭉뚱그리곤 했어. 아빠가 밀었어: "스택이 리스트야, 아니면 규칙이야?" 마침내 계약 (LIFO) 을 기계장치 (리스트, 연결 리스트, 배열) 에서 분리하니, 안개가 걷혔어 — 알고리즘을 내가 필요한 행동으로 추론하고 구현은 나중에 고를 수 있었어. Foundations 트랙이랑 같은 교훈, 날카로워진 거: 추상화 먼저 이름 붙이고, 기계장치 둘째로 골라.

Code

스택 계약 하나, 구현 둘·python

# 계약 하나: push, pop, peek, is_empty (LIFO). 기계 둘.

class ArrayStack:
    """Python 리스트 (동적 배열) 기반 스택."""
    def __init__(self): self._data = []
    def push(self, x): self._data.append(x)        # 분할 상환 O(1)
    def pop(self):     return self._data.pop()      # 끝에서 O(1)
    def peek(self):    return self._data[-1]
    def is_empty(self): return not self._data

class _Node:
    def __init__(self, val, nxt): self.val = val; self.next = nxt

class LinkedStack:
    """연결 리스트 기반 스택 (head 에서 push/pop)."""
    def __init__(self): self._head = None
    def push(self, x): self._head = _Node(x, self._head)   # O(1)
    def pop(self):
        node = self._head; self._head = node.next; return node.val  # O(1)
    def peek(self):    return self._head.val
    def is_empty(self): return self._head is None

def reverse_with_stack(items, stack):   # *어느* 기계로든 작동
    for x in items: stack.push(x)
    out = []
    while not stack.is_empty(): out.append(stack.pop())
    return out

print(reverse_with_stack([1, 2, 3], ArrayStack()))   # [3, 2, 1]
print(reverse_with_stack([1, 2, 3], LinkedStack()))  # [3, 2, 1] — 같은 계약

Exercise

큐 계약을 정의하는 네 연산을 (그리고 그걸 스택이 아닌 큐로 만드는 행동 규칙을) 적어봐. 그다음: 큐를 구현해야 하고 앞-제거 속도가 결정적이면, 어떤 기계장치를 고르고 뭘 피할지 — 그리고 왜 계약은 어느 쪽이든 동일하게 유지되는지 설명해.

Hint

큐 계약: enqueue, dequeue, peek, is_empty — FIFO (dequeue 가 가장 오래된 걸 반환). 덱이나 연결 리스트를 골라 (O(1) 앞-제거); 평범한 리스트는 피해 (pop(0) 이 O(n)). 계약은 안 바뀌고; 기계의 비용만 달라.

서로 다른 두 질문

왜 분리가 중요한가

같은 계약, 두 기계

피파의 고백

Code

External links

Exercise

Progress

댓글 0