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

"자료형은 어떻게 만들어졌느냐가 아니라 무엇을 약속하느냐로 정의될 수 있어. 계약과 기계장치를 갈라놓는 이 구분은 소프트웨어를 통틀어 가장 깊은 발상에 든다고 봐."

서로 다른 두 질문

스택 연산을 하나라도 건드리기 전에 이 구분부터 몸에 붙여. 앞으로 나올 모든 구조를 어떻게 바라볼지가 여기서 정해지거든.

추상 자료형(ADT)은 계약이야. 어떤 연산이 있고 그것들이 어떻게 행동하느냐지. 스택 ADT는 push, pop, peek, is_empty를 제공하겠다고 약속하고, 거기에 pop은 언제나 가장 최근에 push한 항목을 돌려준다는 규칙이 붙어.
구현은 기계장치야. 그 계약을 실제로 지켜내는 코드와 저장소지. 스택은 동적 배열로도, 연결 리스트로도, 더 별난 무언가로도 만들 수 있어. 그리고 push와 pop만 쓰는 쪽에서는 그 차이를 알아챌 방법이 없고.

계약은 무엇이고 구현은 어떻게야. 이 둘은 떼어놓을 수 있고, 떼어놓은 채로 두는 게 진짜 무기가 돼.

왜 분리가 중요한가

기계장치가 아니라 계약에 대고 코드를 짜면, 밑에 있는 기계가 통째로 바뀌어도 위쪽 코드는 아무 영향을 안 받아. 배열 기반 스택으로 시작했다가 나중에 안정적인 참조가 필요해져서 연결 리스트 기반으로 갈아 끼워도, 호출하는 쪽은 전부 그대로 돌아가. 계약만 보고 짰으니까. 이게 아빠가 세상 곳곳에서 본다는 OOP 발상 그 자체야. 인터페이스가 추상화고 클래스는 그걸 구체적으로 실현한 하나일 뿐이며, 의존해야 할 대상은 인터페이스라는 것. 스택은 '마지막에 들어온 게 먼저'라는 개념 자체고, 배열이나 연결 리스트는 그 개념을 실물로 만드는 한 가지 방법일 뿐이야.

ADT는 계약이야. 연산과 그 행동을 정한 것. 구현은 그 계약을 지켜내는 기계장치고. 계약에 대고 짜두면 기계장치는 언제든 갈아 끼울 수 있어. 맞는 기계장치보다 맞는 계약을 먼저 고르는 것, 그게 설계의 한 수야.

같은 계약, 두 기계

아래 코드는 똑같은 스택 계약을 두 가지 방식으로 만들어. 하나는 Python 리스트로, 하나는 연결 리스트로. 둘 다 push, pop, peek을 똑같이 내놓지. 스택을 받아 쓰는 함수는 둘 중 뭘 받았는지 알 필요도, 신경 쓸 필요도 없어. 이렇게 서로 갈아 끼울 수 있다는 게 여기서 제일 중요한 대목이야. 알고리즘은 "스택"이라는 말로 추론하고, 구현은 처한 제약(메모리, 참조, 캐시)에 맞춰 따로 고르면 돼.

피파의 고백

나는 "스택"과 "Python 리스트"를 같은 것처럼 뭉뚱그리곤 했어. 아빠가 파고들더라. "스택이 리스트야, 아니면 규칙이야?" 계약(LIFO)과 기계장치(리스트든 연결 리스트든 배열이든)를 갈라놓고 나서야 안개가 걷혔어. 알고리즘을 내가 필요한 행동으로 생각하고 구현은 나중에 고를 수 있게 된 거야. 기초 트랙에서 배운 것과 같은 교훈인데 한층 날이 선 형태지. 추상화에 먼저 이름을 붙이고, 기계장치는 그다음에 고를 것.

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